Matching Modulo Associativity and Idempotency is NP-Complete

KLÍMA, Ondřej and Jiří SRBA. Matching Modulo Associativity and Idempotency is NP-Complete. In Mathematical Foundation of Computer Science 2000, 25th International Symposium. Berlin: Springer-Verlag, 2000, p. 456-466. Lecture Notes in Computer Science, 1893. ISBN 3-540-67901-4.

Basic information

• Original name: Matching Modulo Associativity and Idempotency is NP-Complete
• Authors: KLÍMA, Ondřej and Jiří SRBA.
• Edition: Berlin, Mathematical Foundation of Computer Science 2000, 25th International Symposium, p. 456-466, Lecture Notes in Computer Science, 1893, 2000.
• Publisher: Springer-Verlag

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10101 Pure mathematics
• Country of publisher: Slovakia
• Confidentiality degree: is not subject to a state or trade secret
• RIV identification code: RIV/00216224:14310/00:00002108
• Organization unit: Faculty of Science
• ISBN: 3-540-67901-4

Abstract

We show that AI-matching (AI denotes the theory of an associative and idempotent function symbol), which is solving matching word equations in free idempotent semigroups, is NP-complete.

Links

• GA201/00/0400, research and development project: Name: Nekonečně stavové souběžné systémy - modely a verifikace

Investor: Czech Science Foundation, Infinite state concurrent systems - models and verification

• 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

• MSM 143300001, plan (intention): Name: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů

Investor: Ministry of Education, Youth and Sports of the CR, Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing