# The Library

### Alternating automata on data trees and XPath satisfiability

Tools

Jurdzinski, Marcin and Lazic, Ranko.
(2011)
*Alternating automata on data trees and XPath satisfiability.*
ACM Transactions on Computational Logic (TOCL), Volume 12
(Number 3).
pp. 1-21.
ISSN 1529-3785

**Full text not available from this repository.**

Official URL: http://dx.doi.org/10.1145/1929954.1929956

## Abstract

A data tree is an unranked ordered tree whose every node is labeled by a letter from a finite alphabet and an element ("datum") from an infinite set, where the latter can only be compared for equality. The article considers alternating automata on data trees that can move downward and rightward, and have one register for storing data. The main results are that nonemptiness over finite data trees is decidable but not primitive recursive, and that nonemptiness of safety automata is decidable but not elementary. The proofs use nondeterministic tree automata with faulty counters. Allowing upward moves, leftward moves, or two registers, each causes undecidability. As corollaries, decidability is obtained for two data-sensitive fragments of the XPath query language.

Item Type: | Journal Article |
---|---|

Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |

Divisions: | Faculty of Science > Computer Science |

Library of Congress Subject Headings (LCSH): | Algorithms, Machine theory, Trees (Graph theory), Data mining, Query languages (Computer science) |

Journal or Publication Title: | ACM Transactions on Computational Logic (TOCL) |

Publisher: | Association for Computing Machinery, Inc. |

ISSN: | 1529-3785 |

Date: | 2011 |

Volume: | Volume 12 |

Number: | Number 3 |

Page Range: | pp. 1-21 |

Identification Number: | 10.1145/1929954.1929956 |

Status: | Peer Reviewed |

Publication Status: | Published |

Funder: | Intel Corporation |

References: | ALPERN, B. AND SCHNEIDER, F. B. 1987. Recognizing safety and liveness. Distr. Comput. 2, 3, 117–126. BENEDIKT, M., FAN, W., AND GEERTS, F. 2008. XPath satisfiability in the presence of DTDs. J. ACM 55, 2. BJ ¨ORKLUND, H. AND BOJA´NCZYK, M. 2007. Bounded depth data trees. In Proceeding of the 34th International Colloquium on Automata, Language and Programming (ICALP). Lecture Notes in Computer Science, vol. 4596. Springer, 862–874. BJ ¨ORKLUND, H. AND SCHWENTICK, T. 2007. On notions of regularity for data languages. In In Proceeding of the 16th International Symposium on Fundamentals of Computation Theory (FCT). Lecture Notes in Computer Science, vol. 4639. Springer, 88–99. BOJA´NCZYK, M., MUSCHOLL, A., SCHWENTICK, T., AND SEGOUFIN, L. 2009. Two-variable logic on data trees and XML reasoning. J. ACM 56, 3. BOJA´NCZYK, M., MUSCHOLL, A., SCHWENTICK, T., SEGOUFIN, L., AND DAVID, C. 2006. Two-variable logic on words with data. In Proceeding of the 21st IEEE Symposiam on Login in Computer (LICS). IEEE Computer Society, 7–16. BRAY, T., PAOLI, J., AND SPERBERG-MCQUEEN, C. 1998. Extensible markup language (XML) 1.0. W3C Recommendation. BRZOZOWSKI, J. A. AND LEISS, E. L. 1980. On equations for regular languages, finite automata, and sequential networks. Theoret. Comput. Sci. 10, 1, 19–35. CLARK, J. AND DEROSE, S. 1999. XML path language (XPath). W3C Recommendation. DAVID, C. 2004. Mots et donn´ees infinies.M.S. thesis, Laboratoire d’Informatique Algorithmique: Fondements et Applications, Paris. DEGROOTE, P., GUILLAUME, B., AND SALVATI, S. 2004. Vector addition tree automata. In Prceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS). IEEE Computer Society, 64–73. DEMRI, S. AND LAZI´C, R. 2009. LTL with the freeze quantifier and register automata. ACM Trans. Comp. Logic 10, 3. FIGUEIRA, D. 2009. Satisfiability of downward XPath with data equality tests. In Prceedings of the 28th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS). ACM, 197–206. FINKEL, A. AND SCHNOEBELEN, P. 2001. Well-structured transitions systems everywhere! Theoret. Comput. Sci. 256, 1–2, 63–92. GEERTS, F. AND FAN, W. 2005. Satisfiability of XPath queries with sibling axes. In Proceedings of the 10th International Symposium on Database Programming Languages (DBPL). Lecture Notes in Computer Science, vol. 3774. Springer, 122–137. HALL´E, S.,VILLEMAIRE, R., AND CHERKAOUI, O. 2006. CTLmodel checking for labeled tree queries. In Proceedings of the 13th International Symposium on Temporal Representation and Reasoning (TIME). IEEE Comput. Society, 27–35. HIGMAN, G. 1952. Ordering by divisibility in abstract algebras. Proc. London Math. Soc. 3, 2, 7, 326–336. JURDZI ´ NSKI, M. AND LAZI´C, R. 2007. Alternation-free modal mu-calculus for data trees. In Proceedings of the 22nd IEEE Symposium on Logic in Computing Science (LICS). IEEE Computer Society, 131–140. KAMINSKI, M. AND FRANCEZ, N. 1994. Finite-memory automata. Theor. Comput. Sci. 134, 2, 329–363. KAMINSKI, M. AND TAN, T. 2008. Tree automata over infinite alphabets. In Pillars of Computer Science, Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occassion of His 85th Birthday. Lecture Notes in Computer Science, vol. 4800. Springer, 386–423. LAZI´C, R. 2006. Safely freezing LTL. In Proceedings of the 26th International Conference on Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, vol. 4337. Springer, 381–392. L¨ODING, C. AND THOMAS, W. 2000. Alternating automata and logics over infinite words. In Proceedings of the IFIP International Conference on Theoretical Computer Science (IFIPTCS). Lecture Notes in Computer Science, vol. 1878. Springer, 521–535. MULLER, D. E., SAOUDI, A., AND SCHUPP, P. E. 1986. Alternating automata, the weak monadic theory of the tree, and its complexity. In Proceedings of the 13th International Colloquinm on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 226. Springer, 275–283. NEVEN, F., SCHWENTICK, T., AND VIANU, V. 2004. Finite state machines for strings over infinite alphabets. ACM Trans. Comp. Logic 5, 3, 403–435. OLTEANU, D., FURCHE, T., AND BRY, F. 2004. An efficient single-pass query evaluator for XML data streams. In Proceedings of the ACM Symposium on Applied Computing (SAC). ACM, 627–631. SAKAMOTO, H. AND IKEDA, D. 2000. Intractability of decision problems for finite-memory automata. Theoret. Comput. Sci. 231, 2, 297–308. SEGOUFIN, L. 2006. Automata and logics for words and trees over an infinite alphabet. In Proceedings of the 20th International Workshop on Computer Science Logic (CSL). Lecture Notes in Computer Scince, vol. 4207. Springer, 41–57. |

URI: | http://wrap.warwick.ac.uk/id/eprint/41430 |

Data sourced from Thomson Reuters' Web of Knowledge

### Actions (login required)

View Item |