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$

  • 4
    $\begingroup$ please define 'partitions of an automata' and 'weak alternatiing automata' or give pointers to both ? $\endgroup$ – Suresh Venkat Dec 7 '10 at 17:03
  • 3
    $\begingroup$ 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 $\endgroup$ – Suresh Venkat Dec 7 '10 at 17:16
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Dec 12 '10 at 14:24
  • $\begingroup$ I corrected the mistakes $\endgroup$ – kafka Dec 12 '10 at 15:08
  • $\begingroup$ It is easier to read if you use (i) LaTeX or (ii) a combination of Unicode and HTML. LaTeX is probably easier to write. $\endgroup$ – Tsuyoshi Ito Dec 12 '10 at 15:30

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

  • $\begingroup$ 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 $\endgroup$ – kafka Dec 9 '10 at 18:00
  • $\begingroup$ @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.” $\endgroup$ – Tsuyoshi Ito Dec 12 '10 at 23:56
  • 2
    $\begingroup$ 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}. $\endgroup$ – Tsuyoshi Ito Dec 13 '10 at 14:30
  • $\begingroup$ @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? $\endgroup$ – kafka Dec 13 '10 at 18:08
  • 3
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Dec 15 '10 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.