Publication Details

Coincidental Extention of Scattered Context Languages

MEDUNA, A. Coincidental Extention of Scattered Context Languages. Acta Informatica, 2003, vol. 2003, no. 112, p. 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. 112, ISSN 0001-5903
Publisher
Springer Verlag
Place
Berlin
BibTeX
@article{BUT42000,
  author="Alexandr {Meduna}",
  title="Coincidental Extention of Scattered Context Languages",
  journal="Acta Informatica",
  year="2003",
  volume="2003",
  number="112",
  pages="307--314",
  issn="0001-5903"
}
Back to top