Bottom-up automata on data trees and vertical XPath

Diego Figueira, Luc Segoufin

A data tree is a finite tree whose every node carries a label from a finite alphabet and a datum from some infinite domain. We introduce a new model of automata over unranked data…