The Complexity of Szilard Languages of Matrix Grammars Revisited

• Autorzy: Cojocaru L. , Mäkinen E.
• Języki publikacji: EN

Abstrakty

EN

The regulated rewriting mechanism is one of the most efficient methods to augment the Chomsky hierarchy with a large variety of language classes. In this paper we investigate the derivation mechanism in regulated rewriting grammars such as matrix grammars, by studying their Szilard languages. We focus on the complexity of Szilard languages associated with unrestricted and leftmost-like derivations in matrix grammars, with or without appearance checking. The reason is twofold. First, to relate these classes of languages to parallel complexity classes such as NC¹ and AC¹, and, second, to improve some previous results. We prove that unrestricted Szilard languages and certain leftmost Szilard languages of context-free matrix grammars, without appearance checking, can be accepted by indexing alternating Turing machines in logarithmic time and space. Consequently, these classes are included in U_E-uniform NC¹. Unrestricted Szilard languages of matrix grammars with appearance checking can be accepted by deterministic Turing machines in O(n log n) time and O(log n) space. Leftmost-like Szilard languages of context-free matrix grammars, with appearance checking, can be recognized by nondeterministic Turing machines by using the same time and space resources. Hence, all these classes are included in AC¹.

Słowa kluczowe

EN

matrix grammars; Szilard languages; alternating Turing machines; NC1 and AC1; complexity classes

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 123, nr 4
• Strony: 381--399
• Opis fizyczny: Bibliogr. 35 poz.

Twórcy

autor

Cojocaru L.

• School of Information Sciences, Computer Science University of Tampere Kanslerinrinne 1, Tampere, FIN-33014, Finland

autor

Mäkinen E.

• School of Information Sciences, Computer Science University of Tampere Kanslerinrinne 1, Tampere, FIN-33014, Finland

Bibliografia

• [1] Abraham, S.: Some Questions of Phrase-Structure Grammars, Linguistics, 5(31), 1967, 5-12.
• [2] Altman, E., Banerji, R.: Some Problems of Finite Representability, Information and Control, 8, 1965, 251–263.
• [3] Balcázar, J. L., Dıaz, J., Gabarró, J.: Structural Complexity, vol. II, Springer-Verlag, 1990.
• [4] Borodin, A.: On Relating Time and Space to Size and Depth, SIAM Journal on Computing, 6(4), 1977, 733–743.
• [5] Chandra, A., Kozen, D., Stockmeyer, L.: Alternation, Journal of Association for Computing Machinery, 28(1), 1981, 114–133.
• [6] Cojocaru, L., Mäkinen, E.: On the Complexity of Szilard Languages of Matrix Grammars, Proceedings of the 13th IEEE International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2011, IEEE Computer Society Press, Los Alamitos, 2011, 339–347.
• [7] Cojocaru, L., Mäkinen, E., T¸ iplea, F. L.: Classes of Szilard Languages in NC1, Proceedings of the 11th IEEE International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2009, IEEE Computer Society Press, Los Alamitos, 2009, 299–306.
• [8] Crespi-Reghizzi, S., Mandrioli, D.: Petri Nets and Szilard Languages, Information and Control, 33(2), 1977, 177–192.
• [9] Dassow, J., Fernau, H., Păun, Gh.: On the Leftmost Derivation in Matrix Grammars, International Journal of Foundations of Computer Science, 10(1), 1999, 61–80.
• [10] Dassow, J., Păun, Gh.: Regulated Rewriting in Formal Language Theory, Springer-Verlag, 1989.
• [11] Dassow, J., Păun, Gh., Salomaa, A.: Grammars with Controlled Derivations, Handbook of Formal Languages, vol. II, (G. Rozenberg, A. Salomaa, Eds.), Springer-Verlag, 1997, 101–154.
• [12] Duske, J., Parchmann, R., Specht, J.: Szilard Languages of IO-Grammars, Information and Control, 40(3), 1979, 319–331.
• [13] Fernau, H.: Regulated Grammars under Leftmost Derivation, Grammars, 3(1), 2000, 37–62.
• [14] Fischer, P., Meyer, A., Rosenberg, A.: Counter Machines and Counter Languages, Theory of Computing Systems, 2(3), 1968, 265–283.
• [15] Fleck, A. C.: An Analysis of Grammars by Their Derivation Sets, Information and Control, 24, 1974, 389–398.
• [16] Hopcroft, J., Ullman J.: Introduction to Automata Theory, Languages and Computation, AddisonWesley, 1979.
• [17] Höpner, M., Opp, M.: Renaming and Erasing in Szilard Languages, Proceedings of the 4th International Colloquium on Automata, Languages and Programming, ICALP 1977 (A. Salomaa, M. Steinby, Eds.), LNCS 52, Springer-Verlag, 1977, 244–257.
• [18] Igarashi, Y.: The Tape Complexity of Some Classes of Szilard Languages, SIAM Journal of Computing, 6, 1977, 460–466.
• [19] Linna, M.: Two Decidability Results for Deterministic Pushdown Automata, Mathematical Foundations of Computer Science (J. Gruska, Ed.), LNCS 53, Springer-Verlag, 1977, 365–373.
• [20] Mäkinen, E.: On Certain Properties of Left Szilard Languages, Elektronische Informationsverarbeitung und Kybernetik EIK, 19(10/11), 1983, 497–501.
• [21] Mäkinen, E.: On Context-Free and Szilard Languages, BIT Numerical Mathematics, 24(2), 1984, 164–170.
• [22] Mäkinen, E.: A Note on Depth-First Derivations, BIT Numerical Mathematics, 25(1), 1985, 293–296.
• [23] Mäkinen, E.: On Szilard Languages of Pure Context-Free Grammars, Elektronische Informationsverarbeitung und Kybernetik EIK, 22(10/11), 1986, 527–532.
• [24] Mäkinen, E.: On Homomorphic Images of Szilard Languages, International Journal of Computer Mathematics, 18(3/4), 1986, 239–245.
• [25] Mäkinen, E.: A Note on the Inclusion Problem for Szilard Languages, International Journal of Computer Mathematics, 21(3/4), 1987, 291–295.
• [26] Moriya, E.: Associate Languages and Derivational Complexity of Formal Grammars and Languages, Information and Control, 22(2), 1973, 139–162.
• [27] Păun, Gh.: On Szilard’s Languages Associated to a Matrix Grammar, Information Processing Letters, 8(2), 1979, 104–105.
• [28] Penttonen, M.: On Derivation Language Corresponding to Context-Free Grammars, Acta Informatica, 3, 1974, 285–291.
• [29] Penttonen, M.: Szilard Languages Are log n Tape Recognizable, Elektronische Informationsverarbeitung und Kybernetik EIK, 13(11), 1977, 595–602.
• [30] Ruzzo, W.: On Uniform Circuit Complexity, Journal of Computer and System Sciences, 22(3), 1981, 365–383.
• [31] Salomaa, A.: Matrix Grammars with a Leftmost Restriction, Information and Control, 20(2), 1972, 143–149.
• [32] Salomaa, A.: Formal Languages, Academic Press, London-New York, 1973.
• [33] Stotskij, E. D.: Some Restriction on Derivations in Context-Free Grammars, Nauchno-Tekhnicheskaya Informatsiya Seriya, 2(7), 1967, 35–38.
• [34] Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach, Springer-Verlag, 1999.
• [35] Wegener, I.: The Complexity of Boolean functions, Wiley-Teubner Series in Computer Science, New York-Stuttgart, 1987.