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"
}