Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
multi-head automata; counter automata; modulo counters; stateless automata; restricted nondeterminism
multi-head automata; counter automata; modulo counters; stateless automata; restricted nondeterminism
Summary:
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.
References:
[1] Chang, J. H., Ibarra, O. H., Palis, M. A., Ravikumar, B.: On pebble automata. Theoret. Comput. Sci. 44 (1986), 111-121. DOI 10.1016/0304-3975(86)90112-X | MR 0858693 | Zbl 0612.68045
[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 2804119 | Zbl 1247.68133
[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 2544705 | Zbl 1247.68138
[4] Harrison, M.: Introduction to Formal Language Theory. Addison-Wesley, Reading 1978. MR 0526397 | Zbl 0411.68058
[5] Holzer, M., Kutrib, M., Malcher, A.: Complexity of multi-head finite automata: Origins and directions. Theoret. Comput. Sci. 412 (2011), 83-96. DOI 10.1016/j.tcs.2010.08.024 | MR 2779447 | Zbl 1207.68188
[6] Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading 1979. MR 0645539 | Zbl 0980.68066
[7] Ibarra, O. H.: Reversal-bounded multicounter machines and their decision problems. J. Assoc. Comput. Mach. 25 (1978), 116-133. DOI 10.1145/322047.322058 | MR 0461988 | Zbl 0365.68059
[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 2545803 | Zbl 1248.68302
[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 10.1016/j.tcs.2009.09.001 | MR 2590137 | Zbl 1184.68316
[10] Ibarra, O. H., Ravikumar, B.: On partially blind multihead finite automata. Theoret. Comput. Sci. 356 (2006), 190-199. DOI 10.1016/j.tcs.2006.01.030 | MR 2217837 | Zbl 1160.68414
[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 10.1142/S0129054110007556 | MR 2728324 | Zbl 1207.68193
[13] Monien, B.: Two-way multihead automata over a one-letter alphabet. RAIRO Inform. Théor. 14 (1980), 67-82. MR 0570039 | Zbl 0442.68039
[14] Petersen, H.: Automata with sensing heads. In: Proc. 3rd Israel Symposium on Theory of Computing and Systems 1995, p. 150-157. MR 1333431
[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 2776296
[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 10.1142/S0129054108006261 | MR 2454747 | Zbl 1175.68180
Search
Partner of
