Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-29T05:12:17.246Z Has data issue: false hasContentIssue false
  • English
  • Français

Nested Sibling Tree Automata

Published online by Cambridge University Press:  12 March 2009

Françoise Gire  and
Jean-Marc Talbot
Françoise Gire
Affiliation:
Université de Paris I, Centre de Recherche en Informatique Paris Cedex 13, France. [email protected]
Jean-Marc Talbot
Affiliation:
Université de Provence, LIF Marseille France. [email protected]
Get access

Abstract

In the XML standard, data are represented as unranked labeledordered trees. Regular unranked tree automata provide a usefulformalism for the validation of schemas enforcing regular structuralconstraints on XML documents. However some concrete applicationcontexts need the expression of more general constraints than theregular ones. In this paper we propose a new framework in whichcontext-free style structural constraints can be expressed andvalidated. This framework is characterized by: (i) the introductionof a new notion of trees, the so-called typed unranked labeledtrees (tulab trees for short) in which each node receivesone of three possible types (up, down or fix), and (ii) thedefinition of a new notion of tree automata, the so-callednested sibling tulab tree automata, able to enforcecontext-free style structural constraints on tulab tree languages.During their structural control process, such automata are usingvisibly pushdown languages of words [R. Alur and P. Madhusudan, Visibly pushdown languages, 36th ACM symposium on Theory of Computing, Chicago, USA (2004) 202–211] on theiralphabet of states. We show that the resulting class NSTL oftulab tree languages recognized by nested sibling tulab treeautomata is robust, i.e. closed under Boolean operations and withdecision procedures for the classical membership, emptiness andinclusion problems. We then give three characterizations of NSTL :a logical characterization by defining an adequate logic in whichNSTL happens to coincide with the models of monadic second ordersentences; the two other characterizations are using adequateencodings and map together languages of NSTL with some regularsets of 3-ary trees or with particular sets of binary trees.

Keywords

Automatalogicunranked treesXML schemas.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 43 , Issue 2 , April 2009 , pp. 379 - 402
Copyright
© EDP Sciences, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

S. Abiteboul and P. Buneman, Data on the Web: From Relations to Semi-structured Data and XML (1999).
R. Alur, S. Chaudhuri and P. Madhusudan, A fixpoint calculus for local and global program flows, Symposium on Principles of Programming Languages, POPL 2006 (2006) 153–165.
R. Alur, S. Chaudhuri and P. Madhusudan, Languages of nested trees, Computer-Aided Verification, CAV 2006 (2006) 329–342.
Rajeev Alur and P. Madhusudan, Visibly pushdown languages, Chicago, USA. 36th ACM symposium on Theory of Computing (2004) 202–211.
M. Bojanczyck and T. Colcombet, Tree-walking automata cannot be determinized. ICALP (2004) 246–256.
T. Bray, J.P. Paoh and C.M. Sperberg-McQueen, Extensible markup language (xml) 1.0, http://www.w3org/TR/1998/REC-xml-19980210/ (1998).
A. Bruggemann, M. Murata and D. Wood, Regular tree and regular hedge languages over unranked alphabets, Technical Report 2001–05. HKUST TCS Center (1998).
Comon, H. and Cortier, V., Tree automata with one memory set constraints and cryptographic protocols. Theoret. Comput. Sci. 331 (2005) 143–214. CrossRef
H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi, Tree automata techniques and applications, available on: http://www.grappa.univ-lille3.fr/tata (2007), release October, 12th (2007).
Comon-Lundh, H., Jacquemard, F. and Perrin, N., Tree automata with memory, visibility and structural constraints, In Foundations of Software Science and Computational Structures, 10th International Conference, FOSSACS 2007. Lect. Notes Comput. Sci. 4423 (2007) 168–182. CrossRef
D. Lugiez and S. DalZilio, Xml schema, tree logic and sheaves automata, Technical Report RR-4631, Inria (2002).
F. Neven, Automata, logic and xml. CSL (2002) 2–26.
C. Pitcher, Visibly pushdown expression effects for xml stream processing, Programming Languages Technologies for XML. PLAN-X (2005) 5–19.
T. Schwentick, Tree, automata and xml. Paris, PODS (2004).
L. Segoufin, Typing and quering xml documents: some complexity bounds. San Diego CA, PODS (2003) 167–178.
H. Seidl, T. Schwentick and A. Muscholl, Numerical document queries. San Diego CA, PODS (2003).
J.W. Thatcher and J.B. Wright, Generalized finite automata with an application to a decision problem of second-order logic. Mathematical System Theory 2 57–82 (1968).