Journalartikel

Jahr der Veröffentlichung: 2017

Seiten: 122-137

Zeitschrift: Theoretical Computer Science

Bandnummer: 682

ISSN: 0304-3975

eISSN: 1879-2294

Open Access Status: Bronze

DOI Link: https://doi.org/10.1016/j.tcs.2017.02.002

Verlag: Elsevier

Abstract: 
We investigate chop operations, which can be seen as generalized concatenation. For several language families of the Chomsky hierarchy we prove (non)closure properties under chop operations and incomparability to the family of languages that are the chop of two regular languages. We also prove non-closure of that language family under Boolean operations and closure under reversal. Further, the representation of a regular language as the chop of two regular expressions can be exponentially more succinct than its regular expression. By considering the chop of two linear context-free languages we already obtain language families that have non-semi-decidable problems such as emptiness or finiteness. (C) 2017 Elsevier B.V. All rights reserved.

Harvard-Zitierstil: Holzer, M., Jakobi, S. and Kutrib, M. (2017) The chop of languages, Theoretical Computer Science, 682, pp. 122-137. https://doi.org/10.1016/j.tcs.2017.02.002

APA-Zitierstil: Holzer, M., Jakobi, S., & Kutrib, M. (2017). The chop of languages. Theoretical Computer Science. 682, 122-137. https://doi.org/10.1016/j.tcs.2017.02.002