Complexity of problems concerning reset words for some partial cases of automata

Martyugin Pavel: Complexity of problems concerning reset words for some partial cases of automata. In: Acta cybernetica, (19) 2. pp. 517-536. (2009)

Előnézet

Cikk, tanulmány, mű Martyugin_2009_ActaCybernetica.pdf Letöltés (176kB) | Előnézet

Absztrakt (kivonat)

A word w is called a reset word for a deterministic finite automaton A if it maps all states of A to one state. A word w is called a compressing to M states for a deterministic finite automaton A if it maps all states of A to at most M states. We consider several subclasses of automata: aperiodic, D-trivial, monotonic, partially monotonic automata and automata with a zero state. For these subclasses we study the computational complexity of the following problems. Does there exist a reset word for a given automaton? Does there exist a reset word of given length for a given automaton? What is the length of the shortest reset word for a given automaton? Moreover, we consider complexity of the same problems for compressing words.

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. 517-536
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. 535-536. ; ö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. 09:55
URI:	http://acta.bibl.u-szeged.hu/id/eprint/12877

Bővebben:

Tétel nézet