Refinement problems for recognizable relations

Given a relation on the states of a finite deterministic automaton, is it possible to define a congruence of finite index, refining this relation and verifying a given property? This general problem came up while searching for an algebraic solution to the register minimization problem for streaming string transducers realizing rational functions between words. It is also linked to the problem of separation of regular languages. In this talk, I will present different equivalent forms of the refinement problem and show its connection with other well known problems. I will also present an interesting tool, which is part of an ongoing work on the subject, that can describe the possible solutions of this problem. Contributed talk given by Yahia Idriss Benalioua

Authors

• Yahia Idriss Benalioua

Keywords

No keywords are indexed for this paper.