History-deterministic Parikh automata

DOI10.1145/3742431MaRDI QIDQ6939161zbMATH OpenFDO

Authors Enzo Erlich, Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen, Martin Zimmermann

Publication date 22 August 2025

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NoDerivs 4.0 International

Full work available at URL https://doi.org/10.1145/3742431

zbMATH Keywords

history-determinismParikh automata

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites work

• A bit of nondeterminism makes pushdown automata expressive and succinct
• A pattern logic for automata with outputs
• Affine Parikh automata
• Automata, logics, and infinite games. A guide to current research
• Bounded Algol-Like Languages
• Büchi Good-for-Games Automata Are Efficiently Recognizable
• Decidability results on the existence of lookahead delegators for NFA
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Extended finite automata over groups
• Finite automata over free groups
• History-deterministic Parikh automata
• History-deterministic timed automata
• scientific article; zbMATH DE number 1688359 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 2038747 (Why is no real title available?)
• scientific article; zbMATH DE number 7471692 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• scientific article; zbMATH DE number 7799616 (Why is no real title available?)
• More about Exact Slow $k$-Nim
• Nondeterminism in the presence of a diverse or unknown future
• On a class of languages with holonomic generating functions
• On Context-Free Languages
• On Determinisation of Good-for-Games Automata
• Parikh automata over Infinite words
• Path logics for querying graphs: combining expressiveness and efficiency
• Regular separability of Parikh automata
• Remarks on Parikh-recognizable omega-languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Reversal-bounded multipushdown machines
• Semigroups, Presburger formulas, and languages
• Solving Games Without Determinization
• The Theory of Stabilisation Monoids and Regular Cost Functions
• Token games and history-deterministic quantitative automata
• Two-Way Parikh Automata
• Two-way Parikh automata with a visibly pushdown stack
• Unambiguous constrained automata
• Weakly-unambiguous Parikh automata and their link to holonomic series

This page was built for publication: History-deterministic Parikh automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6939161)