<p>If I understand you correctly, you are asking for a linear extension of the partial order induced by the partitioning of the weak alternating automaton into its maximal strictly connected components and the transitions between the states. </p>

<p>Note that the "extension of the partial order" to a total order is not unique. The process of obtaining any such total order is called topologic sorting.</p>

<p>See the following wikipedia page for details and a link to an algorithm: <a href="http://en.wikipedia.org/wiki/Partially_ordered_set" rel="noreferrer">http://en.wikipedia.org/wiki/Partially_ordered_set</a> </p>

CC BY-SA 2.5
2010-12-09T18:00:43.100Z
but the order is about the partitions and not the individual state of the automaton so I do not think that the topological sort solves the problem
kafka
CC BY-SA 2.5
2010-12-12T23:56:09.163Z
@Antony: That probably means that the question is underspecified.  In that case, please edit your question to clarify what you mean by “extend the partial order to a total order.”
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-13T14:30:29.377Z
Rereading the question and this answer, I see absolutely nothing wrong with this answer.  +1.  @Antony: Run the topological sort algorithm on the set {Q_1,…,Q_n}.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-13T18:08:35.310Z
@Tsuyoshi Ito 伊藤剛志:ok,since then the graph G representing the relationships between the elements of set {Q1,...Qn} applying the topological sort on the graph G.Right?
kafka
CC BY-SA 2.5
2010-12-13T18:21:58.640Z
@Antony: Yes, that is what I meant.  Sorry if it was not clear.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-15T17:05:45.793Z
However as I said before and thinking a bit about, the answer does not work, because if they are not comparable two partitions ,by definition that transition from the state in Qi lead to states in either the same Qi or lower one, so even if I get a total order that does not happen
kafka
CC BY-SA 2.5
2010-12-15T19:04:38.353Z
@Antony: I am afraid that you have not understood what topological sort is.  The order obtained by the topological sort is still compatible with the transition function by definition of topological sort.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-08T16:45:15.310Z
2010-12-08T16:45:15.310Z
CSStudent
<p>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?</p>

<p>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&#39; \in Q_j$ for which $s&#39;\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$
</p>

CC BY-SA 2.5
2010-12-07T17:03:05.583Z
please define 'partitions of an automata' and 'weak alternatiing automata' or give pointers to both ?
Suresh Venkat
CC BY-SA 2.5
2010-12-07T17:16:54.537Z
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
CC BY-SA 2.5
2010-12-12T14:24:46.560Z
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
CC BY-SA 2.5
2010-12-12T15:08:42.740Z
I corrected the mistakes
kafka
CC BY-SA 2.5
2010-12-12T15:30:17.420Z
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
CC BY-SA 2.5
2010-12-12T15:38:22.557Z
unfortunately I do not know how to include latex in the forum,In fact, I wrote directly to the symbols of latex in the post
kafka
CC BY-SA 2.5
2010-12-12T16:28:23.997Z
I tried to fix typos and convert math to LaTeX (enclose by dollar signs just in LaTeX), but I may have introduced errors during this.  Please check that everything is as you intended, and if not, please edit accordingly.  One thing to note: “automata” is the plural form of “automaton,” and therefore we never say “an automata,” just as we never say “a dogs.”
Tsuyoshi Ito
<fl.formal-languages><automata-theory><partial-order>
Extension of a partial order to a total of partitions of a weak alternating automaton
kafka
# Extension of a partial order to a total of partitions of a weak alternating automaton

(Asked by: username_0 on 2010-12-07)

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$

**Tags:** fl.formal-languages, automata-theory, partial-order
> **Comments:**
> **username_1**: please define 'partitions of an automata' and 'weak alternatiing automata' or give pointers to both ?  
> **username_1**: 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  
> **username_2**: 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.  
> **username_0**: I corrected the mistakes  
> **username_2**: It is easier to read if you use (i) LaTeX or (ii) a combination of Unicode and HTML.  LaTeX is probably easier to write.  
> **username_0**: unfortunately I do not know how to include latex in the forum,In fact, I wrote directly to the symbols of latex in the post  
> **username_2**: I tried to fix typos and convert math to LaTeX (enclose by dollar signs just in LaTeX), but I may have introduced errors during this.  Please check that everything is as you intended, and if not, please edit accordingly.  One thing to note: “automata” is the plural form of “automaton,” and therefore we never say “an automata,” just as we never say “a dogs.”  

---

## 1 answers

### Answer by username_3 on 2010-12-08. Score: 7 | Accepted answer

If I understand you correctly, you are asking for a linear extension of the partial order induced by the partitioning of the weak alternating automaton into its maximal strictly connected components and the transitions between the states.

Note that the "extension of the partial order" to a total order is not unique. The process of obtaining any such total order is called topologic sorting.

See the following wikipedia page for details and a link to an algorithm: <http://en.wikipedia.org/wiki/Partially_ordered_set>

> **Comments:**
> **username_0**: but the order is about the partitions and not the individual state of the automaton so I do not think that the topological sort solves the problem  
> **username_2**: @Antony: That probably means that the question is underspecified.  In that case, please edit your question to clarify what you mean by “extend the partial order to a total order.”  
> **username_2**: Rereading the question and this answer, I see absolutely nothing wrong with this answer.  +1.  @Antony: Run the topological sort algorithm on the set {Q_1,…,Q_n}.  
> **username_0**: @Tsuyoshi Ito 伊藤剛志:ok,since then the graph G representing the relationships between the elements of set {Q1,...Qn} applying the topological sort on the graph G.Right?  
> **username_2**: @Antony: Yes, that is what I meant.  Sorry if it was not clear.  
> **username_0**: However as I said before and thinking a bit about, the answer does not work, because if they are not comparable two partitions ,by definition that transition from the state in Qi lead to states in either the same Qi or lower one, so even if I get a total order that does not happen  
> **username_2**: @Antony: I am afraid that you have not understood what topological sort is.  The order obtained by the topological sort is still compatible with the transition function by definition of topological sort.  

---

