DROPS

Document

DOI: 10.4230/OASIcs.TIME.2026.3

The Σ-Chain Product: A Succinct Model of Automata (De)Composition

Authors: Roberto Borelli, Davide Bresolin, Luca Geatti, Angelo Montanari, and Matteo Zavatteri

Published in: OASIcs, Volume 146, 33rd International Symposium on Temporal Representation and Reasoning (TIME 2026)

Abstract

The cascade product is a fundamental construction in automata theory, enabling hierarchical composition of automata and playing a central role in decomposition results such as the Krohn–Rhodes theorem. However, its use is limited by the exponential size required to represent cascades, which stems from the fact that each component may depend on all preceding ones, leading to exponentially large alphabets. To address this issue, we introduce the Σ-chain product, a restricted variant in which each component depends only on the input alphabet and the component immediately preceding it. We show that Σ-chains achieve linear-size representations and can be exponentially more succinct than cascades. We prove that Σ-chains and cascades are expressively equivalent even when restricting the components to specific classes of automata, such as permutation-reset automata. As a consequence, we derive that a language is regular if and only if it is recognized by a Σ-chain of permutation-reset automata. Finally, we analyze structural properties of Σ-chains of reset automata, including a relation with well-known subclasses of star-free languages.

Cite as

Roberto Borelli, Davide Bresolin, Luca Geatti, Angelo Montanari, and Matteo Zavatteri. The Σ-Chain Product: A Succinct Model of Automata (De)Composition. In 33rd International Symposium on Temporal Representation and Reasoning (TIME 2026). Open Access Series in Informatics (OASIcs), Volume 146, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{borelli_et_al:OASIcs.TIME.2026.3,
  author =	{Borelli, Roberto and Bresolin, Davide and Geatti, Luca and Montanari, Angelo and Zavatteri, Matteo},
  title =	{{The \Sigma-Chain Product: A Succinct Model of Automata (De)Composition}},
  booktitle =	{33rd International Symposium on Temporal Representation and Reasoning (TIME 2026)},
  pages =	{3:1--3:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-448-2},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{146},
  editor =	{Orlandini, AndreA and Pinchinat, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.TIME.2026.3},
  URN =		{urn:nbn:de:0030-drops-276999},
  doi =		{10.4230/OASIcs.TIME.2026.3},
  annote =	{Keywords: Automata, Cascade Product, Formal Languages, Krohn-Rhodes Theory}
}

Document

DOI: 10.4230/LIPIcs.STACS.2025.20

On Cascades of Reset Automata

Authors: Roberto Borelli, Luca Geatti, Marco Montali, and Angelo Montanari

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract

The Krohn-Rhodes decomposition theorem is a pivotal result in automata theory. It introduces the concept of cascade product, where two semiautomata, that is, automata devoid of initial and final states, are combined in a feed-forward fashion. The theorem states that any semiautomaton can be decomposed into a sequence of permutation-reset semiautomata. For the counter-free case, this decomposition consists entirely of reset components with two states each. This decomposition has significantly impacted recent research in various areas of computer science, including the identification of a class of transformer encoders equivalent to star-free languages and the conversion of Linear Temporal Logic formulas into past-only expressions (pastification). The paper revisits the cascade product in the context of reset automata, thus considering each component of the cascade as a language acceptor. First, we give regular expression counterparts of cascades of reset automata. We then establish several expressiveness results, identifying hierarchies of languages based on the restriction of the height (number of components) of the cascade or of the number of states in each level. We also show that any cascade of reset automata can be transformed, with a quadratic increase in height, into a cascade that only includes two-state components. Finally, we show that some fundamental operations on cascades, like intersection, union, negation, and concatenation with a symbol to the left, can be directly and efficiently computed by adding a two-state component.

Cite as

Roberto Borelli, Luca Geatti, Marco Montali, and Angelo Montanari. On Cascades of Reset Automata. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{borelli_et_al:LIPIcs.STACS.2025.20,
  author =	{Borelli, Roberto and Geatti, Luca and Montali, Marco and Montanari, Angelo},
  title =	{{On Cascades of Reset Automata}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{20:1--20:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.20},
  URN =		{urn:nbn:de:0030-drops-228453},
  doi =		{10.4230/LIPIcs.STACS.2025.20},
  annote =	{Keywords: Automata, Cascade products, Regular expressions, Krohn-Rhodes theory}
}

Search Results

Documents authored by Borelli, Roberto

The Σ-Chain Product: A Succinct Model of Automata (De)Composition

Abstract

Cite as

On Cascades of Reset Automata

Abstract

Cite as

Thanks for your feedback!

Could not send message