Konferenzpaper

Herausgeberliste: Domaratzki, M; Okhotin, A; Salomaa, K; Yu, S

Jahr der Veröffentlichung: 2005

Seiten: 68-79

Zeitschrift: Lecture notes in computer science

Bandnummer: 3317

ISSN: 0302-9743

ISBN: 3-540-24318-6

eISSN: 1611-3349

Konferenz: 9th International Conference on Implementation and Application of Automata

Verlag: Springer

Serientitel: Lecture Notes in Computer Science

Abstract: 
We investigate the operation problem for linear and deterministic context-free languages: Fix an operation on formal languages. Given linear (deterministic, respectively) context-free languages, is the application of this operation to the given languages still a linear (deterministic, respectively) context-free language? Besides the classical operations, for which the linear and deterministic context-free languages are not closed, we also consider the recently introduced root and power operation. We show non-semi-decidability for all of the aforementioned operations, if the underlying alphabet contains at least two letters. The non-semi-decidability and thus the undecidability for the power operation solves an open problem stated in [4].

Harvard-Zitierstil: Bordihn, H., Holzer, M. and Kutrib, M. (2005) Some non-semi-decidability problems for linear and deterministic context-free languages, Lecture notes in computer science (Schriftenreihe), 3317, pp. 68-79

APA-Zitierstil: Bordihn, H., Holzer, M., & Kutrib, M. (2005). Some non-semi-decidability problems for linear and deterministic context-free languages. Lecture notes in computer science (Schriftenreihe). 3317, 68-79.