The algebraic theory of Parikh automata

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

zbMATH Keywords

automatacircuitsmonoidssemilinear setstyped monoids

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70)

Related Items

A positive extension of Eilenberg's variety theorem for non-regular languages, Unboundedness problems for machines with reversal-bounded counters

Uses Software

• MathOverflow

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 ¹
• 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