It is well known that the class of regular languages coincides with the class of languages recognized by finite automata. Nevertheless, many other characterizations of this class in terms of computational devices and generative models are present in the literature. For example, by suitably restricting more powerful models such as context-free grammars, pushdown automata, and Turing machines, it is possible to obtain formal models that generate or recognize regular languages only. These restricted formalisms provide alternative representations of regular languages that may be significantly more concise than other models that share the same expressive power. The goal of this work is to provide an overview of old and recent results on these formal systems from a descriptional complexity perspective, that is by considering the relationships between the sizes of such devices. We also present some results related to the investigation of the famous question posed by Sakoda and Sipser in 1978, concerning the size blowups from nondeterministic finite automata to two-way deterministic finite automata.

Regular Languages: To Finite Automata and Beyond Succinct : Descriptions and Optimal Simulations / L. Prigioniero - In: 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2021, July 12-14, 2021, Aix-Marseille University, France[s.l] : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. - pp. 1-16 (( convegno AUTOMATA nel 2021 [10.4230/oasics.automata.2021.2].

Regular Languages: To Finite Automata and Beyond Succinct : Descriptions and Optimal Simulations

L. Prigioniero
2021

Abstract

It is well known that the class of regular languages coincides with the class of languages recognized by finite automata. Nevertheless, many other characterizations of this class in terms of computational devices and generative models are present in the literature. For example, by suitably restricting more powerful models such as context-free grammars, pushdown automata, and Turing machines, it is possible to obtain formal models that generate or recognize regular languages only. These restricted formalisms provide alternative representations of regular languages that may be significantly more concise than other models that share the same expressive power. The goal of this work is to provide an overview of old and recent results on these formal systems from a descriptional complexity perspective, that is by considering the relationships between the sizes of such devices. We also present some results related to the investigation of the famous question posed by Sakoda and Sipser in 1978, concerning the size blowups from nondeterministic finite automata to two-way deterministic finite automata.
Regular languages; descriptional complexity; finite automata
Settore INF/01 - Informatica
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
OASIcs-AUTOMATA-2021-2.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 678.82 kB
Formato Adobe PDF
678.82 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/862333
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact