Parikh one-counter automata

Michaël Cadilhac, Arka Ghosh, Guillermo A. Pérez, Ritam Raha

TL;DR

This paper introduces Parikh One-Counter Automata (POCA), a novel computational model that combines two existing ways of extending finite automata with counting capabilities: a single counter testable during a run and multiple counters testable only at the end. They demonstrate that this combination leads to surprisingly richer expressiveness, even in deterministic variants, and analyze the decidability of key problems, finding many to be no harder than for the simpler models.

What Problem Does This Paper Address?

Formal verification often relies on computational models that can express complex system behaviors while still allowing for decidable analysis of critical properties like "does this system ever enter a bad state?". Finite automata, while simple, are not expressive enough for many real-world systems. Researchers have extended them with counters to increase their power. Two prominent extensions are:

  1. One-Counter Automata (OCA): These add a single counter that can be incremented or decremented, with the ability to test if it's zero at any point during a run. This is useful for languages like $\{a^n b^n \mid n \ge 0\}^*$.
  2. Parikh Automata (PA): These add multiple counters, but they can only be checked for specific values (often equality to a target or satisfying a Presburger formula) at the very end of a computation. This is useful for languages like $\{a^n b^n c^n \mid n \ge 0\}$.

The problem addressed here is that these two extensions are orthogonal; a language expressible by one might not be by the other. The authors ask: what happens when we combine both types of counting mechanisms into a single model? Does this new model, the Parikh One-Counter Automaton (POCA), offer a more powerful and useful framework for modeling and verification? Specifically, they investigate its expressiveness and the decidability of its associated decision problems.

Methods

The core of the paper is the formal definition and analysis of Parikh One-Counter Automata (POCA). A POCA is essentially a finite automaton equipped with:

  • A single counter: This counter can be tested for zero-ness during the run (like in OCAs).
  • Multiple Z-valued counters: These are checked only at the end of a run using a Presburger formula (like in PAs).

The authors introduce a "depumping lemma" (Lemma 4) which is crucial for proving limitations of POCA's expressiveness. This lemma is a generalization of pumping lemmas for context-free languages and helps to show that certain languages cannot be recognized by POCA.

They then systematically study the relationships between POCA and its base models (PA and OCA), both in their deterministic and nondeterministic variants. This involves constructing examples of languages that highlight the unique expressive power of POCA.

Finally, they analyze the complexity of standard decision problems like nonemptiness, universality, and inclusion for POCA and its deterministic variant (DetPOCA). They also explore parametric versions of these problems, where counter updates or constraints involve variables.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Synergy of Counting Mechanisms: The most striking insight is that combining the two counting mechanisms (one-counter testable during runs, multi-counter testable at the end) creates a model (POCA) that is strictly more expressive than either of its components, even in its deterministic variant (DetPOCA). This means DetPOCA can recognize languages that neither DetOCA nor DetPA can.
  • Deterministic Power-Up: A key finding is that POCA can sometimes be deterministic for languages that require nondeterminism in either OCA or PA alone. This is significant for formal verification, as deterministic models often have decidable properties that are undecidable for their nondeterministic counterparts.
  • Decidability Preservation: Despite the increased expressiveness, many fundamental decision problems (like nonemptiness) for POCA remain surprisingly decidable and often have the same complexity as for the simpler PA model (coNP-complete). This suggests POCA might be a practical model for verification.
  • Parametric Undecidability: The paper highlights that a parametric version of the nonemptiness problem for POCA (where counter updates involve variables) is undecidable. This is an unfortunate result, as it limits the direct application of POCA to certain types of parametric system verification.

Key Results

  • Expressiveness Hierarchy: The paper establishes strict inclusions: DetPA $\subsetneq$ DetPOCA and DetOCA $\subsetneq$ DetPOCA. It also shows PA $\subsetneq$ POCA and OCA $\subsetneq$ POCA. The expressive power of DetPOCA is incomparable with PA and OCA.
  • Decidability of Core Problems:
    • Nonemptiness for both DetPOCA and POCA is NP-complete.
  • Universality for DetPOCA is coNP-complete.
  • Inclusion of a POCA in a regular language is coNP-complete.
  • Inclusion of a DetPOCA in a regular language is undecidable.
  • Closure Properties: DetPOCA is closed under complement, inverse morphisms, and intersection/union with regular languages. POCA is closed under union, concatenation, morphisms, inverse morphisms, and intersection with regular languages. However, DetPOCA is not closed under union, intersection, concatenation with regular languages, or morphisms.
  • Parametric Undecidability: The parametric universal nonemptiness problem for POCA with parametric updates is undecidable.

Limitations and Future Work

  • Parametric Undecidability: The undecidability of the parametric nonemptiness problem for POCA with parametric updates is a significant limitation, especially given its potential connection to formal verification of systems with variable parameters. The authors note that this contrasts with decidability results for certain fragments of Presburger arithmetic.
  • Open Questions:
    • The decidability of equivalence for DetPOCA remains an open question, though the authors conjecture it is decidable.
  • They pose a question about whether languages of the form $(L\#)^*$ recognized by POCA imply that $L$ can be recognized by an OCA, suggesting that the semilinear constraint might not be meaningfully used in such cases.
  • Future Work: The paper suggests exploring the connection between parametric POCA and formalisms like Presburger arithmetic with divisibility, aiming to find decidable fragments or alternative correspondences. Further investigation into the expressiveness lemmas and their application to other models is also implied.

Summary updated

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 Z-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.
BibTeX
@inproceedings{cadilhac2025parikh,
  author = {Michaël Cadilhac and Arka Ghosh and Guillermo A. Pérez and Ritam Raha},
  title = {{Parikh one-counter automata}},
  booktitle = {Inf. Comput},
  year = {2025},
  url = {https://openreview.net/forum?id=ATvrfCxmre},
}
Figure