Breveglieri Luca and Cherubini A. and Nuccio C. and Rodaro E.: Alphabetical satisfiability problem for trace equations. In: Acta cybernetica, (19) 2. pp. 479-497. (2009)
Preview |
Cikk, tanulmány, mű
Breveglieri_2009_ActaCybernetica.pdf Download (184kB) | Preview |
Abstract
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.
Item Type: | Article |
---|---|
Journal or Publication Title: | Acta cybernetica |
Date: | 2009 |
Volume: | 19 |
Number: | 2 |
ISSN: | 0324-721X |
Page Range: | pp. 479-497 |
Language: | English |
Place of Publication: | Szeged |
Event Title: | International Conference on Automata and Formal Languages (12.) (2008) (Szeged) |
Related URLs: | http://acta.bibl.u-szeged.hu/38528/ |
Uncontrolled Keywords: | Számítástechnika, Kibernetika |
Additional Information: | Bibliogr.: p. 496-497. ; összefoglalás angol nyelven |
Subjects: | 01. Natural sciences 01. Natural sciences > 01.02. Computer and information sciences |
Date Deposited: | 2016. Oct. 15. 12:25 |
Last Modified: | 2022. Jun. 17. 08:15 |
URI: | http://acta.bibl.u-szeged.hu/id/eprint/12875 |
Actions (login required)
![]() |
View Item |