TY - GEN
T1 - History-Deterministic Parikh Automata
AU - Erlich, Enzo
AU - Guha, Shibashis
AU - Jecker, Ismaël
AU - Lehtinen, Karoliina
AU - Zimmermann, Martin
N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2023/9
Y1 - 2023/9
N2 - Parikh automata extend finite automata by counters that can be tested for membership in a semilinear set, but only at the end of a run. Thereby, they preserve many of the desirable properties of finite automata. Deterministic Parikh automata are strictly weaker than nondeterministic ones, but enjoy better closure and algorithmic properties. This state of affairs motivates the study of intermediate forms of nondeterminism. Here, we investigate history-deterministic Parikh automata, i.e., automata whose nondeterminism can be resolved on the fly. This restricted form of nondeterminism is well-suited for applications which classically call for determinism, e.g., solving games and composition. We show that history-deterministic Parikh automata are strictly more expressive than deterministic ones, incomparable to unambiguous ones, and enjoy almost all of the closure properties of deterministic automata.
AB - Parikh automata extend finite automata by counters that can be tested for membership in a semilinear set, but only at the end of a run. Thereby, they preserve many of the desirable properties of finite automata. Deterministic Parikh automata are strictly weaker than nondeterministic ones, but enjoy better closure and algorithmic properties. This state of affairs motivates the study of intermediate forms of nondeterminism. Here, we investigate history-deterministic Parikh automata, i.e., automata whose nondeterminism can be resolved on the fly. This restricted form of nondeterminism is well-suited for applications which classically call for determinism, e.g., solving games and composition. We show that history-deterministic Parikh automata are strictly more expressive than deterministic ones, incomparable to unambiguous ones, and enjoy almost all of the closure properties of deterministic automata.
KW - History-determinism
KW - Parikh automata
KW - Reversal-bounded Counter Machines
UR - http://www.scopus.com/inward/record.url?scp=85167928574&partnerID=8YFLogxK
UR - https://dblp.org/rec/conf/concur/ErlichGJL023
U2 - 10.4230/LIPICS.CONCUR.2023.31
DO - 10.4230/LIPICS.CONCUR.2023.31
M3 - Article in proceeding
VL - 279
T3 - Leibniz International Proceedings in Informatics
SP - 31:1-31:16
BT - 34th International Conference on Concurrency Theory, CONCUR 2023
A2 - Perez, Guillermo A.
A2 - Raskin, Jean-Francois
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 34th International Conference on Concurrency Theory (CONCUR 2023)
Y2 - 18 September 2023 through 23 September 2023
ER -