|
Title
|
|
|
|
Parikh One-Counter Automata
|
|
|
Author
|
|
|
|
|
|
|
Abstract
|
|
|
|
| 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. |
|
|
|
Language
|
|
|
|
English
|
|
|
Source (journal)
|
|
|
|
LIPIcs : Leibniz International Proceedings in Informatics. - Place of publication unknown
|
|
|
Source (book)
|
|
|
|
48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
|
|
|
Publication
|
|
|
|
Place of publication unknown
:
Leibniz-Zentrum für Informatik
,
2023
|
|
|
ISSN
|
|
|
|
1868-8969
|
|
|
ISBN
|
|
|
|
978-3-95977-292-1
|
|
|
DOI
|
|
|
|
10.4230/LIPICS.MFCS.2023.30
|
|
|
Volume/pages
|
|
|
|
272
(2023)
, p. 30:1-30:15
|
|
|
Full text (Publisher's DOI)
|
|
|
|
|
|
|
Full text (open access)
|
|
|
|
|
|