Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-01-07
Computer Science
Formal Languages and Automata Theory
16 pages, in NCMA11
Scientific paper
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.
Cadilhac Michaël
Finkel Alain
McKenzie Pierre
No associations
LandOfFree
On the expressiveness of Parikh automata and related models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the expressiveness of Parikh automata and related models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the expressiveness of Parikh automata and related models will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-8469