Matching Modulo Associativity and Idempotency is NP-Complete

• Authors: KLÍMA Ondřej; SRBA Jiří
• Year of publication: 2000
• Type: Article in Proceedings
• Conference: Mathematical Foundation of Computer Science 2000, 25th International Symposium
• MU Faculty or unit: Faculty of Science
• Field: General mathematics
• Description: 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.

Related projects

• Infinite state concurrent systems - models and verification
• Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing
• Mathematical structures of algebra and geometry