wiki_research

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

testing_if_automatic_relation_is_recognizable (283B)

      1 # Testing if automatic relation is recognizable
      2 
      3 The [CD_membership_problem] for C=[automatic_relations] and D=[recognizable_relations] is [PSPACE_complete]
      4 - cf [morvan2025homomorphism] Proposition VII.1.9
      5 
      6 Up: [CD_membership_problem], [automatic_relation], [recognizable_relation]