https://en.formulasearchengine.com/index.php?title=St%C3%B8rmer_number&feed=atom&action=historyStørmer number - Revision history2024-03-29T13:39:42ZRevision history for this page on the wikiMediaWiki 1.42.0-wmf.5https://en.formulasearchengine.com/index.php?title=St%C3%B8rmer_number&diff=21778&oldid=preven>Maxal at 16:50, 11 October 20132013-10-11T16:50:42Z<p></p>
<p><b>New page</b></p><div>In [[computer science]], a '''pebble automaton''' is an extension of [[tree walking automaton|tree walking automata]] which allows the automaton to use a finite amount of "pebbles", used for marking tree node{{fact|date=January 2011}}. The result is a model stronger than ordinary tree walking automata, but still strictly weaker than [[tree automaton|branching automata]].<br />
<br />
==Definitions==<br />
<br />
A pebble automaton is a tree walking automaton with an additional finite set of fixed size containing pebbles, identified with <math>\{ 1, 2, \dots, n \}</math>. Besides ordinary actions, an automaton can put a pebble at a currently visited node, lift a pebble from the currently visited node and perform a test "is the i-th pebble present at the current node?". There is an important stack restriction on the order in which pebbles can be put or lifted - the i+1-th pebble can be put only if the pebbles from 1st to i-th are already on the tree, and the i+1-th pebble can be lifted only if pebbles from i+2-th to n-th are not on the tree. Without this restriction, the automaton has undecidable emptiness and expressive power beyond regular tree languages.<br />
<br />
The class of languages recognized by deterministic (resp. nondeterministic) pebble automata with n pebbles is denoted <math>DPA_{n}</math> (resp. <math>PA_{n}</math>). We also define <math>DPA = \bigcup_{n} DPA_{n}</math> and likewise <math>PA = \bigcup_{n} PA_{n}</math>.<br />
<br />
<!-- ==Examples==<br />
<br />
(to be added soon) --><br />
==Properties==<br />
<br />
*there exists a language recognized by a pebble automaton with 1 pebble, but not by any tree walking automaton; this implies that either <math>TWA \subsetneq DPA</math> or these classes are incomparable, which is an open problem<br />
*<math>PA \subsetneq REG</math>, i.e. pebble automata are strictly weaker than [[tree automaton|branching automata]]<br />
*it is not known whether <math>DPA = PA</math>, i.e. whether pebble automata can be determinized<br />
*it is not known whether pebble automata are closed under complementation<br />
*the pebble hierarchy is strict, for every n <math>PA_{n} \subsetneq PA_{n+1}</math> and <math>DPA_{n} \subsetneq DPA_{n+1}</math> <br />
<br />
<!-- ==Invisible pebbles==<br />
<br />
(to be added soon)<br />
--><br />
==Automata and logic==<br />
<br />
Pebble automata admit an interesting logical characterization. Let <math>FO+TC</math> denote the set of tree properties describable in [[transitive closure logic|transitive closure first-order logic]], and <math>FO+\text{pos}\,TC</math> the same for positive transitive closure logic, i.e. a logic where the transitive closure operator is not used under the scope of negation. Then it can be proved that <math>PA \subseteq FO+TC</math> and, in fact, <math>PA = FO+\text{pos}\,TC</math> - the languages recognized by pebble automata are exactly those expressible in positive transitive closure logic.<br />
<br />
==See also==<br />
<br />
*[[Tree walking automaton|Tree walking automata]]<br />
*[[Tree automaton|Branching automata]]<br />
*[[Transitive closure logic]]<br />
<br />
[[Category:Trees (data structures)]]<br />
[[Category:Automata theory]]</div>en>Maxal