wiki_research

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

formal_language_separation (517B)

      1 # Formal language separation
      2 
      3 [Computational_problem] parameterized by [formal_language_classes] C and C':
      4 Given two [formal_languages] L1 and L2 that are disjoint in a class C
      5 a [formal_language] L in class C' separates them if L1 subseteq L and L cap L2 is empty
      6 
      7 [Formal_language_separation_problem]
      8 
      9 generalization to multiple languages: [formal_language_covering]
     10 - cf [place2018covering]
     11 
     12 Cases:
     13 - [rat_rec_separability]
     14 - [aut_rec_separability]
     15 
     16 See also: [barcelo2023separating]
     17 
     18 Up: [formal_language_theory]