Treffer: Monadic Second-Order Unification is NP-complete
Title:
Monadic Second-Order Unification is NP-complete
Authors:
Source:
RTA 2004 : rewriting techniques and applications (Aachen, 3-5 June 2004)Lecture notes in computer science. :55-69
Publisher Information:
Berlin: Springer, 2004.
Publication Year:
2004
Physical Description:
print, 16 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Théorie programmation, Programming theory, Logique monadique, Monadic logic, Lógica monadica, Unification, Unificación
Document Type:
Konferenz
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
IIIA, CSIC, Campus de la UAB, Barcelona, Spain
Institut für Informatik, Johann Wolfgang Goethe-Universität, Postfach 11 19 32, 60054 Frankfurt, Germany
IMA, UdG, Campus de Montilivi, Girona, Spain
Institut für Informatik, Johann Wolfgang Goethe-Universität, Postfach 11 19 32, 60054 Frankfurt, Germany
IMA, UdG, Campus de Montilivi, Girona, Spain
ISSN:
0302-9743
Rights:
Copyright 2004 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.15851903
Database:
PASCAL Archive
Weitere Informationen
Monadic Second-Order Unification (MSOU) is Second-Order Unification where all function constants occurring in the equations are unary. Here we prove that the problem of deciding whether a set of monadic equations has a unifier is NP-complete. We also prove that Monadic Second-Order Matching is also NP-complete.