Institut für Informatik und Computational Science
Refine
Has Fulltext
- no (21) (remove)
Year of publication
- 2020 (21) (remove)
Document Type
- Article (19)
- Doctoral Thesis (1)
- Other (1)
Language
- English (21)
Is part of the Bibliography
- yes (21)
Keywords
- Answer Set Programming (2)
- Fault tolerance (2)
- answer set programming (2)
- Android hybrid apps (1)
- Conformant Planning (1)
- DMR (1)
- DNA hairpin formation (1)
- Double cell upsets (DCUs) (1)
- EDC (1)
- Epistemic Logic Programs (1)
We study the derivational complexity of context-free and context-sensitive grammars by counting the maximal number of non-regular and non-context-free rules used in a derivation, respectively. The degree of non-regularity/non-context-freeness of a language is the minimum degree of non-regularity/non-context-freeness of context-free/context-sensitive grammars generating it. A language has finite degree of non-regularity iff it is regular. We give a condition for deciding whether the degree of non-regularity of a given unambiguous context-free grammar is finite. The problem becomes undecidable for arbitrary linear context-free grammars. The degree of non-regularity of unambiguous context-free grammars generating non-regular languages as well as that of grammars generating deterministic context-free languages that are not regular is of order Omega(n). Context-free non-regular languages of sublinear degree of non-regularity are presented. A language has finite degree of non-context-freeness if it is context-free. Context-sensitive grammars with a quadratic degree of non-context-freeness are more powerful than those of a linear degree.