2011/01/07 by Michaël Cadilhac, Cadilhac, Michaël, Alain Finkel +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Algebra and Logic #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1101.1547
openalex publication_date 2011/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Parikh finite word automaton (PA) was introduced and studied by Klaedtke and Ruess in 2003. Natural variants of the PA arise from viewing a PA equivalently as an automaton that keeps a count of its transitions and semilinearly constrains their numbers. Here we adopt this view and define the affine PA (APA), that extends the PA by having each transition induce an affine transformation on the PA registers, and the PA on letters (LPA), that restricts the PA by forcing any two transitions on same letter to affect the registers equally. Then we report on the expressiveness, closure, and decidability properties of such PA variants. We note that deterministic PA are strictly weaker than deterministic reversal-bounded counter machines. We develop pumping-style lemmas and identify an explicit PA language recognized by no deterministic PA.