Breveglieri Luca; Cherubini A.; Nuccio C.; Rodaro E.: Alphabetical satisfiability problem for trace equations. In: Acta cybernetica, (19) 2. pp. 479-497. (2009)
Előnézet |
Cikk, tanulmány, mű
Breveglieri_2009_ActaCybernetica.pdf Letöltés (184kB) | Előnézet |
Absztrakt (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.
| Mű típusa: | Cikk, tanulmány, mű |
|---|---|
| Befoglaló folyóirat/kiadvány címe: | Acta cybernetica |
| Dátum: | 2009 |
| Kötet: | 19 |
| Szám: | 2 |
| ISSN: | 0324-721X |
| Oldalak: | pp. 479-497 |
| Nyelv: | angol |
| Kiadás helye: | Szeged |
| Konferencia neve: | International Conference on Automata and Formal Languages (12.) (2008) (Szeged) |
| Befoglaló mű URL: | http://acta.bibl.u-szeged.hu/38528/ |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Megjegyzések: | Bibliogr.: p. 496-497. ; összefoglalás angol nyelven |
| Szakterület: | 01. Természettudományok 01. Természettudományok > 01.02. Számítás- és információtudomány |
| Feltöltés dátuma: | 2016. okt. 15. 12:25 |
| Utolsó módosítás: | 2022. jún. 17. 08:15 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/12875 |
 |
Tétel nézet |
