License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.AUTOMATA.2021.2
URN: urn:nbn:de:0030-drops-140115
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14011/
Go to the corresponding OASIcs Volume Portal

Prigioniero, Luca

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

pdf-format:
OASIcs-AUTOMATA-2021-2.pdf (0.7 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2021/14011},
  URN =		{urn:nbn:de:0030-drops-140115},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.2},
  annote =	{Keywords: Regular languages, descriptional complexity, finite automata}
}

Keywords: Regular languages, descriptional complexity, finite automata
Collection: 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)
Issue Date: 2021
Date of publication: 28.06.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI