wiki_research

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

context_free_grammar_ultralinear (539B)

      1 # Ultralinear CFG
      2 
      3 A [CFG] where there is a bound on the maximal number of [nonterminals] that can occur in any [derivation], i.e., where the [derivation_index] of all [derivations] is bounded
      4 
      5 Can be seen in terms of [PDAs] via the notion of [PDA_finite_turn], studied in [ginsburg1966finite]
      6 
      7 Special cases:
      8 - [linear_CFGs]
      9 - [metalinear_CFGs]
     10 
     11 Generalization:
     12 - [finite_index_CFGs]
     13 
     14 Up: [context_free_grammar]
     15 
     16 See also: [context_free_grammar_finite_index], [context_free_grammar_metalinear]
     17 
     18 Aliases: ultralinear CFG, ultralinear CFGs