# Extension of a partial order to a total of partitions of a weak alternating automaton

My problem is this: given a weak alternating automaton and its partitions, and given a partial order on these partitions, how do we extend the partial order to a total order?

The partitions of weak alternating automaton are defined as follows: Let $A(\Sigma,Q,q_0,\delta,\alpha)$ where $\alpha$ represents the acceptance condition, $Q$ is the set of states, and $q_0$ is the initial state. A weak alternating automaton is an alternating Buchi tree automaton in which exists a partition of the set $Q$ into disjoint sets $Q_1,\dotsc,Q_n$, such that for each set $Q_i$, either $Q_i\subseteq\alpha$ (in which case $Q_i$ is an accepting set) or $Q_i\cap\alpha=\varnothing$ (in which case $Q_i$ is a rejecting set). In addition exists a partial order $\leq$ on the collection of $Q_i$, such that for every $s \in Q_i$ and $s' \in Q_j$ for which $s'\in\delta(s,a)$ we have $Q_j \leq Q_i$. Thus, transition from the state in $Q_i$ lead to states in either the same $Q_i$ or lower one.Hence , given the partial order defined above, how to turn this order in a total order $Q_1 \leq Q_2 \leq ... \leq Q_n$

• please define 'partitions of an automata' and 'weak alternatiing automata' or give pointers to both ? – Suresh Venkat Dec 7 '10 at 17:03
• thanks for the link, but wouldn't it be easier to merely add it in ? you're more likely to get answers that way. Moreover, it's still not clear what a partition of an automaton is – Suresh Venkat Dec 7 '10 at 17:16
• I tried to tidy the definition paragraph, but I gave up because it was incomprehensible to me. For example, the following part does not make sense to me at all: “either Q_i is subset of \alpha in which case Q_i is tha accepting set, or Q_i intersected \alpha is empty , in which case Q_i is the accepting set.” You are claiming that Q_i is the accepting set in both cases. Probably you should reread what you posted and correct any mistakes and typos. – Tsuyoshi Ito Dec 12 '10 at 14:24
• I corrected the mistakes – kafka Dec 12 '10 at 15:08
• It is easier to read if you use (i) LaTeX or (ii) a combination of Unicode and HTML. LaTeX is probably easier to write. – Tsuyoshi Ito Dec 12 '10 at 15:30