Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR13-040 | 20th January 2017 17:45

The Algebraic Theory of Parikh Automata

RSS-Feed




Revision #2
Authors: Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
Accepted on: 20th January 2017 17:45
Downloads: 721
Keywords: 


Abstract:

The Parikh automaton model equips a finite automaton with integer registers
and imposes a semilinear constraint on the set of their final settings.
Here the theories of typed monoids and of rational series are used to
characterize the language classes that arise algebraically. Complexity
bounds are derived, such as containment of the unambiguous Parikh automata
languages in NC$^1$. Affine Parikh automata, where each transition applies
an affine transformation on the registers, are also considered. Relying on
these characterizations, the landscape of relationships and closure
properties of the classes at hand is completed, in particular over unary
languages.



Changes to previous version:

Brush up, a few more results.


Revision #1 to TR13-040 | 22nd January 2016 07:55

The Algebraic Theory of Parikh Automata





Revision #1
Authors: Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
Accepted on: 22nd January 2016 07:55
Downloads: 797
Keywords: 


Abstract:

The Parikh automaton model equips a finite automaton with integer registers
and imposes a semilinear constraint on the set of their final settings.
Here the theories of typed monoids and of rational series are used to
characterize the language classes that arise algebraically. Complexity
bounds are derived, such as containment of the unambiguous Parikh automata
languages in NC$^1$. Affine Parikh automata, where each transition applies
an affine transformation on the registers, are also considered. Relying on
these characterizations, the landscape of relationships and closure
properties of the classes at hand is completed, in particular over unary
languages.



Changes to previous version:

Long version, including new results.


Paper:

TR13-040 | 11th March 2013 18:40

The Algebraic Theory of Parikh Automata





TR13-040
Authors: Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
Publication: 24th March 2013 07:39
Downloads: 3290
Keywords: 


Abstract:

The Parikh automaton model equips a finite automaton with integer registers and imposes a semilinear constraint on the set of their final settings. Here the theory of typed monoids is used to characterize the language classes that arise algebraically. Complexity bounds are derived, such as containment of the unambiguous Parikh automata languages in NC$^1$. Noting that DetAPA languages are positive supports of rational $\mathbb{Z}$-series, DetAPA are further shown stronger than Parikh automata on unary langages. This suggests unary DetAPA languages as candidates for separating the two better known variants of uniform NC$^1$.



ISSN 1433-8092 | Imprint