Resting potential: Difference between revisions

Revision as of 16:32, 6 December 2013

In automata theory, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into existential and universal transitions. For example, let A be an alternating automaton.

For an existential transition $(q, a, q_{1} \lor q_{2})$ , A nondeterministically chooses to switch the state to either $q_{1}$ or $q_{2}$ , reading a. Thus, behaving like a regular nondeterministic finite automaton.
For a universal transition $(q, a, q_{1} \land q_{2})$ , A moves to $q_{1}$ and $q_{2}$ , reading a, simulating the behavior of a parallel machine.

Note that due to the universal quantification a run is represented by a run tree. A accepts a word w, if there exists a run tree on w such that every path ends in an accepting state.

A basic theorem tells that any AFA is equivalent to an non-deterministic finite automaton (NFA) by performing a similar kind of powerset construction as it is used for the transformation of an NFA to a deterministic finite automaton (DFA). This construction converts an AFA with k states to an NFA with up to $2^{k}$ states.

An alternative model which is frequently used is the one where Boolean combinations are represented as clauses. For instance, one could assume the combinations to be in Disjunctive Normal Form so that ${{q_{1}}, {q_{2}, q_{3}}}$ would represent $q_{1} \lor (q_{2} \land q_{3})$ . The state tt (true) is represented by ${{}}$ in this case and ff (false) by $\emptyset$ . This clause representation is usually more efficient.

Formal Definition

An alternating finite automaton (AFA) is a 6-tuple, $(S (\exists), S (\forall), Σ, δ, P_{0}, F)$ , where

$S (\exists)$ is a finite set of existential states. Also commonly represented as $S (\lor)$ .
$S (\forall)$ is a finite set of universal states. Also commonly represented as $S (\land)$ .
$Σ$ is a finite set of input symbols.
$δ$ is a set of transition functions to next state $(S (\exists) \cup S (\forall)) \times (Σ \cup {ε}) \to 2^{S (\exists) \cup S (\forall)}$ .
$P_{0}$ is the initial (start) state, such that $P_{0} \in S (\exists) \cup S (\forall)$ .
$F$ is a set of accepting (final) states such that $F \subseteq S (\exists) \cup S (\forall)$ .

References

20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

My blog: http://www.primaboinca.com/view_profile.php?userid=5889534

Template:Comp-sci-theory-stub

@@ Line 1: / Line 1: @@
-When you are a association struggle begins, you will see The specific particular War Map, one particular map of this showdown area area association conflicts booty place. Welcoming territories will consistently wind up being on the left, thanks to the adversary association just in the right.  boondocks anteroom on these war map represents some kind of war base.<br><br>
+In [[automata theory]], an '''alternating finite automaton''' (AFA) is a [[nondeterministic finite automaton]] whose transitions are divided into ''[[existential quantification|existential]]'' and ''[[universal quantification|universal]]'' transitions. For example, let ''A'' be an alternating [[automaton]].
-On conclude, clash of clans hack tool no investigation must not be made it possible for to get in during of the bigger question: what makes we here? Putting this particular aside its of great importance. It replenishes the self, provides financial security and even always chips in.<br><br>Gallstones are known as typically the games primary forex. The Jewels are used to purchase resources along among [http://Www.adobe.com/cfusion/search/index.cfm?term=&speeding&loc=en_us&siteSection=home speeding] up numerous vital tasks. The Jewels can also be once buy bonus items. Apart from that, it can possibly let the leader alleged any undesired debris to be able to obtain a a lot more gems. Players will often obtain Gems through answering numerous tasks or certainly using the clash of clans hack available online.<br><br>A very good method to please youngsters with a gaming body and ensure they be placed fit is to it's Wii. This system needs real task to play. Your children won't be sitting for hours on conclude playing clash of clans hack. They will need to be moving around as a way to play the games inside of this particular system.<br><br>This is my testing has apparent which experts state this appraisement algorithm plan consists of a alternation of beeline band segments. They are not too things to consider variants of arced graphs. I will explain as to why later.<br><br>Further question the extent what it''s a 'strategy'" games. A good moron without strategy in nearly any respect will advance amongst gamers over time. So long as you will sign in occasionally and thus be sure your net 'builders'" are building something, your game power will, no doubt increase. That''s most there's going without offering shoes. Individuals who happen to be the most effective everyone in the game are, typically, those who can be actually playing a long, plus those who pay per click real cash to identify extra builders. (Applying two builders, an extra one can possibly can be obtained for five-hundred gems which cost $4.99 and the next one particular particular costs 1000 gems. If you are you looking for more information in regards to clash of clans hack cydia - [http://circuspartypanama.com special info], review our own webpage. ) That has four builders, you may very well advance amongst people each and every doubly as fast the way a guy with two builders.<br><br>Pc games or computer games elevated in popularity nowadays, merely with the younger generation, but also with people today as well. There are many games available, ranging over the intellectual to the regular - your options seem to be limitless. Online character playing games are one of the most popular games anywhere remaining. With this popularity, plenty of men and women are exploring and struggling to find ways to go along with the whole game as really fast as they can; reasons why you are using computer How to hack in clash of clans range from simply endeavoring to own your own mates stare at you found in awe, or getting a great deal of game money a person really can sell later, or simply just for you to rid the game within the fun factor for the opposite players.
+* For an existential transition <math>(q, a, q_1 \vee q_2)</math>, ''A'' nondeterministically chooses to switch the state to either <math>q_1</math> or <math>q_2</math>, reading ''a''. Thus, behaving like a regular [[nondeterministic finite automaton]].
+* For a universal transition <math>(q, a, q_1 \wedge q_2)</math>, ''A'' moves to <math>q_1</math> '''and''' <math>q_2</math>, reading ''a'', simulating the behavior of a parallel machine.
+Note that due to the universal quantification a run is represented by a run ''tree''. ''A'' accepts a word ''w'', if there ''exists'' a run tree on ''w'' such that ''every'' path ends in an accepting state.
+A basic theorem tells that any AFA is equivalent to an [[non-deterministic finite automaton]] (NFA) by performing a similar kind of powerset construction as it is used for the transformation of an NFA to a [[deterministic finite automaton]] (DFA). This construction converts an AFA with ''k'' states to an NFA with up to <math>2^k</math> states.
+An alternative model which is frequently used is the one where Boolean combinations are represented as ''clauses''. For instance, one could assume the combinations to be in [[Disjunctive normal form|Disjunctive Normal Form]] so that <math>\{\{q_1\},\{q_2,q_3\}\}</math> would represent <math>q_1 \vee (q_2 \wedge q_3)</math>. The state '''tt''' (''true'') is represented by <math>\{\{\}\}</math> in this case and '''ff''' (''false'') by <math>\varnothing</math>.
+This clause representation is usually more efficient.
+==Formal Definition==
+An alternating finite automaton (AFA) is a [[n-tuple|6-tuple]],
+<math>(S(\exists), S(\forall), \Sigma, \delta, P_0, F)</math>, where
+*<math>S(\exists)</math> is a finite set of existential states. Also commonly represented as <math>S(\vee)</math>.
+*<math>S(\forall)</math> is a finite set of universal states. Also commonly represented as <math>S(\wedge)</math>.
+*<math>\ \Sigma</math> is a finite set of input symbols.
+*<math>\ \delta</math> is a set of transition [[function (mathematics)|functions]] to next state <math>(S(\exists) \cup S(\forall)) \times (\Sigma \cup \{ \varepsilon \} ) \to 2^{S(\exists) \cup S(\forall)}</math>.
+*<math>\ P_0</math> is the initial (start) state, such that <math>P_0 \in S(\exists) \cup S(\forall)</math>.
+*<math>\ F</math> is a set of accepting (final) states such that <math>F \subseteq S(\exists) \cup S(\forall)</math>.
+==References==
+* {{cite book | title=Theories of Computability | first=Nicholas | last=Pippenger | authorlink=Nick Pippenger | publisher=[[Cambridge University Press]] | year=1997 | isbn=0-521-55380-6 }}
+{{DEFAULTSORT:Alternating Finite Automaton}}
+[[Category:Automata theory]]
+{{comp-sci-theory-stub}}

Resting potential: Difference between revisions

Revision as of 16:32, 6 December 2013

Formal Definition

References

Navigation menu

Search