Tree-controlled grammars with restrictions placed upon cuts and paths

Title:

Tree-controlled grammars with restrictions placed upon cuts and paths

Creator:

Koutný, Jiří and Meduna, Alexander

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:a1f605ed-a084-469f-bb6c-70c5e9117efc
uuid:a1f605ed-a084-469f-bb6c-70c5e9117efc

Subject:

context-free grammars, tree-controlled grammars, restricted derivation trees, paths, cuts, and language families

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

First, this paper discusses tree-controlled grammars with root-to-leaf derivation-tree paths restricted by control languages. It demonstrates that if the control languages are regular, these grammars generate the family of context-free languages. Then, in a similar way, the paper introduces tree-controlled grammars with derivation-tree cuts restricted by control languages. It proves that if the cuts are restricted by regular languages, these grammars generate the family of recursively enumerable languages. In addition, it places a binary-relation-based restriction upon these grammars and demonstrate that this additional restriction does not affect the generative power of these grammars.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

[165]-175

Source:

Kybernetika | 2012 Volume:48 | Number:1

Harvested from:

CDK

Metadata only:

false