Directable nondeterministic automata

Imreh Balázs; Steinby Magnus: Directable nondeterministic automata. In: Acta cybernetica, (14) 1. pp. 105-115. (1999)

Előnézet

Cikk, tanulmány, mű cybernetica_014_numb_001_105-115.pdf Letöltés (808kB) | Előnézet

Absztrakt (kivonat)

An automaton is directable if it has a directing word which takes it from every state to the same state. For nondeterministic (n.d.) automata directability can be defined in several meaningful ways. We consider three such notions. An input word w of an n.d. automaton A is (1) Dl-directing if the set of states aw in which A may be after reading w consists of the same single state c for all initial states a; (2) D2-directing if the set aw is independent of the initial state a; (3) D3-directing if some state c appears in all of the sets aw. We consider the sets of D1-, D2- and D3-directing words of a given n.d. automaton, and compare the classes of D1-, D2- and D3-directable n.d. automata with each other. We also estimate the lengths of the longest possible minimum-length D1-, D2- and D3-directing words of an n-state n.d. automaton. All questions are studied separately for n.d. automata which have at least one next state for every input-state pair.

Mű típusa:	Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe:	Acta cybernetica
Dátum:	1999
Kötet:	14
Szám:	1
ISSN:	0324-721X
Oldalak:	pp. 105-115
Nyelv:	angol
Kiadás helye:	Szeged
Befoglaló mű URL:	http://acta.bibl.u-szeged.hu/38507/
Kulcsszavak:	Számítástechnika, Kibernetika, Automaták
Megjegyzések:	Bibliogr.: 115. p. ; ö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:26
Utolsó módosítás:	2022. jún. 14. 09:11
URI:	http://acta.bibl.u-szeged.hu/id/eprint/12613

Bővebben:

Tétel nézet