Geodesic
Automata with modulo counters and nondeterministic counter bounds
Kybernetika, Tome 50 (2014) no. 1, pp. 66-94
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2014-1-0066
Classification : 68Q05, 68Q10, 68Q45
Keywords: multi-head automata; counter automata; modulo counters; stateless automata; restricted nondeterminism 
@article{10_14736_kyb_2014_1_0066,
     author = {Reidenbach, Daniel and Schmid, Markus L.},
     title = {Automata with modulo counters and nondeterministic counter bounds},
     journal = {Kybernetika},
     pages = {66--94},
     year = {2014},
     volume = {50},
     number = {1},
     doi = {10.14736/kyb-2014-1-0066},
     mrnumber = {3195005},
     zbl = {06296992},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2014-1-0066/}
}
TY  - JOUR
AU  - Reidenbach, Daniel
AU  - Schmid, Markus L.
TI  - Automata with modulo counters and nondeterministic counter bounds
JO  - Kybernetika
PY  - 2014
SP  - 66
EP  - 94
VL  - 50
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2014-1-0066/
DO  - 10.14736/kyb-2014-1-0066
LA  - en
ID  - 10_14736_kyb_2014_1_0066
ER  - 
%0 Journal Article
%A Reidenbach, Daniel
%A Schmid, Markus L.
%T Automata with modulo counters and nondeterministic counter bounds
%J Kybernetika
%D 2014
%P 66-94
%V 50
%N 1
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2014-1-0066/
%R 10.14736/kyb-2014-1-0066
%G en
%F 10_14736_kyb_2014_1_0066
Reidenbach, Daniel; Schmid, Markus L. Automata with modulo counters and nondeterministic counter bounds. Kybernetika, Tome 50 (2014) no. 1, pp. 66-94. doi: 10.14736/kyb-2014-1-0066

[1] Chang, J. H., Ibarra, O. H., Palis, M. A., Ravikumar, B.: On pebble automata. Theoret. Comput. Sci. 44 (1986), 111-121. | DOI | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[4] Harrison, M.: Introduction to Formal Language Theory. Addison-Wesley, Reading 1978. | MR | Zbl

[5] Holzer, M., Kutrib, M., Malcher, A.: Complexity of multi-head finite automata: Origins and directions. Theoret. Comput. Sci. 412 (2011), 83-96. | DOI | MR | Zbl

[6] Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading 1979. | MR | Zbl

[7] Ibarra, O. H.: Reversal-bounded multicounter machines and their decision problems. J. Assoc. Comput. Mach. 25 (1978), 116-133. | DOI | MR | Zbl

[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. | MR | Zbl

[9] Ibarra, O. H., Karhumäki, J., Okhotin, A.: On stateless multihead automata: Hierarchies and the emptiness problem. Theoret. Comput. Sci. 411 (2010), 581-593. | DOI | MR | Zbl

[10] Ibarra, O. H., Ravikumar, B.: On partially blind multihead finite automata. Theoret. Comput. Sci. 356 (2006), 190-199. | DOI | MR | Zbl

[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.: On stateless two-pushdown automata and restarting automata. Internat. J. Found. Comput. Sci. 21 (2010), 781-798. | DOI | MR | Zbl

[13] Monien, B.: Two-way multihead automata over a one-letter alphabet. RAIRO Inform. Théor. 14 (1980), 67-82. | MR | Zbl

[14] Petersen, H.: Automata with sensing heads. In: Proc. 3rd Israel Symposium on Theory of Computing and Systems 1995, p. 150-157. | MR

[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. | MR

[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.: On stateless automata and P systems. Internat. J. Found. Comput. Sci. 19 (2008), 1259-1276. | DOI | MR | Zbl

Cité par Sources :