On external contextual grammars with subregular selection languages.

Tools

Dassow, Jürgen, Manea, Florin and Truthe, Bianca (2012) On external contextual grammars with subregular selection languages. Theoretical Computer Science, 449 . pp. 64-73. DOI 10.1016/j.tcs.2012.04.008.

This is the latest version of this item.

[thumbnail of dmt-contextualsubreg-tcs-rev.pdf]
Preview
 Text
dmt-contextualsubreg-tcs-rev.pdf
Download (335kB) | Preview

Supplementary data:

Abstract

In this paper, we study the power of external contextual grammars with selection languages from subfamilies of the family of regular languages. If we consider families $F_n$ which are obtained by restriction to $n$ states or nonterminals or productions or symbols to accept or to generate regular languages, we obtain four infinite hierarchies of the corresponding families of languages generated by external contextual grammars with selection languages in $F_n$. Moreover, we give some results on the power of external contextual grammars with regular commutative, regular circular, definite, suffix-free, ordered, combinational, nilpotent, and union-free selection languages.

Document Type: Article
Keywords: Formal languages, External contextual grammars, Subregular selection languages.
Research affiliation: Kiel University
Refereed: Yes
Publisher: Elsevier
Date Deposited: 16 Apr 2013 14:31
Last Modified: 15 Mar 2018 04:47
URI: https://oceanrep.geomar.de/id/eprint/20780

Available Versions of this Item

Actions (login required)

View Item View Item