Grammars with Context Conditions
and Their Applications

Alexander Meduna and Martin Švec

Wiley, Hoboken, New Jersey, 2005

Home

Authors' Bio

Related Publications

the authors
the authors

Crucial Journal Papers by the Authors

A. Meduna. Context-free Derivations on Word Monoids. Acta Informatica, 27:781--786, 1990.

A. Meduna. Generalized Forbidding Grammars. International Journal of Computer Mathematics, 36:31--38, 1990.

A. Meduna. Syntactic Complexity of Scattered Context Grammars. Acta Informatica, 32:285--298, 1995.

A. Meduna. Syntactic Complexity of Context-Free Grammars over Word Monoids. Acta Informatica, 33:457--462, 1996.

A. Meduna and M. Švec. Reduction of Simple Semi-conditional Grammars with Respect to the Number of Conditional Productions. Acta Cybernetica, 15:353--360, 2002.

A. Meduna and M. Švec. Descriptional Complexity of Generalized Forbidding Grammars. International Journal of Computer Mathematics, 80(1):11--17, 2003.

A. Meduna and M. Švec. Forbidding ET0L Grammars. Theoretical Computer Science, 306:449--469, 2003.

Additional Publications by the Authors

A. Meduna. A Note on Exponential Density of ET0L Languages. Kybernetika, 22:514--518, 1986.

A. Meduna. Characterization of the Chomsky Hierarchy Through Sequential-Parallel Grammars. Rostocker Mathematische Kolloquium, 32:4--14, 1987.

A. Meduna. Evaluated grammars. Acta Cybernetika, 8:169--176, 1987.

A. Meduna. Symbiotic E0L systems. Acta Cybernetica, 10:165--172, 1992.

A. Meduna. Canonical scattered rewriting. International Journal of Computer Mathematics, 51:122--129, 1993.

A. Meduna. A Formalization of Sequential, Parallel and Continuous Rewriting. International Journal of Computer Mathematics, 47:153--161, 1993.

A. Meduna. Matrix Grammars under Leftmost and Rightmost Restrictions. In Gh. Paun, ed., Mathematical Linguistics and Related Topics. Romanian Academy of Sciences, Bucharest, 1994, pp. 243--257.

A. Meduna. A Trivial Method of Characterizing the Family of Recursively Enumerable Languages by Scattered Context Grammars. EATCS Bulletin, 56:104--106, 1995.

A. Meduna. On the Number of Nonterminals in Matrix Grammars with Leftmost Derivations. LNCS, 1217:27--38, 1997.

A. Meduna. Six-Nonterminal Multi-Sequential Grammars Characterize the Family of Recursively Enumerable Languages. International Journal of Computer Mathematics, 65:179--189, 1997.

A. Meduna. Descriptional Complexity of Multi-Continuous Grammars. Acta Cybernetica, 13:375--384, 1998.

A. Meduna. Economical Transformation of Phrase-Structure Grammars to Scattered Context Grammars. Acta Cybernetica, 13:225--242, 1998.

A. Meduna. Prefix Pushdown Automata. International Journal of Computer Mathematics, 71:215--228, 1999.

A. Meduna. Four-Nonterminal Scattered Context Grammars Characterize the Family of Recursively Enumerable Languages. International Journal of Computer Mathematics, 63:67--83, 1997.

A. Meduna. Generative Power of Three-Nonterminal Scattered Context Grammars. Theoretical Computer Science, 246:276--284, 2000.

A. Meduna. Terminating Left-Hand Sides of Scattered Context Productions. Theoretical Computer Science, 237:423--427, 2000.

A. Meduna. Uniform Generation of Languages by Scattered Context Grammars. Fundamenta Informaticae, 44:231--235, 2001.

A. Meduna. Descriptional Complexity of Scattered Rewriting and Multirewriting: An Overview. Journal of Automata, Languages and Combinatorics, 7:571--577, 2002.

A. Meduna. Coincidental Extension of Scattered Context Languages. Acta Informatica, 39:307--314, 2003.

A. Meduna. Simultaneously One-Turn Two-Pushdown Automata. International Journal of Computer Mathematics, 80:679--687, 2003.

A. Meduna, C. Crooks, and M. Sarek. Syntactic Complexity of Regulated Rewriting. Kybernetika, 30:177--186, 1994.

A. Meduna and E. Csuhaj-Varju. Grammars with Context Conditions. EATCS Bulletin, 32:112--124, 1993.

A. Meduna. Automata and Languages: Theory and Applications. Springer, London, 2000.

A. Meduna and H. Fernau. On the Degree of Scattered Context-Sensitivity. Theoretical Computer Science, 290:2121--2124, 2003.

A. Meduna and H. Fernau. A Simultaneous Reduction of Several Measures of Descriptional Complexity in Scattered Context Grammars. Information Processing Letters, 86:235--240, 2003.

A. Meduna and A. Gopalaratnam. On Semi-Conditional Grammars with Productions Having Either Forbidding or Permitting Conditions. Acta Cybernetica, 11:307--323, 1994.

A. Meduna and G. Horvath. On State Grammars. Acta Cybernetica, 8:237--245, 1988.

A. Meduna and D. Kolar. Descriptional Complexity of Multi-Parallel Grammars with Respect to the Number of Nonterminals. In Grammars and Automata for String Processing: from Mathematics and Computer Science to Biology and Back. Francis and Taylor, London, 2000, pp. 724--732.

A. Meduna and D. Kolar. Regulated Pushdown Automata. Acta Cybernetica, 18:653--664, 2000.

A. Meduna and D. Kolar. Homogenous Grammars with a Reduced Number of Non-Context-Free Productions. Information Processing Letters, 81:253--257, 2002.

A. Meduna and D. Kolar. One-Turn Regulated Pushdown Automata and Their Reduction. Fundamenta Informaticae, 16:399--405, 2002.

A. Meduna and P. Vurm. Multisequential Grammars with Homogeneous Selectors. Fundamenta Informaticae, 34:1--7, 2001.

Relevant Publications not by the Authors

E. Csuhaj-Varju. On Grammars with Local and Global Context Conditions. International Journal of Computer Mathematics, 47:17--27, 1992.

J. Dassow and Gh. Paun. Regulated Rewriting in Formal Language Theory. Akademie-Verlag, Berlin, 1989.

J. Gonczarowski and M. K.Warmuth. Scattered and Context-Sensitive Rewriting. Acta Informatica, 20:391--411, 1983.

S. Greibach and J. Hopcroft. Scattered Context Grammars. Journal of Computer and System Sciences, 3:233--247, 1969.

E. Navratil. Context-Free Grammars with Regular Conditions. Kybernetika, 6(2):118--125, 1970.

Gh. Paun. On the Generative Capacity of Conditional Grammars. Information and Control, 43:178--186, 1979.

Gh. Paun. A Variant of Random Context Grammars: Semi-conditional Grammars. Theoretical Computer Science, 41:1--17, 1985.

M. Penttonen. One-Sided and Two-Sided Context in Formal Grammars. Information and Control, 25:371--392, 1974.

G. Rozenberg and A. Salomaa. The Mathematical Theory of L Systems. Academic Press, New York, 1980.

G. Rozenberg and S. H. von Solms. Priorities on Context Conditions in Rewriting Systems. Information Sciences, 14:15--50, 1978.

S. H. von Solms. Random Context Array Grammars. Information Processing, 80:59--64, 1980.

S. H. von Solms. Rewriting Systems with Limited Distance Forbidding Context. International Journal of Computer Mathematics, 15:39--49, 1984.

F. J. Urbanek. A Note on Conditional Grammars. Revue Roumaine de Mathematiques Pures at Appliquees, 28:341--342, 1983.

A. P. J. van der Walt. Random Context Grammars. In Proceedings of the Symposium on Formal Languages, 1970.