Paper Info
Title
Partitioning a Symmetric Rational Relation into Two Asymmetric Rational Relations.
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.
Year
Venue
Field
2019
CIAA
Transducer,Partition problem,Discrete mathematics,Embedding,Absolute value,Partition (number theory),Mathematics,Reflexive relation,Computation
DocType
Volume
Citations 
Journal
abs/1903.10740
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Stavros Konstantinidis128331.10
Mitja Mastnak221.07
Juraj Sebej3245.25