A partial automaton is a system M=(Q, A, δ ) with Q being the finite nonempty set of states, A being a finite nonempty alphabet and δ being a partial function from Q×A to Q. (meaning something like "if I'm in q and get the symbol a on input, I will be in q'." if δ(q,a)=q' and "if I'm in q and get the symbol a on input, I'm stuck." if δ(q,a) is undefined). Instead of δ(q,a) we often write simply qa.
The action is extended to words as usual, setting qua := (qu)a. Of course if qu is undefined, then so is qua .
A word w is a directing word of M if pw=qw is defined for each state p,q in Q. In other words, if M gets w on input, no matter in which state M is, after processing w it will be in a fixed state. M is called directable if it possesses at least one directing word.
The question can be stated as follows:
Given an n-state directable partial automaton, how long can be its shortest directing word at most?
Known bounds:
- For each n there exists a directable n-state partial automaton whose shortest directing word has length Ω(3n/3). See P.V. Martyugin, Lower bounds for length of carefully synchronizing words, Presented at Satellite Workshop on Words and Automata of the International Computer Science Symposium in Russia (CSR'06), St. Petersburg, 2006. Basically a ternary counter is simulated.
- Every n-state directable partial automaton possesses a directing word of length O(n2·4n/3). See here: http://dl.acm.org/citation.cfm?id=1570791
My intuition says 3n/3 is closer to the solution..
No comments:
Post a Comment