Seminár Ústavu informatiky


Note on Partitioning of a Symmetric Rational Relation into Two Asymmetric Rational Relations

RNDr. Juraj Šebej, PhD.

31. októbra 2018 (streda) o 12:45
SJ2S07 (3.16T), 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.