Matching Modulo Associativity and Idempotency is NP-Complete

• Autoři: KLÍMA Ondřej; SRBA Jiří
• Rok publikování: 2000
• Druh: Článek ve sborníku
• Konference: Mathematical Foundation of Computer Science 2000, 25th International Symposium
• Fakulta / Pracoviště MU: Přírodovědecká fakulta
• Obor: Obecná matematika
• Popis: 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.

Související projekty

• Nekonečně stavové souběžné systémy - modely a verifikace
• Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů
• Matematické struktury algebry a geometrie