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

Producció científica: Capítol del llibre/Acta del congrés › Capítol de llibre › Avaluat per experts

12 Cites (Scopus)

Resum

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.

Idioma original	Anglès
Títol de la publicació	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Vincent van Oostrom
Editor	Springer Verlag
Pàgines	55-69
Nombre de pàgines	15
ISBN (imprès)	3540221530
DOIs	https://doi.org/10.1007/978-3-540-25979-4_4
Estat de la publicació	Data de publicació - 2004
Publicat externament	Sí

Sèrie de publicacions

Nom	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volum	3091
ISSN (imprès)	0302-9743
ISSN (electrònic)	1611-3349

Accés al document

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

Altres arxius i enllaços

Enllaç a la publicació de Scopus

Com citar-ho

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) (pàg. 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. pàg. 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, pàg. 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àg. 55-69 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3091).

Producció científica: Capítol del llibre/Acta del congrés › Capítol de llibre › Avaluat per experts

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àg. 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

Resum

Sèrie de publicacions

Accés al document

Altres arxius i enllaços

Fingerprint

Com citar-ho