wiki_research

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

rational_relation_deterministic (844B)

      1 # Deterministic rational relation
      2 
      3 Special case: [automatic_relation]
      4 
      5 Generalization: [rational_relation]
      6 
      7 The [rational_relations] recognized by a [multitape_automaton] which is [deterministic_automaton] and where, on every state, we know precisely which set of [heads] will move. This can be called a [deterministic_multitape_automaton]
      8 
      9 Must also add a fresh padding symbol to the right of words
     10 
     11 The [emptiness_problem] on the [intersections] of two dynamic rational relations is [undecidable] by reduction from [PCP], cf [morvan2025homomorphism] p209
     12 
     13 The [inclusion_problem] for [deterministic_multitape_automata] is [undecidable] but the [automaton_equivalence_problem] is [decidable], cf [morvan2025homomorphism] p209
     14 
     15 
     16 Up: [rational_relation], [determinism]
     17 
     18 Aliases: deterministic rational relation, deterministic rational relations