wiki_research

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

rec_membership_problem (421B)

      1 # Rec membership problem
      2 
      3 The [cd_membership_problem] asking, given a [rational_relation], whether it is [relation_equivalent] to a [recognizable_relation]
      4 
      5 [morvan2025homomorphism] p233:
      6 - The problem is [undecidable] in general
      7 - But [decidable] given a [deterministic_rational_relation]
      8 - It is [PSPACE_complete] given an [automatic_relation]
      9 
     10 Up: [cd_membership_problem], [rational_relation], [recognizable_relation]