In a And\Or-graph induced by the transition function, each node of $G$ corresponds to a state $q$ belonging to a set $Q$ of the state of the Automaton, for $q$ with $\delta(q,a)=q_1*q_2$, the node is a $*$-node with two successors $q_1$ and $q_2$. For $q=\{true,false\}$, the node $q$ is a sink-node. Hence, if $*$ is $\vee$ then q is $\vee-node$, else $q$ is $\wedge-node$. My problem is this : since that the result of transition function of a alternating automata includes more nodes in $\wedge$ and $\vee$ (example: $\delta(q_0,a)=(q_1 \vee q_2) \wedge q_3 \wedge q_4 )$ ), how to build the graph And\Or on transition function of an alternating automaton?

The Graph And/Or graph is defined as following : A form of graph or tree used in problem solving and problem decomposition. The nodes of the graph represent states or goals and their successors are labeled as either AND or OR branches. The AND successors are subgoals that must all be achieved to satisfy the parent goal, while OR branches indicate alternative subgoals, any one of which could satisfy the parent goal.

Instead the alternating automata is a automata with transition function defined as following : $\delta: S \times \Sigma \longrightarrow B^+(S)$ where S are the states of the automata ,$\Sigma$ the alphabet and $B^+(S)$ is the set of positive Boolean formulas over S.

  • 1
    $\begingroup$ no one can help me on this issue, perhaps I have not explained the problem well? $\endgroup$ – kafka Dec 15 '10 at 17:10
  • 1
    $\begingroup$ I'm not sure I understand your terminology. What is an and/or graph? What is an alternating automaton? $\endgroup$ – Qiaochu Yuan Dec 18 '10 at 0:32
  • $\begingroup$ @Qiaochu Yuan:I added the definitions you asked me $\endgroup$ – kafka Dec 18 '10 at 10:36
  • $\begingroup$ I have hard time understanding a question, can you give a self-contained example of an AND/OR graph and it's corresponding alternating automaton? $\endgroup$ – Yaroslav Bulatov Dec 18 '10 at 23:08
  • $\begingroup$ the question is not switch from one graph And/Or to a alternating automata but build the graph And/or on the transition function represented by a Boolean formula.Example :Let $\delta(q_0,a)=(q1 \vee q2) \wedge q3 \wedge q4$ i want to build this graph and classify the node $q_0$ as $\wedge-node$ or $\vee-node$ $\endgroup$ – kafka Dec 19 '10 at 14:56

Your definition of the transition function $\delta$ is different than the usual definition for that of an alternating finite automaton (AFA). The usual definition is $\delta:S\times\Sigma\longrightarrow2^S$.

If you use the usual definition, the problem you mention does not occur since each state in $q\in S=(Q_\exists \cup Q_\forall)$ is either a $\vee$-node (element of $Q_\exists$) or a $\wedge$-node (element of $Q_\forall$). If $q_0$ is a $\vee$-node, then the boolean value of $q_0$ is $\bigvee_{q\in \delta(q_0,a)} q$. If $q_0$ is a $\wedge$-node, then the boolean value of $q_0$ is $\bigwedge_{q\in \delta(q_0,a)} q$. It should be clear how to construct an and-or tree from this definition.

If instead you choose to use your definition, a solution would be to add more states when presented with an example like $\delta(q,a)=((q_1 \vee q_2) \wedge q_3 \wedge q_4 )$. We can convert each state so that it does not have both $\wedge$ and $\vee$ in the boolean expression. Consider adding a new state $q_5$ such that $\delta(q_5,a)=(q_1\vee q_2)$ and amending $\delta$ so that $\delta(q,a)=(q_5 \wedge q_3 \wedge q_4 )$. Now it is clear that $q$ is a $\wedge$-node (and that $q_5$ is a $\vee$-node). This effectively aligns your transition definition with the usual definition and your problem is removed.


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.