2026-08-11T21:31:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18564 2024-03-06T11:02:08Z ddc:004 open_access

Parikh One-Counter Automata Cadilhac, Michaël Ghosh, Arka Pérez, Guillermo A. Raha, Ritam Parikh automata Context-free languages One-counter automata Counting abilities in finite automata are traditionally provided by two orthogonal extensions: adding a single counter that can be tested for zeroness at any point, or adding ℤ-valued counters that are tested for equality only at the end of runs. In this paper, finite automata extended with both types of counters are introduced. They are called Parikh One-Counter Automata (POCA): the "Parikh" part referring to the evaluation of counters at the end of runs, and the "One-Counter" part to the single counter that can be tested during runs. Their expressiveness, in the deterministic and nondeterministic variants, is investigated; it is shown in particular that there are deterministic POCA languages that cannot be expressed without nondeterminism in the original models. The natural decision problems are also studied; strikingly, most of them are no harder than in the original models. A parametric version of nonemptiness is also considered. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michaël Cadilhac and Arka Ghosh and Guillermo A. Pérez and Ritam Raha 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.30 urn:nbn:de:0030-drops-185645 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.30 eng https://creativecommons.org/licenses/by/4.0/legalcode