Journalartikel

Jahr der Veröffentlichung: 2007

Seiten: 1271-1282

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 18

Heftnummer: 6

ISSN: 0129-0541

DOI Link: https://doi.org/10.1142/S0129054107005315

Verlag: World Scientific Publishing

Abstract: 
We introduce a new type of finite copying parallel rewriting system, i. e., grammars with linked nonterminals, which extend the generative capacity of context-free grammars. They can be thought of as having sentential forms where some instances of a nonterminal may be linked. The context-free-like productions replace a nonterminal together with its connected instances. New links are only established between symbols of the derived subforms. A natural limitation is to bound the degree of synchronous rewriting. We present an infinite degree hierarchy of separated language families with the property that degree one characterizes the family of regular and degree two the family of context-free languages. Furthermore, the hierarchy is a refinement of the known hierarchy of finite copying rewriting systems. Several closure properties known from equivalent systems are summarized.

Harvard-Zitierstil: Klein, A. and Kutrib, M. (2007) Context-free grammars with linked nonterminals, International Journal of Foundations of Computer Science, 18(6), pp. 1271-1282. https://doi.org/10.1142/S0129054107005315

APA-Zitierstil: Klein, A., & Kutrib, M. (2007). Context-free grammars with linked nonterminals. International Journal of Foundations of Computer Science. 18(6), 1271-1282. https://doi.org/10.1142/S0129054107005315