Publication Details

Coincidental Extention of Scattered Context Languages

MEDUNA Alexander. Coincidental Extention of Scattered Context Languages. Acta Informatica, vol. 2003, no. 39, pp. 307-314. ISSN 0001-5903.
Czech title
Shodné rozšíření jazyků s rozptýleným kontextem
Type
journal article
Language
english
Authors
Keywords

coincidental extention; scattered context languages

Abstract

Coincidental extention of scattered context languages is introduced and discussed.

Annotation

For a symbol, #, and a string, x = a_1 a_2 \ldots a_{n-1} a_n, any string of the form #^i a_1 #^i a_2 #^i \ldots #^i a_n-1 #^i a_n #^i, where i \geq 0, is a coincidental #-extension of x. A language, K, is a coincidental #-extension of L if every string o K represents a coi ncidental extension of a string in L and the deletion of all #s in K results in L. This paper proves that for every recursively enumerable language, E, there exists a propagating scattered context language that represents a coincidental extension of E.

Published
2003
Pages
307-314
Journal
Acta Informatica, vol. 2003, no. 39, ISSN 0001-5903
Book
Acta Informatica
Publisher
Springer Verlag
Place
Berlin, DE
BibTeX
@ARTICLE{FITPUB7165,
   author = "Alexander Meduna",
   title = "Coincidental Extention of Scattered Context Languages",
   pages = "307--314",
   booktitle = "Acta Informatica",
   journal = "Acta Informatica",
   volume = 2003,
   number = 39,
   year = 2003,
   location = "Berlin, DE",
   publisher = "Springer Verlag",
   ISSN = "0001-5903",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7165"
}
Back to top