Time and space complexity of inside-out macro languages

References

• Aho , A.V. 1968 . Indexed grammars-an extension of contxt-free grammars . J. Assoc. Comp. Math , 15 : 647 – 671 .
   Google Scholar
• Asveld , P.R.J. 1978 . Iterated Context-Independent Rewriting-An Algebraic Approach to Families of Languages , Netherlands : Twente University of Technology .
   Google Scholar
• Asveld , P.R.J. 1980 . Space-bounded complexity classes and iterated deterministic substitution . Inform. Contr , 44 : 282 – 299 .
   Google Scholar
• Asveld , P.R.J. 1981 . Generalizations of context-free grammars and the non-self-embedding propert , Amsterdam : Mathematical Centre .
   Google Scholar
• Asveld , P.R.J. and Engelfriet , J. 1979 . Extended linear macro grammars, iteration grammars, and register programs . Acta Informatica , 11 : 259 – 285 .
   Google Scholar
• Cook , S.A. 1971 . Characterizations of pushdown machines in terms of time-bounded computers . J. Assoc. Comp. Mach , 18 : 4 – 18 .
   Web of Science ®Google Scholar
• Downey , P.J. 1974 . Formal Languages and Recursion Schemes . Proceedings IEEE Conf. on Biologically Motivated Automata Theory . 1974 .
   Google Scholar
• Engelfriet , J. and Schmidt.E , Meineche. 1977 . IO and OI, Part I . J. Comput. System Sci , 15 : 328 – 353 .
   Google Scholar
• Engelfriet , J. and Slutzki , G. 1979 . Bounded nesting in macro grammars . Inform. Contr , 42 : 157 – 193 .
   Google Scholar
• Erni , W.J. 1976 . Some further languages log-tape reducible to context-free languages , Karlsruhe : Institut fur Angewandte Informatik und Formale Beschreibungsverfahren .
   Google Scholar
• Erni , W.J. 1977 . Auxiliary pushdown acceptors and regulated rewriting systems , Karlsruhe : Institut fur Angewandte Informatik und Formale Beschreibungsverfahren .
   Google Scholar
• Fischer , M.J. 1968 . Grammars with Macro-like Productions , Cambridge : Harvard University .
   Google Scholar
• Fischer , M.J. 1968 . Grammars with macro-like productions . Proceedings 9th Ann. IEEE Symp. on Switching and Automata Theory , : 131 – 142 .
   Google Scholar
• Harju , T. 1977 . A polynomial recognition algorithm for the EDTOL languages . Elektron. Informationsverarbeit. Kybernetik , 13 : 169 – 177 .
   Google Scholar
• Harrison , M.A. 1978 . Introduction to Formal Language Theory , Addison-Wesley .
   Google Scholar
• Hopcroft , J.E. and Ullman , J.D. 1979 . Introduction to Automata Theory, Languages and Computation , Addison-Wesley .
   Google Scholar
• Hunt , H.B. 1976 . On the complexity of finite, pushdown, and stack automata . Math. Systems Theory , 10 : 33 – 52 .
   Google Scholar
• Jones , N.D. and Skyum , S. 1977 . Recognition of deterministic ETOL languages in logarithmic space . Inform. Contr , 35 : 177 – 181 .
   Google Scholar
• Maslov , A.N. 1974 . The hierarchy of indexed languages of an arbitrary level . Soviet Math , 15 : 1170 – 1174 .
   Google Scholar
• Rounds , W.C. 1973 . Complexity of recognition in intermediate-level languages . Proceedings 14th Ann. IEEE Symp. on Switching and Automata Theory , 15 : 145 – 158 .
   Google Scholar
• Sudborough , I.H. 1977 . “ The time and tape complexity of developmental languages ” . In Lecture Notes in Computer Science , Edited by: Salomaa , A. and Steinby , M. Vol. 52 , 509 – 523 . Heidelberg, New York : Springer-Verlag .
   Google Scholar
• Sudborough , I.H. 1977 . The complexity of the membership problem for some extensions of context-free languages . Internat. J. Computer Math , 6 : 191 – 215 .
   Web of Science ®Google Scholar
• Sudborough , I.H. 1978 . On the tape complexity of deterministic context-free languages . J. Assoc. Comp. Mach , 25 : 405 – 414 .
   Web of Science ®Google Scholar
• Wand , M. 1973 . Mathematical Foundations of Formal Language Theory , Cambridge : Massachusetts Institute of Technology .
   Google Scholar