Infinite-tree automaton

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a> and <a href="/facts/Mathematical_logic/SaI7Y3wN">mathematical logic</a>, an infinite-tree automaton is a <a href="/facts/State_machine/GMusWd0a">state machine</a> that deals with infinite <a href="/facts/Tree_(set_theory)/5zkqfoz3">tree structures</a>. It can be seen as an extension of top-down <a href="/facts/Tree_automaton/Tu9nqDL2">finite-tree automata</a> to infinite trees or as an extension of <a href="/facts/%25CE%25A9-automata/wXtY3hVu">infinite-word automata</a> to infinite trees.
</p><p>A finite automaton which runs on an infinite tree was first used by <a href="/facts/Michael_O._Rabin/M6NHIb5J">Michael Rabin</a> for proving decidability of <a href="/facts/S2S_(mathematics)/vravDH1k"> S2S</a>, the <a href="/facts/Monadic_second-order_logic/m9g3W9VP"> monadic second-order</a> theory with two successors. It has been further observed that tree automata and logical theories are closely connected and it allows decision problems in logic to be reduced into decision problems for automata.
</p>

Infinite-tree automaton open-in-new

Infinite-tree automaton