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

## RNDr. Juraj Šebej, PhD. Ústav informatiky, PF UPJŠ

14. novembra 2018 (streda) o 12:45
SJ2S07 (3.16T), PF UPJŠ

## Abstrakt

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.