Monadic second-order unification Is NP-complete

Jordi Levy; Manfred Schmidt-Schauß; Mateu Villaret

doi:10.1007/978-3-540-25979-4_4

Monadic second-order unification Is NP-complete

Jordi Levy
, Manfred Schmidt-Schauß
, Mateu Villaret

CSIC
Goethe University Frankfurt
IMA

Research output: Chapter in Book/Conference proceeding › Book chapter › peer-review

12 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Vincent van Oostrom
Publisher	Springer Verlag
Pages	55-69
Number of pages	15
ISBN (Print)	3540221530
DOIs	https://doi.org/10.1007/978-3-540-25979-4_4
Publication status	Published - 2004
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3091
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-540-25979-4_4

Cite this

Levy, J., Schmidt-Schauß, M., & Villaret, M. (2004). Monadic second-order unification Is NP-complete. In V. van Oostrom (Ed.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 55-69). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3091). Springer Verlag. https://doi.org/10.1007/978-3-540-25979-4_4

Levy, Jordi ; Schmidt-Schauß, Manfred ; Villaret, Mateu. / Monadic second-order unification Is NP-complete. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Vincent van Oostrom. Springer Verlag, 2004. pp. 55-69 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{243381b7e310440286be024436fa56b2,

title = "Monadic second-order unification Is NP-complete",

abstract = "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.",

author = "Jordi Levy and Manfred Schmidt-Schau{\ss} and Mateu Villaret",

year = "2004",

doi = "10.1007/978-3-540-25979-4\_4",

language = "English",

isbn = "3540221530",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "55--69",

editor = "\{van Oostrom\}, Vincent",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

Levy, J, Schmidt-Schauß, M & Villaret, M 2004, Monadic second-order unification Is NP-complete. in V van Oostrom (ed.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3091, Springer Verlag, pp. 55-69. https://doi.org/10.1007/978-3-540-25979-4_4

Monadic second-order unification Is NP-complete. / Levy, Jordi; Schmidt-Schauß, Manfred; Villaret, Mateu.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Vincent van Oostrom. Springer Verlag, 2004. p. 55-69 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3091).

Research output: Chapter in Book/Conference proceeding › Book chapter › peer-review

TY - CHAP

T1 - Monadic second-order unification Is NP-complete

AU - Levy, Jordi

AU - Schmidt-Schauß, Manfred

AU - Villaret, Mateu

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/33749423952

U2 - 10.1007/978-3-540-25979-4_4

DO - 10.1007/978-3-540-25979-4_4

M3 - Book chapter

AN - SCOPUS:33749423952

SN - 3540221530

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 55

EP - 69

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - van Oostrom, Vincent

PB - Springer Verlag

ER -

Levy J, Schmidt-Schauß M, Villaret M. Monadic second-order unification Is NP-complete. In van Oostrom V, editor, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 55-69. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-25979-4_4

Monadic second-order unification Is NP-complete

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this