Issue |
RAIRO-Theor. Inf. Appl.
Volume 46, Number 4, October-December 2012
Special Issue: Non-Classical Models of Automata and Applications III (NCMA-2011)
|
|
---|---|---|
Page(s) | 511 - 545 | |
DOI | https://doi.org/10.1051/ita/2012013 | |
Published online | 02 August 2012 |
Affine Parikh automata∗
1
DIRO, Université de Montréal, CP 6128
succ. centre-ville, Montréal
QC, H3C 3J7, Canada
cadilhac@iro.umontreal.ca, mckenzie@iro.umontreal.ca.
The third author is supported by the Natural Sciences and Engineering Research
Council of Canada.
2
LSV, ENS Cachan, CNRS, 61, avenue du Président Wilson, 94235
Cachan Cedex,
France
finkel@lsv.ens-cachan.fr
Ce travail a bénéficié d’une aide de l’Agence Nationale de la Recherche portant
la référence “REACHARD-ANR-11-BS02-001”
Received:
4
November
2011
Accepted:
30
April
2012
The Parikh finite word automaton (PA) was introduced and studied in 2003 by Klaedtke and Rueß. 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, that extends the PA by having each transition induce an affine transformation on the PA registers, and the PA on letters, that restricts the PA by forcing any two transitions on the 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.
Mathematics Subject Classification: 68Q45
Key words: Automata / semilinear sets / affine functions / counter machines
© EDP Sciences 2012
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.