Note on Partitioning of a Symmetric Rational Relation into Two Asymmetric Rational Relations
RNDr. Juraj Šebej, PhD.
Ústav informatiky, PF UPJŠ
Problem can be stated as follows: "Let $R$ be rational, irreflexive, symmetric relation. Are there rational, asymmetric, relations $R_1$ and $R_2$ such that $R$ is equal to $R_1 \cup R_2$." This problem is motivated by a method of embedding an $R$-independent language into one that is maximal $R$-independent, which requires to use an asymmetric partition of $R$ as well as $R_1$ and $R_2$ are transitive relations. Relation $R$ represents property of language, therefore motivation can be restated as answer to question if language is prefix-free, suffix-free or it satisfies any 3-independence. We answer this problem for some classes of rational relations but general case is still open.