Conference paper
Authors list: Bordihn, H; Holzer, M; Kutrib, M
Editor list: Domaratzki, M; Okhotin, A; Salomaa, K; Yu, S
Publication year: 2005
Pages: 68-79
Journal: Lecture notes in computer science
Volume number: 3317
ISSN: 0302-9743
ISBN: 3-540-24318-6
eISSN: 1611-3349
Conference: 9th International Conference on Implementation and Application of Automata
Publisher: Springer
Title of series: 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].
Citation Styles
Harvard Citation style: 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 Citation style: 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.
