Automata with modulo counters and nondeterministic counter bounds

Daniel Reidenbach; Markus L. Schmid

Kybernetika (2014)

  • Volume: 50, Issue: 1, page 66-94
  • ISSN: 0023-5954

Abstract

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

How to cite

top

Reidenbach, Daniel, and Schmid, Markus L.. "Automata with modulo counters and nondeterministic counter bounds." Kybernetika 50.1 (2014): 66-94. <http://eudml.org/doc/261159>.

@article{Reidenbach2014,
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.},
author = {Reidenbach, Daniel, Schmid, Markus L.},
journal = {Kybernetika},
keywords = {multi-head automata; counter automata; modulo counters; stateless automata; restricted nondeterminism; multi-head automata; counter automata; modulo counters; stateless automata; restricted nondeterminism},
language = {eng},
number = {1},
pages = {66-94},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Automata with modulo counters and nondeterministic counter bounds},
url = {http://eudml.org/doc/261159},
volume = {50},
year = {2014},
}

TY - JOUR
AU - Reidenbach, Daniel
AU - Schmid, Markus L.
TI - Automata with modulo counters and nondeterministic counter bounds
JO - Kybernetika
PY - 2014
PB - Institute of Information Theory and Automation AS CR
VL - 50
IS - 1
SP - 66
EP - 94
AB - 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.
LA - eng
KW - multi-head automata; counter automata; modulo counters; stateless automata; restricted nondeterminism; multi-head automata; counter automata; modulo counters; stateless automata; restricted nondeterminism
UR - http://eudml.org/doc/261159
ER -

References

top
  1. Chang, J. H., Ibarra, O. H., Palis, M. A., Ravikumar, B., 10.1016/0304-3975(86)90112-X, Theoret. Comput. Sci. 44 (1986), 111-121. Zbl0612.68045MR0858693DOI10.1016/0304-3975(86)90112-X
  2. Chiniforooshan, E., Daley, M., Ibarra, O. H., Kari, L., Seki, S., 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. Zbl1247.68133MR2804119
  3. Frisco, P., Ibarra, O. H., 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. Zbl1247.68138MR2544705
  4. Harrison, M., Introduction to Formal Language Theory., Addison-Wesley, Reading 1978. Zbl0411.68058MR0526397
  5. Holzer, M., Kutrib, M., Malcher, A., 10.1016/j.tcs.2010.08.024, Theoret. Comput. Sci. 412 (2011), 83-96. Zbl1207.68188MR2779447DOI10.1016/j.tcs.2010.08.024
  6. Hopcroft, J. E., Ullman, J. D., Introduction to Automata Theory, Languages, and Computation., Addison-Wesley, Reading 1979. Zbl0980.68066MR0645539
  7. Ibarra, O. H., 10.1145/322047.322058, J. Assoc. Comput. Mach. 25 (1978), 116-133. Zbl0365.68059MR0461988DOI10.1145/322047.322058
  8. Ibarra, O. H., Eğecioğlu, Ö., Hierarchies and characterizations of stateless multicounter machines., In: Computing and Combinatorics, Lecture Notes in Comput. Sci. 5609 (2009), pp. 408-417. Zbl1248.68302MR2545803
  9. Ibarra, O. H., Karhumäki, J., Okhotin, A., 10.1016/j.tcs.2009.09.001, Theoret. Comput. Sci. 411 (2010), 581-593. Zbl1184.68316MR2590137DOI10.1016/j.tcs.2009.09.001
  10. Ibarra, O. H., Ravikumar, B., 10.1016/j.tcs.2006.01.030, Theoret. Comput. Sci. 356 (2006), 190-199. Zbl1160.68414MR2217837DOI10.1016/j.tcs.2006.01.030
  11. Kutrib, M., Malcher, A., Wendlandt, M., 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. 
  12. Kutrib, M., Messerschmidt, H., Otto, F., 10.1142/S0129054110007556, Internat. J. Found. Comput. Sci. 21 (2010), 781-798. Zbl1207.68193MR2728324DOI10.1142/S0129054110007556
  13. Monien, B., Two-way multihead automata over a one-letter alphabet., RAIRO Inform. Théor. 14 (1980), 67-82. Zbl0442.68039MR0570039
  14. Petersen, H., Automata with sensing heads., In: Proc. 3rd Israel Symposium on Theory of Computing and Systems 1995, p. 150-157. MR1333431
  15. Reidenbach, D., Schmid, M. L., 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. MR2776296
  16. Reidenbach, D., Schmid, M. L., 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. 
  17. Reidenbach, D., Schmid, M. L., Automata with Modulo Counters and Nondeterministic Counter Bounds., Internal Report 1110, Department of Computer Science, Loughborough University 2013. https://dspace.lboro.ac.uk/2134/13438. 
  18. Yang, L., Dang, Z., Ibarra, O. H., 10.1142/S0129054108006261, Internat. J. Found. Comput. Sci. 19 (2008), 1259-1276. Zbl1175.68180MR2454747DOI10.1142/S0129054108006261

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.