Journal article

Publication year: 2007

Pages: 1271-1282

Journal: International Journal of Foundations of Computer Science

Volume number: 18

Issue number: 6

ISSN: 0129-0541

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

Publisher: 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 Citation style: 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 Citation style: 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