Reidenbach_Schmid_CIAA_2012_final_version.pdf (284.91 kB)
Download file

Automata with modulo counters and nondeterministic counter bounds

Download (284.91 kB)
conference contribution
posted on 19.09.2012, 08:19 by Daniel ReidenbachDaniel Reidenbach, Markus L. Schmid
We introduce and investigate Nondeterministically Bounded Modulo Counter Automata (NBMCA), which are two-way one-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.

History

School

  • Science

Department

  • Computer Science

Citation

REIDENBACH, D. and SCHMID, M.L., 2012. Automata with modulo counters and nondeterministic counter bounds. IN: Moreira, N. and Reis, R. (eds.). Proceedings, 17th International Conference, CIAA 2012, Porto, Portugal, July 17-20, 2012. Lecture Notes in Computer Science: Implementation and Application of Automata, 7381, pp.361-368.

Publisher

© Springer

Version

AM (Accepted Manuscript)

Publication date

2012

Notes

This is a conference paper. It was published in the Lecture Notes of Computer Science series [© Springer-Verlag]: www.springerlink.com.

ISBN

9783642316050

ISSN

0302-9743

Book series

Lecture Notes in Computer Science;7381

Language

en