Alphabetical satisfiability problem for trace equations

It is known that the satisfiability problem for equations over free partially commutative monoids is decidable but computationally hard. In this paper we consider the satisfiability problem for equations over free partially commutative monoids under the constraint that the solution is a subset of th...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerzők: Breveglieri Luca
Cherubini A.
Nuccio C.
Rodaro E.
Testületi szerző: International Conference on Automata and Formal Languages (12.) (2008) (Szeged)
Dokumentumtípus: Cikk
Megjelent: 2009
Sorozat:Acta cybernetica 19 No. 2
Kulcsszavak:Számítástechnika, Kibernetika
Tárgyszavak:
Online Access:http://acta.bibl.u-szeged.hu/12875
Leíró adatok
Tartalmi kivonat:It is known that the satisfiability problem for equations over free partially commutative monoids is decidable but computationally hard. In this paper we consider the satisfiability problem for equations over free partially commutative monoids under the constraint that the solution is a subset of the alphabet. We prove that this problem is NP-complete for quadratic equations and that its uniform version is NP-complete for linear equations.
Terjedelem/Fizikai jellemzők:479-497
ISSN:0324-721X