A Characterization of Irreducible Sets Modulo Left-Linear Term Rewriting Systems by Tree Automata
Zsolt Fülöp, Sándor Vágvölgyi · Fundamenta Informaticae · 1990
The concept of top-down tree automata with prefix look-ahead is introduced. It is shown that a tree language is the set of irreducible trees of a left-linear term rewriting system if and only if it can be recognized by a one-state deterministic top-down tree automaton with pre fix look-ahead.