Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

Operational complexity and right linear grammars

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
  • معلومة اضافية
    • بيانات النشر:
      Springer Science and Business Media LLC, 2021.
    • الموضوع:
      2021
    • نبذة مختصرة :
      For a regular language L, let $${{\,\mathrm{Var}\,}}(L)$$ Var ( L ) be the minimal number of nonterminals necessary to generate L by right linear grammars. Moreover, for natural numbers $$k_1,k_2,\ldots ,k_n$$ k 1 , k 2 , … , k n and an n-ary regularity preserving operation f, let $$g_f^{{{\,\mathrm{Var}\,}}}(k_1,k_2,\ldots ,k_n)$$ g f Var ( k 1 , k 2 , … , k n ) be the set of all numbers k such that there are regular languages $$L_1,L_2,\ldots , L_n$$ L 1 , L 2 , … , L n such that $${{\,\mathrm{Var}\,}}(L_i)=k_i$$ Var ( L i ) = k i for $$1\le i\le n$$ 1 ≤ i ≤ n and $${{\,\mathrm{Var}\,}}(f(L_1,L_2,\ldots , L_n))=k$$ Var ( f ( L 1 , L 2 , … , L n ) ) = k . We completely determine the sets $$g_f^{{{\,\mathrm{Var}\,}}}$$ g f Var for the operations reversal, Kleene-closures $$+$$ + and $$*$$ ∗ , and union; and we give partial results for product and intersection.
    • ISSN:
      1432-0525
      0001-5903
    • Rights:
      OPEN
    • الرقم المعرف:
      edsair.doi...........4e6f6009e4f3c2f5e4a254fde94c3b41