wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

context_free_grammar_finite_index (1110B)

      1 # Finite index CFG
      2 
      3 Defined in [salomaa1973formal] Chapter VI section 10: A [CFG] G having a bound k such that every word in the [language_accepted_by] G has a [derivation] with [derivation_index] at most k
      4 
      5 Equivalent characterization:
      6 - non-expansive CFGs*, i.e., those where you cannot rewrite a nonterminal into
      7   multiple copies of itself
      8 - closing the CFLs under substitution, where closing a family under
      9   substitution means closing under the operation where you replace each letter
     10   by a language of the family (cf [salomaa1973formal]): these are called the
     11   "quasi-rational languages" ([autebert1997context], [shemetova2024rational])
     12 
     13 Strictly generalizes:
     14 - [ultralinear_CFGs]
     15 - [superlinear_CFGs]
     16 
     17 Variant:
     18 - [derivation_bounded_set], i.e., for a [CFG], the sublanguage of [derivation_trees] of bounded [derivation_tree_index]
     19   - defined in [ginsburg1968derivation]
     20   - also discussed in [esparza2016brief] in connection with [Strahler_number]
     21 
     22 Up: [context_free_grammar]
     23 
     24 Aliases: finite index CFG, finite index CFGs, quasirational, quasirational language, non-expansive CFG, non expansive CFG