KLÍMA, Ondřej. Unification Modulo Associativity and Idempotency Is NP-complete. In 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.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Unification Modulo Associativity and Idempotency Is NP-complete
Authors KLÍMA, Ondřej (203 Czech Republic, guarantor).
Edition Berlin, Mathematical Foundations of Computer Science 2002:27th International Symposium, p. 423-432, Lecture Notes in Computer Science, 2420, 2002.
Publisher Springer-Verlag
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10101 Pure mathematics
Country of publisher Poland
Confidentiality degree is not subject to a state or trade secret
RIV identification code RIV/00216224:14310/02:00007266
Organization unit Faculty of Science
ISBN 3-540-44040-2
UT WoS 000181442200035
Keywords in English unification; free idempotent semigroups; equations
Tags equations, free idempotent semigroups, unification
Tags International impact, Reviewed
Changed by Changed by: doc. Mgr. Ondřej Klíma, Ph.D., učo 3868. Changed: 21/11/2006 17:47.
Abstract
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.
Links
MSM 143100009, plan (intention)Name: Matematické struktury algebry a geometrie
Investor: Ministry of Education, Youth and Sports of the CR, Mathematical structures of algebra and geometry
PrintDisplayed: 19/6/2024 05:19