Kybernetika 50 no. 1, 66-94, 2014

Automata with modulo counters and nondeterministic counter bounds

Daniel Reidenbach and Markus L. SchmidDOI: 10.14736/kyb-2014-1-0066

Abstract:

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.

Keywords:

multi-head automata, counter automata, modulo counters, stateless automata, restricted nondeterminism

Classification:

68Q45, 68Q05, 68Q10

paper.pdf

References:

  1. J. H. Chang, O. H. Ibarra, M. A. Palis and B. Ravikumar: On pebble automata. Theoret. Comput. Sci. 44 (1986), 111-121.   CrossRef
  2. E. Chiniforooshan, M. Daley, O. H. Ibarra, L. Kari and S. Seki: One-reversal counter machines and multihead automata: Revisited. In: Proc. 37th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011, Lecture Notes in Comput. Sci. 6543 (2011), pp. 166-177.   CrossRef
  3. P. Frisco and O. H. Ibarra: On stateless multihead finite automata and multihead pushdown automata. In: Proc. Developments in Language Theory 2009, Lecture Notes in Comput. Sci. 5583 (2009), pp. 240-251.   CrossRef
  4. M. Harrison: Introduction to Formal Language Theory. Addison-Wesley, Reading 1978.   CrossRef
  5. M. Holzer, M. Kutrib and A. Malcher: Complexity of multi-head finite automata: Origins and directions. Theoret. Comput. Sci. 412 (2011), 83-96.   CrossRef
  6. J. E. Hopcroft and J. D. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading 1979.   CrossRef
  7. O. H. Ibarra: Reversal-bounded multicounter machines and their decision problems. J. Assoc. Comput. Mach. 25 (1978), 116-133.   CrossRef
  8. O. H. Ibarra and Ö. E\u{g}ecio\u{g}lu: Hierarchies and characterizations of stateless multicounter machines. In: Computing and Combinatorics, Lecture Notes in Comput. Sci. 5609 (2009), pp. 408-417.   CrossRef
  9. O. H. Ibarra, J. Karhumäki and A. Okhotin: On stateless multihead automata: Hierarchies and the emptiness problem. Theoret. Comput. Sci. 411 (2010), 581-593.   CrossRef
  10. O. H. Ibarra and B. Ravikumar: On partially blind multihead finite automata. Theoret. Comput. Sci. 356 (2006), 190-199.   CrossRef
  11. M. Kutrib, A. Malcher and M. Wendlandt: One-way multi-head finite automata with pebbles but no states. In: Proc. 17th International Conference on Developments in Language Theory, DLT 2013, Lecture Notes in Comput. Sci. 7907 (2013), pp. 313-324.   CrossRef
  12. M. Kutrib, H. Messerschmidt and F. Otto: On stateless two-pushdown automata and restarting automata. Internat. J. Found. Comput. Sci. 21 (2010), 781-798.   CrossRef
  13. B. Monien: Two-way multihead automata over a one-letter alphabet. RAIRO Inform. Théor. 14 (1980), 67-82.   CrossRef
  14. H. Petersen: Automata with sensing heads. In: Proc. 3rd Israel Symposium on Theory of Computing and Systems 1995, p. 150-157.   CrossRef
  15. D. Reidenbach and M. L. Schmid: A polynomial time match test for large classes of extended regular expressions. In: Proc. 15th International Conference on Implementation and Application of Automata, CIAA 2010, Lecture Notes in Comput. Sci. 6482 (2011), pp. 241-250.   CrossRef
  16. D. Reidenbach and M. L. Schmid: Automata with modulo counters and nondeterministic counter bounds. In: Proc. 17th International Conference on Implementation and Application of Automata, CIAA 2012, Lecture Notes in Comput. Sci. 7381 (2012), pp. 361-368.   CrossRef
  17. D. Reidenbach and M. L. Schmid: Automata with Modulo Counters and Nondeterministic Counter Bounds. Internal Report 1110, Department of Computer Science, Loughborough University 2013. \url{https://dspace.lboro.ac.uk/2134/13438.}   CrossRef
  18. L. Yang, Z. Dang and O. H. Ibarra: On stateless automata and {P} systems. Internat. J. Found. Comput. Sci. 19 (2008), 1259-1276.   CrossRef