Automata and Logic
Pebble automata admit an interesting logical characterization. Let denote the set of tree properties describable in transitive closure first-order logic, and 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 and, in fact, - the languages recognized by pebble automata are exactly those expressible in positive transitive closure logic.
Read more about this topic: Pebble Automaton
Famous quotes containing the word logic:
“We want in every man a long logic; we cannot pardon the absence of it, but it must not be spoken. Logic is the procession or proportionate unfolding of the intuition; but its virtue is as silent method; the moment it would appear as propositions and have a separate value, it is worthless.”
—Ralph Waldo Emerson (1803–1882)