Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
289--305
Opis fizyczny
bibliogr. 21 poz., wykr.
Twórcy
autor
- Institute of Computer Science, University of Wrocław , Joliot-Curie 15, PL-50-383 Wrocław, Poland, tju@ii.uni.wroc.pl
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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS8-0003-0061