On the k-reversibility of finite automata

Falucskai, János (2009) On the k-reversibility of finite automata Annales Mathematicae et Informaticae. 36. pp. 71-75. ISSN 1787-5021 (Print), 1787-6117 (Online)

[thumbnail of AMI_36_from71to75.pdf] pdf
AMI_36_from71to75.pdf

Download (115kB) [error in script]

Absztrakt (kivonat)

It is a famous result of Angluin (1982 [1]) that there exists a time poly- nomial and space linear algorithm to identify the canonical automata of kreversible languages by using characteristic sample sets. This result has several applications. In this paper we characterise the class of all automata for which her method is not applicable. In particular, the aim of this paper is to characterise the family of finite automata which are not k-reversible for any non-negative integer k.

Mű típusa: Folyóiratcikk - Journal article
Szerző:
Szerző neve
Email
MTMT azonosító
ORCID azonosító
Közreműködés
Falucskai, János
NEM RÉSZLETEZETT
NEM RÉSZLETEZETT
NEM RÉSZLETEZETT
Szerző
Kapcsolódó URL-ek:
Kulcsszavak: finite automata, k-reversible automata
Nyelv: angol
Kötetszám: 36.
ISSN: 1787-5021 (Print), 1787-6117 (Online)
Felhasználó: Tibor Gál
Dátum: 05 Már 2019 16:55
Utolsó módosítás: 05 Már 2019 16:55
URI: http://publikacio.uni-eszterhazy.hu/id/eprint/3119
Műveletek (bejelentkezés szükséges)
Tétel nézet Tétel nézet