Partitioning a symmetric rational relation into two asymmetric rational relations
From MaRDI portal
Publication:2177607
DOI10.1007/978-3-030-23679-3_14zbMATH Open1434.68270arXiv1903.10740OpenAlexW2965104913MaRDI QIDQ2177607FDOQ2177607
Authors: Stavros Konstantinidis, Mitja Mastnak, Juraj Šebej 
Publication date: 6 May 2020
Abstract: We consider the problem of partitioning effectively a given symmetric (and irreflexive) rational relation R into two asymmetric rational relations. This problem is motivated by a recent method of embedding an R-independent language into one that is maximal R-independent, where the method requires to use an asymmetric partition of R. We solve the problem when R is realized by a zero-avoiding transducer (with some bound k): if the absolute value of the input-output length discrepancy of a computation exceeds k then the length discrepancy of the computation cannot become zero. This class of relations properly contains all recognizable, all left synchronous, and all right synchronous relations. We leave the asymmetric partition problem open when R is not realized by a zero-avoiding transducer. We also show examples of total wordorderings for which there is a relation R that cannot be partitioned into two asymmetric rational relations such that one of them is decreasing with respect to the given word-ordering.
Full work available at URL: https://arxiv.org/abs/1903.10740
Recommendations
Cited In (1)
This page was built for publication: Partitioning a symmetric rational relation into two asymmetric rational relations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2177607)
