DROPS

Document

Invited Talk

DOI: 10.4230/OASIcs.AUTOMATA.2021.2

Regular Languages: To Finite Automata and Beyond (Invited Talk)

Authors: Luca Prigioniero

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 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.

Cite as

Luca Prigioniero. Regular Languages: To Finite Automata and Beyond (Invited Talk). In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{prigioniero:OASIcs.AUTOMATA.2021.2,
  author =	{Prigioniero, Luca},
  title =	{{Regular Languages: To Finite Automata and Beyond}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{2:1--2:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.2},
  URN =		{urn:nbn:de:0030-drops-140115},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.2},
  annote =	{Keywords: Regular languages, descriptional complexity, finite automata}
}

Search Results

Documents authored by Prigioniero, Luca

Regular Languages: To Finite Automata and Beyond (Invited Talk)

Abstract

Cite as

Thanks for your feedback!

Could not send message