| In this paper, the conjugacy problem on prefix codes and synchronizing bounded partially ordered automata are considered. As the main results, Conway Problem is confirmed for rational prefix codes, while (?)ern(?) Conjecture is ensured for bounded partially ordered automata.The commutativity equation XY=YXis the simplest equation on formal languages.Concerning this equaltion, there is an open problem:Conway's Problem: Is the centralizer of a rational language rational?The cojugate equation XZ=ZY is a generalization of the commutativity equation. In fact, it had ever played a fundamental role in the consideration on some algebra systems such as groups. In this paper, the solutions of conjugacy equation on prefix codes is described as below: if X and Y are prefix codes and Z is a non-empty language sastisfying the condition XZ=ZY, then there exists a prefix set P and Q such that X=(PQ)~k, Y=(QP)~k and Z=(PQ)~IP for some k ?N~+ and a non-empey set I(?)N. As a conseuqnece of such a result, it is found that the centralizer of a prefix code is rational.An automaton is synchronizing if all of its states can be transited to a single state under the action of some word. The researches on synchronizing automata are focused on the following conjecture:(?)ern(?) Conjecture: Each n-state synchronizing automaton possess a synchronizing word of length at most (n-1)~2.Aiming at this conjecture, bounded partially ordered automata are defined. It is shown that the shortest synchronizing words of an n-state bounded partially ordered automaton are of length at most n-1. Also, an algorithm is designed for checking the synchronization and finding the shortest synchronizing words of bounded partially ordered automata. The above results mean that synchronizing bounded partially ordered automata (especially, lattice ordered automata) satisfy (?)ern(?) conjecture.Furthermore, the relationship of monotonic automata, generalized monotonic automata, bounded partially ordered automata are also discussed. |
PDF Full Text Request