The investigation of automata and languages defined over a one letter alphabet shows interesting differences with respect to the case of alphabets with at least two letters. Probably, the oldest example emphasizing one of these differences is the collapse of the classes of regular and context-free languages in the unary case (Ginsburg and Rice, 1962). Many differences have been proved concerning the state costs of the simulations between different variants of unary finite state automata (Chrobak, 1986, Mereghetti and Pighizzini, 2001). We present an overview of these results. Because important connections with fundamental questions in space complexity, we give emphasis to unary two-way automata. Furthermore, we discuss unary versions of other computational models, as probabilistic automata, one-way and two-way pushdown automata, even extended with auxiliary workspace, and multi-head automata.
Investigations on Automata and Languages over a Unary Alphabet / G. Pighizzini. - In: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - ISSN 0129-0541. - 26:7(2015), pp. 827-850.
Investigations on Automata and Languages over a Unary Alphabet
G. Pighizzini
2015
Abstract
The investigation of automata and languages defined over a one letter alphabet shows interesting differences with respect to the case of alphabets with at least two letters. Probably, the oldest example emphasizing one of these differences is the collapse of the classes of regular and context-free languages in the unary case (Ginsburg and Rice, 1962). Many differences have been proved concerning the state costs of the simulations between different variants of unary finite state automata (Chrobak, 1986, Mereghetti and Pighizzini, 2001). We present an overview of these results. Because important connections with fundamental questions in space complexity, we give emphasis to unary two-way automata. Furthermore, we discuss unary versions of other computational models, as probabilistic automata, one-way and two-way pushdown automata, even extended with auxiliary workspace, and multi-head automata.File | Dimensione | Formato | |
---|---|---|---|
ciaa2014journalRev.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
428.52 kB
Formato
Adobe PDF
|
428.52 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
S012905411540002X.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
299.05 kB
Formato
Adobe PDF
|
299.05 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.