Advertisement
Published in:
2014 | OriginalPaper | Chapter
Investigations on Automata and Languages over a Unary Alphabet
Author : Giovanni Pighizzini
Published in: Implementation and Application of Automata
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 those 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 one-way and two-way pushdown automata, even extended with auxiliary workspace, and multi-head automata.