Other formats:
BibTeX
LaTeX
RIS
@inproceedings{483395, author = {Klíma, Ondřej}, address = {Berlin}, booktitle = {Mathematical Foundations of Computer Science 2002:27th International Symposium}, keywords = {unification; free idempotent semigroups; equations}, language = {eng}, location = {Berlin}, isbn = {3-540-44040-2}, pages = {423-432}, publisher = {Springer-Verlag}, title = {Unification Modulo Associativity and Idempotency Is NP-complete}, year = {2002} }
TY - JOUR ID - 483395 AU - Klíma, Ondřej PY - 2002 TI - Unification Modulo Associativity and Idempotency Is NP-complete VL - Lecture Notes in Computer Science, 2420 PB - Springer-Verlag CY - Berlin SN - 3540440402 KW - unification KW - free idempotent semigroups KW - equations N2 - We show that the unification problem for the theory of one associative and idempotent function symbol (AI-unification), i.e. solving word equations in free idempotent semigroups, is NP-complete. ER -
KLÍMA, Ondřej. Unification Modulo Associativity and Idempotency Is NP-complete. In \textit{Mathematical Foundations of Computer Science 2002:27th International Symposium}. Berlin: Springer-Verlag, 2002, p.~423-432. Lecture Notes in Computer Science, 2420. ISBN~3-540-44040-2.
|