The algebraic theory of Parikh automata
From MaRDI portal
Publication:722218
DOI10.1007/s00224-017-9817-2zbMath1410.68244OpenAlexW2767333777MaRDI QIDQ722218
Pierre McKenzie, Michaël Cadilhac, Andreas Krebs
Publication date: 23 July 2018
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-017-9817-2
Related Items
A positive extension of Eilenberg's variety theorem for non-regular languages, Unboundedness problems for machines with reversal-bounded counters
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Nondeterministic \(NC^1\) computation
- Semigroups, Presburger formulas, and languages
- Characterizing \(\text{TC}^{0}\) in terms of infinite groups
- BOUNDED PARIKH AUTOMATA
- Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages
- Weak Second‐Order Arithmetic and Finite Automata
- Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids
- Kleene, Rabin, and Scott Are Available
- Formal Languages and Groups as Memory
- Finite monoids and the fine structure of NC 1
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- Path Logics for Querying Graphs: Combining Expressiveness and Efficiency
- Affine Parikh automata
- UNAMBIGUOUS CONSTRAINED AUTOMATA
- Bounded Regular Sets
- On Context-Free Languages
- Some closure properties of the family of stochastic languages