2134/13438
Daniel Reidenbach
Daniel
Reidenbach
Markus L. Schmid
Markus L.
Schmid
Automata with Modulo Counters and Nondeterministic Counter Bounds
Loughborough University
2013
untagged
Statistics
Information and Computing Sciences not elsewhere classified
2013-10-28 10:20:11
Preprint
https://repository.lboro.ac.uk/articles/preprint/Automata_with_Modulo_Counters_and_Nondeterministic_Counter_Bounds/9403475
We introduce and investigate Nondeterministically Bounded Modulo Counter
Automata (NBMCA), which are two-way multi-head automata that comprise a
constant number of modulo counters, where the counter bounds are nondeterministically
guessed, and this is the only element of nondeterminism. NBMCA are
tailored to recognising those languages that are characterised by the existence of
a specific factorisation of their words, e. g., pattern languages. In this work, we
subject NBMCA to a theoretically sound analysis.