Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PARIKH AUTOMATA:
Reports tagged with Parikh automata:
TR13-040 | 11th March 2013
Michaƫl Cadilhac, Andreas Krebs, Pierre McKenzie

The Algebraic Theory of Parikh Automata

Revisions: 2

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 ... more >>>




ISSN 1433-8092 | Imprint