Konferenzpaper

Jahr der Veröffentlichung: 2005

Seiten: 423-440

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 16

Heftnummer: 3

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054105003078

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

Verlag: World Scientific Publishing

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-semidecidability, to be more precise, we show completeness for the second level of the arithmetic hierarchy for all of the aforementioned operations, except for the power operation, if the underlying alphabet contains at least two letters. The result for the power opera, tion solves an open problem stated in Theoret. Comput. Sci. 314 (2004) 445-449.

Harvard-Zitierstil: Bordihn, H., Holzer, M. and Kutrib, M. (2005) Unsolvability levels of operation problems for subclasses of context-free languages, International Journal of Foundations of Computer Science, 16(3), pp. 423-440. https://doi.org/10.1142/S0129054105003078

APA-Zitierstil: Bordihn, H., Holzer, M., & Kutrib, M. (2005). Unsolvability levels of operation problems for subclasses of context-free languages. International Journal of Foundations of Computer Science. 16(3), 423-440. https://doi.org/10.1142/S0129054105003078