[comp.theory] 2-way automata on Infinite Trees

6500ramk@ucsbuxa.ucsb.edu (Y S Ramakrishna) (12/04/90)

Does anyone know of any references to the membership problem for
2-way automata on infinite trees ? The type of automaton I'm
interested in, has the Buchi-acceptance criterion, and can move
up and down (a) branch(es) of the tree. Any related references
will also be appreciated.

Also, for Buchi-automata on omega-sequences, does anyone know
in what way the ability to move back on the input and/or use pebbles
on the input tape affect the emptiness problem ? Any references ?

Thanks in advance.

(Please mail your replies to ramki@alpha.ucsb.edu if you think
 this posting is not of sufficient general interest.)

-- Y S Ramakrishna at UC,Santa Barbara.