On directable nondeterministic trapped automata

Imreh Balázs; Imreh Csanád; Ito Masami: On directable nondeterministic trapped automata. In: Acta cybernetica, (16) 1. pp. 37-45. (2003)

Előnézet

Cikk, tanulmány, mű cybernetica_016_numb_001_037-045.pdf Letöltés (872kB) | Előnézet

Absztrakt (kivonat)

A finite automaton is said to be directable if it has an input word, a directing word, which takes it from every state into the same state. For nondeterministic (n.d.) automata, directability can be generalized in several ways. In [8], three such notions, D1-, D2-, and D3-directability, are introduced. In this paper, we introduce the trapped n.d. automata, and for each i = 1,2,3, present lower and upper bounds for the lengths of the shortest Di-directing words of n-state Di-directable trapped n.d. automata. It turns out that for this special class of n.d. automata, better bounds can be found than for the general case, and some of the obtained bounds are sharp.

Mű típusa:	Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe:	Acta cybernetica
Dátum:	2003
Kötet:	16
Szám:	1
ISSN:	0324-721X
Oldalak:	pp. 37-45
Nyelv:	angol
Kiadás helye:	Szeged
Konferencia neve:	Conference for PhD Students in Computer Science (3.) (2002) (Szeged)
Befoglaló mű URL:	http://acta.bibl.u-szeged.hu/38515/
Kulcsszavak:	Számítástechnika, Kibernetika
Megjegyzések:	Bibliogr.: p. 44-45. ; ö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. 14. 15:38
URI:	http://acta.bibl.u-szeged.hu/id/eprint/12707

Bővebben:

Tétel nézet