DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2026.16

Decomposition of Automata Recognizing Ideals

Authors: Mathias Berry, Pierre-Cyrille Héam, and Ismaël Jecker

Published in: LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026)

Abstract

Minimizing the size of finite automata is a fundamental problem in theoretical computer science. Beyond standard minimization, further reductions can be achieved by decomposing an automaton into smaller components whose languages combine via intersection or union to recover the original language. However, in general, no polynomial-time algorithm is known for computing such decompositions. In this paper, we focus on automata that recognize ideals, that is, languages at level 1/2 in the Straubing–Thérien hierarchy. Equivalently, these languages are expressible as a finite union of languages of the form Σ^*a₁Σ^*… Σ^*a_nΣ^* where Σ is an alphabet and a_i are letters of Σ. We show that the two problems of deciding whether an automata recognizing an ideal can be decomposed into an intersection or a union of smaller automata are decidable in NL. Moreover, we provide a polynomial-time algorithm that computes a decomposition into an intersection, if one exists, while ensuring that the resulting components also recognize ideal languages.

Cite as

Mathias Berry, Pierre-Cyrille Héam, and Ismaël Jecker. Decomposition of Automata Recognizing Ideals. In 37th International Conference on Concurrency Theory (CONCUR 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 391, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{berry_et_al:LIPIcs.CONCUR.2026.16,
  author =	{Berry, Mathias and H\'{e}am, Pierre-Cyrille and Jecker, Isma\"{e}l},
  title =	{{Decomposition of Automata Recognizing Ideals}},
  booktitle =	{37th International Conference on Concurrency Theory (CONCUR 2026)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-447-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{391},
  editor =	{Sokolova, Ana and Totzke, Patrick},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.16},
  URN =		{urn:nbn:de:0030-drops-273473},
  doi =		{10.4230/LIPIcs.CONCUR.2026.16},
  annote =	{Keywords: Finite state automata, decomposition, Shuffle ideals}
}

Search Results

Documents authored by Berry, Mathias

Decomposition of Automata Recognizing Ideals

Abstract

Cite as

Thanks for your feedback!

Could not send message