Growing Grammars and Length-reducing Automata

• Autorzy: Jurdziński T.
• Języki publikacji: EN

Abstrakty

EN

Growing context-sensitive grammars were introduced in 1986 as a restricted variant of context-sensitive grammars, where all productions are length increasing. Several interesting properties of these grammars have been shown since then, including polynomial time complexity of the membership problem and machine model characterizations. Various characterizations of the model, efficient recognition algorithm and the properties of its deterministic variant (possessing a characterization by string-rewriting systems) justify the practical value. Moreover, as pointed out by McNaughton in 1999, growing context-sensitive grammars complement the Chomsky hierarchy in a very natural way. This article reviews results on this topic and proposes some open problems.

Słowa kluczowe

EN

Chomsky hierarchy; growing grammars; length-reducing automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 112, nr 2/3
• Strony: 193--217
• Opis fizyczny: Bibliogr. 40 poz., tab., wykr.

Twórcy

autor

Jurdziński T.

• Institute of Computer Science, University of Wrocław, Joliot-Curie 15, PL-50-383 Wrocław, Poland,

Bibliografia

• [1] S.O. Aandera: On k-tape versus (k - 1)-tape real time computation. In: R.M. Karp (ed.), Proc. Complexity of Computation, SIAM-AMS Symposium in Appl. Math., 7, American Mathematical Society, 1974, pp. 75-96.
• [2] R.V. Book: Time-bounded grammars and their languages. Journal of Computer Systems Sciences , 5, 1071, pp. 397-429.
• [3] R.V. Book,S.A. Greibach: Quasi-realtime languages. Mathematical Systems Theory, 4, 1970, pp. 97-111.
• [4] R.V. Book, F. Otto: String-Rewriting Systems, Springer-Verlag, Berlin/New York, 1993.
• [5] Borodin, A., Cook, S. A., Dymond, P. W., Ruzzo,W. L., Tompa, M.: Two Applications of Inductive Counting for Complementation Problems. SIAM Journal on Computing, 18(3), 1989, pp. 559-578.
• [6] G. Buntrock: Wachsende kontextsensitive sprachen. Habilitationsschrift,Würzburg, 1995.
• [7] G. Buntrock, K. Lory´s: On growing context-sensitive languages. In: W. Kuich (ed.), Proc. ICALP'92, LNCS 623, Springer, 1992, pp. 77-88.
• [8] G. Buntrock, F. Otto: Growing Context-Sensitive Languages and Church-Rosser Languages. Information and Computation 141(1), 1998, pp. 1-36.
• [9] S. Cho, D.T. Huynh: Uniform membership for deterministic growing context-sensitive grammars is Pcomplete. Technical Report UTDCS-5-89, Computer Science Department, University of Texas at Dallas, Richardson, Texas 75083, 1989.
• [10] E. Dahlhaus, M.K. Warmuth: Membership for growing context-sensitive grammars is polynomial. Journal of Computer Systems Sciences , 33(3), 1986, pp. 456-472.
• [11] A. Gladkij: On the complexity of derivations for context-sensitive grammars. Algebri i Logika 3, 1964, pp. 29-44. [In Russian]
• [12] M. A. Harrison: Introduction to Formal Language Theory. Addison-Wesley, 1978.
• [13] M. Holzer, F. Otto: Shrinking Multi-pushdown Automata. In: M. Liskiewicz, R. Reischuk (eds.), Proc. FCT'05, LNCS 3623, Springer, 2005, pp. 305-316.
• [14] J. Hromkovič,G. Schnitger: On the Power of Randomized PushdownAutomata. In: W. Kuich, G. Rozenberg, A. Salomaa (eds.), Proc. Developments in Language Theory (DLT) 2001, LNCS 2295, pp. 262-271.
• [15] J. Hromkovič, G. Schnitger: Pushdown Automata andMulticounterMachines, a Comparison of Computation Modes. In: J. C. M. Baeten, J. K. Lenstra, J. Parrow, G. J. Woeginger (eds.), Proc. ICALP 2003, LNCS 2719, pp. 66-80.
• [16] P. Jančar, F. Mr´az, M. Pl´atek, and J. Vogel: Restarting autamata. In: H. Reichel (ed.), Proc. Fundamentals of Computation Theory (FCT) 1995, LNCS 965, Springer-Verlag, 1995, pp. 283-292.
• [17] T. Jurdziński: Probabilistic Length-Reducing Two-Pushdown Automata. Theory Comput. Syst. 45(1), 2009, pp. 74-107.
• [18] T. Jurdziński: The Boolean Closure of Growing Context-Sensitive Languages. Fundam. Inform. 89(2-3), 2008, pp. 289-305.
• [19] T. Jurdziński, K. Loryś: Lower bound technique for length-reducing automata. Information and Computation, 205(9), 2007, pp. 1387-1412.
• [20] T. Kasami: An Efficient Recognition and Syntax-Analysis Algorithm for Contex-free Languages. Science Report AFCRL-65-758, Air Force Cambridge Research Laboratory, Bedford,Mass., 1965.
• [21] M. Kutrib, A. Malcher: When Church-Rosser Becomes Context Free. International Journal of Foundations of Computer Science 18(6), 2007, pp. 1293-1302.
• [22] C. Lautemann: One pushdown and a small tape. In: K.W. Wagner (ed.), "Dirk Siefkes zum 50. Geburtstag", Technische Universitaet Berlin and Universitaet Augsburg, 1988.
• [23] M. Li, P. Vitanyi: An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag 1993.
• [24] Liu, L. Y.,Weiner, P.: An infinite hierarchy of intersections of context-free languages. Mathematical Systems Theory, 7, 1973, pp. 185-192.
• [25] R. McNaughton: An insertion into the Chomsky hierarchy? In: J. Karhumaki, H. A. Maurer, G. Paun, G. Rozenberg (eds.), Jewels are Forever, Contributions on Theoretical Computer Science in Honour of Arto Salomaa, Springer-Verlag, 1999, pp. 204-212.
• [26] R. McNaughton, P. Narendran, F. Otto: Church-Rosser Thue systems and formal languages. Journal of the Association Computing Machinery, 35 (1988), pp. 324-344.
• [27] P. Narendran, K. Krithivasan: On the membership problem for some grammars. COINS Technical Report CAR-TR-267 and CS-TR-1787 and AFOSR-86-0092, Center for Automation Research, University of Maryland, College Park, MD 20742, 1987.
• [28] G. Niemann: Church-Rosser Languages and Related Classes. PhD Thesis, Universitaet Kassel, 2002.
• [29] G. Niemann and F. Otto: Restarting automata, Church-Rosser languages, and representations of r.e. languages. In: G. Rozenberg and W. Thomas (eds.), Proc. Developments in Language Theory - Foundations, Applications, and Perspectives, (DLT) 1999,World Scientific, Singapore, 2000, pp. 103-114.
• [30] G. Niemann and F. Otto: Further results on restarting automata. In: M. Ito and T. Imaoka (eds.), Words, Languages and Combinatorics III, Proceedings,World Scientific, Singapore, 2003, pp. 353-369.
• [31] G. Niemann, F. Otto: The Church-Rosser languages are the deterministic variants of the growing contextsensitive languages. Information and Computation, 197(1-2), 2005, p. 1-21.
• [32] G. Niemann, J.R. Woinowski: The growing context-sensitive languages are the acyclic context-sensitive languages. In: W. Kuich, G. Rozenberg, A. Salomaa (eds.), Proc. Developments in Language Theory (DLT) 2001, LNCS 2295, Springer, 2002, pp. 197-205.
• [33] C. O'Dunlaing, Natalie Schluter: A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems. Theor. Comput. Sci. 411(3), 2010, pp. 677-690.
• [34] A. Okhotin: An overviewof conjunctive grammars. Formal Language Theory Column. Bulletin of the EATCS 79, 2003, pp. 145-163.
• [35] A. Okhotin: Boolean grammars. Information and Computation 194(1), 2004, pp. 19-48.
• [36] F. Otto: Restarting Automata and Their Relations to the Chomsky Hierarchy. In: Z. ´Esik, Z. Fülöp (eds.), Proc. Developments in Language Theory (DLT), 2003, LNCS 2710, pp. 55-74.
• [37] F. Otto, M. Katsura, Y. Kobayashi: Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids. Journal of Symbolic Computation 26(5), 1998, pp. 621-648.
• [38] J.R. Woinowski. A normal form for Church-Rosser language systems. In A. Middeldorp (ed.), Proc. Rewriting Techniques and Applications (RTA) 2001, LNCS 2051, 2001, Springer, pp. 322-337.
• [39] J.R. Woinowski. Prefix Languages of Church-Rosser Languages. In: S. Kapoor, S. Prasad (eds.), Proc. Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2000, LNCS 1974, 2000, Springer, pp. 516-530.
• [40] D.H. Younger: Recognition and parsing of context-free languages in time n3. Information and Control, 19, 1967, pp. 189-208.