Paper Info
Title
Unsolvability Levels Of Operation Problems For Subclasses Of Context-Free Languages
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.
Year
DOI
Venue
2005
10.1142/S0129054105003078
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Keywords
Field
DocType
linear and deterministic context-free languages, algorithmic undecidability, arithmetical hierarchy, operations on languages, root and power operation
Discrete mathematics,Context-free language,Combinatorics,Formal language,Nested word,Abstract family of languages,Deterministic pushdown automaton,Deterministic context-free language,Cone (formal languages),Third-generation programming language,Mathematics
Journal
Volume
Issue
ISSN
16
3
0129-0541
Citations 
PageRank 
References 
4
0.53
11
Authors
3
Name
Order
Citations
PageRank
Henning Bordihn116731.96
Markus Holzer213812.30
Martin Kutrib377889.77