automatic_relation (840B)
1 # Automatic relation 2 3 Relation on words defined by [automaton]: you read two words with a padding 4 symbol, i.e., [automaton_synchronous] 5 6 - Paper about this: [barcelo2023separating] 7 - [automatic_relation_algebra] 8 9 Example: the [infinite_binary_tree] is an automatic relation 10 11 Special case: [recognizable_relations] 12 13 Generalization: [deterministic_rational_relations], [rational_relations] 14 15 [CD_membership_problem]: [testing_if_automatic_relation_is_recognizable] 16 17 It is an [open_problem] whether the [computational_problem] of deciding [formal_language_separation] of automatic relations by a [recognizable_relation] is a [decidable] problem 18 19 [automatic_relations_FO_definable] 20 21 Up: [automata], [relation] 22 23 See also: [automatic_structure], [automatic_graph], [sequence_automatic], [post_correspondence_problem] 24 25 Aliases: automatic relations