The Boolean Closure of Growing Context-Sensitive Languages

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

Abstrakty

EN

The set of growing context-sensitive languages (GCSL) is a naturally defined subclass of context-sensitive languages whose membership problem is solvable in polynomial time. Moreover, growing context-sensitive languages and their deterministic counterpart called Church-Rosser Languages (CRL) complement the Chomsky hierarchy in a natural way [13]. In this paper, closures of GCSL under the boolean operations are investigated. It is shown that there exists an infinite intersection hierarchy for GCSL and CRL, answering an open problem from [2]. Furthermore, the expressive power of the boolean closures of GCSL, CRL, CFL and LOGCFL are compared.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 89, nr 2-3
• Strony: 289--305
• Opis fizyczny: bibliogr. 21 poz., 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] 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, 559-578.
• [2] Buntrock, G., Lory´s, K.: On growing context-sensitive languages, ICALP 1992, LNCS 623, 77-88.
• [3] Buntrock, G., Otto, F.: Growing Context-Sensitive Languages and Church-Rosser Languages, Information and Compation, 141(1), 1998, 1-36.
• [4] Dahlhaus, E., Warmuth, M.: Membership for growing context-sensitive grammars is polynomial, Journal of Computer and System Sciences, 33(3), 1986, 456-472.
• [5] Holzer, M., Otto, F.: Shrinking Multi-pushdown Automata, Proc. of Fundamentals of Computation Theory (FCT) 2005, LNCS 3623, 305-316.
• [6] Jurdziński, T.: Probabilistic Length-Reducing Two-Pushdown Automata, Theory of Computing Systems, DOI: 10.1007/s00224-007-9066-x, to appear (a full version of [8]).
• [7] Jurdziński, T.: The Boolean Closure of Growing Context-Sensitive Languages, DLT 2006 (Developments in Language Theory), LNCS 4036, 248-259.
• [8] Jurdziński, T.: Probabilistic Length-Reducing Automata, MFCS 2006, LNCS 4162, 561-572.
• [9] Jurdziński, T., Lory´s, K.: Lower bound technique for length-reducing automata, Information and Computation, 205(9), 2007, 1387-1412.
• [10] Kutrib, M., Malcher, A.,Wotschke, D.: The Boolean Closure of Linear Context-Free Languages, DLT 2004, LNCS 3340, 284-295.
• [11] Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, 1993.
• [12] Liu, L. Y.,Weiner, P.: An infinite hierarchy of intersections of context-free languages, Mathematical Systems Theory, 7, 1973, 185-192.
• [13] McNaughton, R.: An Insertion into the Chomsky Hierarchy?, Jewels are Forever, Contributions on Theoretical Computer Science in Honour of Arto Salomaa, Springer, 1999, 204-212.
• [14] McNaughton, R., Narendran, P., Otto, F.: Church-Rosser Thue systems and formal languages, Journal of the Association of Computing Machinery, 35, 1988, 324-344.
• [15] Niemann, G.: Church-Rosser Languages and Related Classes, Ph.D. Thesis, Universitaet Kassel, 2002.
• [16] Niemann, G., Otto, F.: The Church-Rosser languages are the deterministic variants of the growing contextsensitive languages, Information and Computation, 197(1-2), 2005, 1-21.
• [17] Okhotin, A.: Boolean grammars, Information and Computation, 194(1), 2004, 19-48.
• [18] Woinowski, J. R.: Prefix Languages of Church-Rosser Languages, Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2000, LNCS 1974, 516-530.
• [19] Wotschke, D.: Nondeterminismand Boolean Operations in PDAs, Journal of Computer and System Sciences, 16(3), 1978, 456-461.
• [20] Wotschke, D.: The Boolean Closures of the Deterministic and Nondeterministic Context-Free Languages, GI Jahrestagung, LNCS 1, 1973, 113-121.
• [21] Wotschke, D.: A characterization of boolean closures of families of languages, Automatentheorie und Formale Sprachen, LNCS 2, 1973, 191-200.