DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2026.48

Polynomial Complementation of Nondeterministic Two-Way Finite Automata by 1-Limited Automata

Authors: Bruno Guillon, Luca Prigioniero, and Javad Taheri

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

We prove that, paying a polynomial increase in size only, every unrestricted two-way nondeterministic finite automaton (2NFA) can be complemented by a 1-limited automaton (1-LA), a nondeterministic extension of 2NFAs still characterizing regular languages. The resulting machine is actually a restricted form of 1-LAs - known as 2NFAs with common guess - and is self-verifying. A corollary of our construction is that a single exponential is necessary and sufficient for complementing 1-LAs.

Cite as

Bruno Guillon, Luca Prigioniero, and Javad Taheri. Polynomial Complementation of Nondeterministic Two-Way Finite Automata by 1-Limited Automata. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{guillon_et_al:LIPIcs.STACS.2026.48,
  author =	{Guillon, Bruno and Prigioniero, Luca and Taheri, Javad},
  title =	{{Polynomial Complementation of Nondeterministic Two-Way Finite Automata by 1-Limited Automata}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.48},
  URN =		{urn:nbn:de:0030-drops-255378},
  doi =		{10.4230/LIPIcs.STACS.2026.48},
  annote =	{Keywords: descriptional complexity, inductive counting, common-guess}
}

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

Polynomial Complementation of Nondeterministic Two-Way Finite Automata by 1-Limited Automata

Abstract

Cite as

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

Abstract

Cite as

Thanks for your feedback!

Could not send message