Some remarks on directable automata

Imreh Balázs; Steinby Magnus: Some remarks on directable automata. In: Acta cybernetica, (12) 1. pp. 23-35. (1995)

Előnézet

Cikk, tanulmány, mű cybernetica_012_numb_001_023-035.pdf Letöltés (729kB) | Előnézet

Absztrakt (kivonat)

A finite automaton is said to be directable if there exists a word, a directing word, which takes the automaton from every state to the same state. After some general remarks on directable automata and their directing words we present methods for testing the directability of an automaton and for finding the least congruence of an automaton which yields a directable quotient automaton. A well-known conjecture by J. Cera? claims that any n-state directable automaton has a directing word of length <(n-x)5, but the best known upper bounds are of the order 0(re*). However, for special classes of automata lower bounds can be given. We consider a generalized form of Cern?'s conjecture proposed by J.-E. Pin for the classes of commutative, definite, reverse definite, generalized definite and nilpotent automata. We also establish the inclusion relationships between these classes within the class of directable automata.

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

Bővebben:

Tétel nézet