1 Search Results for "Prigioniero, Luca"

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-dev.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}
}
  • Refine by Author
  • 1 Prigioniero, Luca

  • Refine by Classification
  • 1 Theory of computation → Models of computation
  • 1 Theory of computation → Regular languages

  • Refine by Keyword
  • 1 Regular languages
  • 1 descriptional complexity
  • 1 finite automata

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact