×

Non-self-embedding grammars, constant-height pushdown automata, and limited automata. (English) Zbl 1462.68104

Summary: Non-self-embedding grammars are a restriction of context-free grammars which does not allow to describe recursive structures and, hence, which characterizes only the class of regular languages. A double exponential gap in size from non-self-embedding grammars to deterministic finite automata is known. The same size gap is also known from constant-height pushdown automata and \(1\)-limited automata to deterministic finite automata. Constant-height pushdown automata and \(1\)-limited automata are compared with non-self-embedding grammars. It is proved that non-self-embedding grammars and constant-height pushdown automata are polynomially related in size. Furthermore, a polynomial size simulation by \(1\)-limited automata is presented. However, the converse transformation is proved to cost exponential. Finally, a different simulation shows that also the conversion of deterministic constant-height pushdown automata into deterministic \(1\)-limited automata costs polynomial.

MSC:

68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anselmo, M., Giammarresi, D. and Varricchio, S., Finite automata and non-self-embedding grammars, CIAA 2002, 2608 (2002), pp. 47-56. · Zbl 1033.68053
[2] Bednárová, Z., Geffert, V., Mereghetti, C. and Palano, B., Removing nondeterminism in constant height pushdown automata, Inf. Comput.237 (2014) 257-267. · Zbl 1360.68539
[3] Bednárová, Z., Geffert, V., Mereghetti, C. and Palano, B., The size-cost of Boolean operations on constant height deterministic pushdown automata, Theoretical Computer Science449 (2012) 23-36. · Zbl 1272.68205
[4] Chomsky, N., On certain formal properties of grammars, Information and Control2(2) (1959) 137-167. · Zbl 0088.10801
[5] Chomsky, N., A note on phrase structure grammars, Information and Control2(4) (1959) 393-395. · Zbl 0095.33804
[6] Geffert, V., Mereghetti, C. and Palano, B., More concise representation of regular languages by automata and regular expressions, Inf. Comput.208(4) (2010) 385-394. · Zbl 1192.68409
[7] Hibbard, T. N., A generalization of context-free determinism, Information and Control11(1/2) (1967) 196-238. · Zbl 0168.25801
[8] Hopcroft, J. E., Motwani, R. and Ullman, J. D., Introduction to automata theory, languages, and computation - (2. ed.) (Addison-Wesley-Longman, 2001). · Zbl 0980.68066
[9] Kapoutsis, C. A., Královic, R. and Mömke, T., Size complexity of rotating and sweeping automata, J. Comput. Syst. Sci.78(2) (2012) 537-558. · Zbl 1242.68146
[10] Kelemenová, A., Complexity of normal form grammars, Theor. Comput. Sci.28 (1984) 299-314. · Zbl 0548.68070
[11] Kutrib, M., Pighizzini, G. and Wendlandt, M., Descriptional complexity of limited automata, Information and Computation259 (2018) 259-276. · Zbl 1390.68404
[12] Kutrib, M. and Wendlandt, M., On simulation cost of unary limited automata, DCFS 2015, 9118, (Springer, 2015), pp. 153-164. · Zbl 1390.68405
[13] Mereghetti, C. and Pighizzini, G., Two-way automata simulations and unary languages, Journal of Automata, Languages and Combinatorics5(3) (2000) 287-300. · Zbl 0965.68043
[14] Ogden, W. F., Ross, R. J. and Winklmann, K., An “interchange lemma” for context-free languages, SIAM J. Comput.14(2) (1985) 410-415. · Zbl 0601.68051
[15] Pighizzini, G., Deterministic pushdown automata and unary languages, Int. J. Found. Comput. Sci.20(4) (2009) 629-645. · Zbl 1191.68400
[16] Pighizzini, G. and Pisoni, A., Limited automata and regular languages, Int. J. Found. Comput. Sci.25(7) (2014) 897-916. · Zbl 1320.68114
[17] Pighizzini, G. and Prigioniero, L., Non-self-embedding grammars and descriptional complexity, Ninth Workshop on Non-Classical Models of Automata and Applications, NCMA 2017, Prague, Czech Republic, August 17-18, 2017, (Österreichische Computer Gesellschaft, 2017), pp. 197-209.
[18] Pighizzini, G. and Prigioniero, L., Limited automata and unary languages, Inf. Comput.266 (2019) 60-74. · Zbl 1427.68153
[19] Pighizzini, G., Shallit, J. and Wang, M., Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds, J. Comput. Syst. Sci.65(2) (2002) 393-414. · Zbl 1059.68068
[20] Sakoda, W. J. and Sipser, M., Nondeterminism and the size of two way finite automata, Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, (ACM, 1978), pp. 275-286. · Zbl 1282.68160
[21] Wagner, K. W. and Wechsung, G., Computational Complexity (D. Reidel Publishing Company, Dordrecht, 1986). · Zbl 0584.68061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.