History


Please fill in your query. A complete syntax description you will find on the General Help page.
Languages modulo normalization. (English)
Konev, Boris (ed.) et al., Frontiers of combining systems. 6th international symposium, FroCoS 2007, Liverpool, UK, September 10‒12, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74620-1/pbk). Lecture Notes in Computer Science 4720. Lecture Notes in Artificial Intelligence, 221-236 (2007).
Summary: We propose a new class of tree automata, called tree automata with normalization (TAN). This framework is obtained by extending equational tree automata, and improves the results of the previous work, such as: recognized tree languages modulo the idempotency $f(x,x) = x$ are closed under complement, which are not closed in equational tree automata, besides we do not lose important decidability. In the paper, first we investigate the closure properties of this class for Boolean operations and the decidability relative to the equational tree automata. Next we consider the relationship to other automata frameworks, in particular, hedge automata, which is a class of unranked tree automata. Hedge automata have been recognized in the XML database community as a theoretical basis for modeling the manipulation of semi-structured data. Through the observation about transformations from hedge automata to tree automata, we discuss advantages in the expressiveness and complexity of TAN. As an application of our framework, we show an example that XML schema with constraints that can not be dealt with by other tree automata frameworks is manipulated by TAN.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!