Publication Details

Uniform Generation of Languages by Scattered Context Grammars

MEDUNA Alexander. Uniform Generation of Languages by Scattered Context Grammars. Fundamenta Informaticae, vol. 2001, no. 45, pp. 231-235. ISSN 0169-2968.

Czech title

Jednotné generování jazyků gramatikami s rozptýleným kontextem

Type

journal article

Language

english

Authors

Meduna Alexander, Doc. RNDr., CSc. (DCSE FEECS BUT)

Keywords

uniform generation, scattered context grammars

Abstract

This paper demonstrates a uniform permutation-based generation of languages by using scattered context grammars.

Annotation

The present paper discusses the uniform generation of languages by scattered context grammars. More specifically, it demonstrates that every recursively enumerable language can be generated by a scattered context grammar, G, so that every sentential form in a generation of a sentence has the form y_1\ldots y_m i, where u is a terminal word and each y_i is a permutation either of two equally long words, z_1 \in \{A, B, C\}^* and z_2 \in \{ A, B, D\}^*, where A, B, C, and D are G's nonterminals. Then, it presents an analogical result so that u precedes y_1\ldots y_m.

Published

2001

Pages

231-235

Journal

Fundamenta Informaticae, vol. 2001, no. 45, ISSN 0169-2968

Book

Fundamenta informaticae

Publisher

IOS Press

Place

Warszawa, PL

BibTeX

@ARTICLE{FITPUB6184,
   author = "Alexander Meduna",
   title = "Uniform Generation of Languages by Scattered Context Grammars",
   pages = "231--235",
   booktitle = "Fundamenta informaticae",
   journal = "Fundamenta Informaticae",
   volume = 2001,
   number = 45,
   year = 2001,
   location = "Warszawa, PL",
   ISSN = "0169-2968",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/6184"
}