@article{BordihnMitrana2020,
  author    = {Bordihn, Henning and Mitrana, Victor},
  title     = {On the degrees of non-regularity and non-context-freeness},
  series = {Journal of computer and system sciences},
  volume    = {108},
  journal   = {Journal of computer and system sciences},
  publisher = {Elsevier},
  address   = {San Diego, Calif. [u.a.]},
  issn      = {0022-0000},
  doi       = {10.1016/j.jcss.2019.09.003},
  pages     = {104 -- 117},
  year      = {2020},
  abstract  = {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.},
  language  = {en}
}