Abstract:Because of the simplicity of taking complement operation on alternating (tree) automata and the equivalence relationship between alternating (tree) automata and nondeterministic (tree) automata, the study on alternating (tree) automata becomes a new research area of automata and model checking. Based on notions of L-valued alternating automata and alternating tree automata, the notion of L-valued alternating tree automata is introduce, and closure properties and expressive power of L-valued alternating tree automata are studied. Firstly, it is proved that after taking dual operations on transitions and changing the weight of each final state to its complement, a new L-valued alternating tree automaton is achieved which is the complement of the starting one. Afterwards, the closure is illustrated under conjunction and disjunction of languages accepted by L-valued alternating tree automata. Finally, the expressive power of L-valued alternating tree automata, L-valued tree automata, and L-valued nondeterministic automata are discussed. The equivalence relationship is proved between L-valued alternating tree automata and L-valued tree automata, the algorithms are given between them and complexities are discussed of algorithms; simultaneously, a method is provided to show how to use L-valued nondeterministic automata to simulate L-valued alternating tree automata.

Abstract:How to efficiently evaluate massive XPaths set over an XML stream is a fundamental problem in applications of the data stream. The current methods can not fully support the commonly used features of XPath, or can not meet the space and time requirement of the data stream applications. In this paper, a new tree automata based machine, XEBT, is proposed to solve the problem. Different from traditional ones, XEBT has the following features: First, it is based on tree automata with a powerful expressiveness, which can support Xpath {[]} without extra states or intermediate results; Second, XEBT supports many optimization strategies, including DTD based XPath tree automata construction, partial determination to reduce the concurrent states at running time with limited extra space costs, and the combination of bottom-up and top-down evaluation. Experimental results show that XEBT supports the complex Xpath and outperforms the former work in both efficiency and space cost.

Abstract:XPath becomes the basic mechanism for XML query. The non-deterministic operators in XPath, such as ‘//’ denoting ancestor-descendant relationship and ‘*’ denoting wildcards in XPath, greatly enhance the flexibility of XPath, but at the same time, introduce the complexity in XPath evaluation. How to explore DTD to reduce non-deterministic operators in XPath in order to improve the efficiency of XPath processing becomes a fundamental problem. The existing work focus on the limited fragment of XPath or DTD. This paper employs tree automata to express XPath and DTD in a unified framework, proposes a novel production operation on tree automata for XPath and tree automata for DTD, proves that the result of production equals to the optimized form of XPath in the presence of DTD, and generates the optimized XPath in a polynomial time based on the generation cost. The experimental result demonstrate that logical optimization on XPath can lead to the increase of efficiency on the existing XPath evaluator.