Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!ucsd!hub.ucsb.edu!ucsbuxa!6500ramk
From: 6500ramk@ucsbuxa.ucsb.edu (Y S Ramakrishna)
Newsgroups: comp.theory
Subject: 2-way automata on Infinite Trees
Keywords: automata, w-languages, tree-languages, decidability
Message-ID: <7630@hub.ucsb.edu>
Date: 4 Dec 90 04:09:16 GMT
Sender: news@hub.ucsb.edu
Distribution: comp
Lines: 17


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.


Brought to you by Super Global Mega Corp .com