regular_language (1096B)
1 # Regular language 2 3 ## [computational_problem] 4 5 - [regular_language_membership] 6 - [approximate_membership] 7 - [dynamic_membership] 8 - [sliding_window] 9 - [regular_language_communication_complexity] 10 11 ## [regular_language_list] 12 13 - [parity] 14 15 ## [regular_language_family] 16 17 - [locally_testable_language] 18 - [regular_language_sparse]: polynomial number of words per length 19 - [regular_language_slender]: constant number of words 20 - [regular_language_thin]: at most one word 21 - [formal_language_monomial] 22 23 ## Connections 24 25 - [regular_language_communication_complexity] 26 27 ## Generalizations 28 29 - [regular_tree_language] 30 31 ## Concepts 32 33 - [star_height] 34 - arbitrarily large 35 - connection to [cycle_rank] of [automata] via [eggans_theorem] 36 - [generalized_star_height] en ajoutant [complementation] 37 - generalized star height of zero is [star_free_language] 38 - [state_complexity] 39 - [syntactic_complexity] 40 41 ## Results 42 43 - [myhill_nerode_theorem] 44 - [myhill_nerode_relation] 45 - [pumping_lemma] 46 - [regular_language_dichotomies] 47 48 See also: [automata] 49 50 Up: [formal_language], [regular] 51 52 Aliases: regular languages