Logics for Unranked Trees: An Overview

Leonid Libkin

doi:10.2168/LMCS-2(3:2)2006

Leonid Libkin - Logics for Unranked Trees: An Overview

lmcs:2244 - Logical Methods in Computer Science, July 26, 2006, Volume 2, Issue 3 - https://doi.org/10.2168/LMCS-2(3:2)2006

Logics for Unranked Trees: An OverviewArticle

Authors: Leonid Libkin

Labeled unranked trees are used as a model of XML documents, and logical languages for them have been studied actively over the past several years. Such logics have different purposes: some are better suited for extracting data, some for expressing navigational properties, and some make it easy to relate complex properties of trees to the existence of tree automata for those properties. Furthermore, logics differ significantly in their model-checking properties, their automata models, and their behavior on ordered and unordered trees. In this paper we present a survey of logics for unranked trees.

https://doi.org/10.2168/LMCS-2(3:2)2006

Source: arXiv.org:cs/0606062

Volume: Volume 2, Issue 3

Published on: July 26, 2006

Submitted on: August 31, 2005

Keywords: Computer Science - Logic in Computer Science,Computer Science - Databases,H.2.3,H.2.1,I.7,F.2.3,F.4.1,F.4.3

Licence: arXiv.org - Assumed non-exclusive license to distribute

Funding:

Source : OpenAIRE Graph

Funder: Natural Sciences and Engineering Research Council of Canada

Classifications

Mathematics Subject Classification 2020¹

68Q15 - Complexity classes (hierarchies, relations among complexity classes, etc.)

Sources:

[1] zbMATH Open.

Bibliographic References

24 Documents citing this article

Jelle Hellings;Marc Gyssens;Jan Van Den Bussche;Dirk Van Gucht, Document Server@UHasselt (UHasselt), Expressive Completeness of Two-Variable First-Order Logic with Counting for First-Order Logic Queries on Rooted Unranked Trees, pp. 1-13, 2023, Boston, MA, USA, 10.1109/lics56636.2023.10175828, http://hdl.handle.net/1942/41525.

Johanna Björklund;Shay B. Cohen;Frank Drewes;Giorgio Satta, 2020, Bottom-up unranked tree-to-graph transducers for translation into semantic graphs, Theoretical Computer Science, 870, pp. 3-28, 10.1016/j.tcs.2020.12.012, https://doi.org/10.1016/j.tcs.2020.12.012.

Johanna Björklund;Frank Drewes;Giorgio Satta, Lecture notes in computer science, Z-Automata for Compact and Direct Representation of Unranked Tree Languages, pp. 83-94, 2019, 10.1007/978-3-030-23679-3_7.

Matthew Hague;Anthony W. Lin;Chih-Duo Hong, 2019, CSS Minification via Constraint Solving, ACM Transactions on Programming Languages and Systems, 41, 2, pp. 1-76, 10.1145/3310337.

Felipe Pezoa;Juan L. Reutter;Fernando Suarez;Martín Ugarte;Domagoj Vrgoč, Proceedings of the 25th International Conference on World Wide Web, Foundations of JSON Schema, 2016, Montréal Québec Canada, 10.1145/2872427.2883029.

Mariam Beriashvili;Besik Dundua, Advances in intelligent systems and computing, A Constraint Solver for Equations over Sequences and Contexts, pp. 115-127, 2016, 10.1007/978-3-319-38884-7_9.

Anuj Dawar;Luc Segoufin, Capturing MSO with One Quantifier, pp. 142-152, 2015, 10.1007/978-3-319-23534-9_8, https://hal.inria.fr/hal-01223378.

Diego Figueira;Leonid Libkin, Edinburgh Research Explorer (University of Edinburgh), Path Logics for Querying Graphs: Combining Expressiveness and Efficiency, 89, pp. 329-340, 2015, Kyoto, Japan, 10.1109/lics.2015.39, https://www.pure.ed.ac.uk/ws/files/19966471/lics15.pdf.

Leonid Libkin;Tony Tan;Domagoj Vrgoč, 2015, Regular expressions for data words, Edinburgh Research Explorer (University of Edinburgh), 81, 7, pp. 1278-1297, 10.1016/j.jcss.2015.03.005, https://www.pure.ed.ac.uk/ws/files/20039402/regular_v_jcss_final.pdf.

Matthew Hague;Anthony W. Lin;C.-H. Luke Ong, 2015, Detecting redundant CSS rules in HTML5 applications: a tree rewriting approach, arXiv (Cornell University), 50, 10, pp. 1-19, 10.1145/2858965.2814288, https://arxiv.org/abs/1412.5143.

Matthew Hague;Anthony W. Lin;C.-H. Luke Ong, arXiv (Cornell University), Detecting redundant CSS rules in HTML5 applications: a tree rewriting approach, 2015, Pittsburgh PA USA, 10.1145/2814270.2814288, https://arxiv.org/abs/1412.5143.

Makoto Kanazawa, 2014, Multidimensional trees and a Chomsky–Schützenberger–Weir representation theorem for simple context-free tree grammars, Journal of Logic and Computation, 26, 5, pp. 1469-1516, 10.1093/logcom/exu043.

Paulo Caetano da Silva, Advances in systems analysis, software engineering, and high performance computing book series, Multidimensional Data Analysis Based on Links, pp. 212-281, 2014, 10.4018/978-1-4666-6098-4.ch009.

Leonid Libkin;Domagoj Vrgoč, Edinburgh Research Explorer (University of Edinburgh), Regular Expressions for Data Words, pp. 274-288, 2012, 10.1007/978-3-642-28717-6_22, https://www.research.ed.ac.uk/en/publications/13c95756-5107-4393-bc07-fc4923e0b2f3.

Paulo Caetano da Silva;Valéria Cesário Times;Ricardo Rodrigues Ciferri;Cristina Dutra de Aguiar Ciferri, 2012, Analytical Processing Over XML and XLink, International Journal of Data Warehousing and Mining, 8, 1, pp. 52-92, 10.4018/jdwm.2012010103.

Thomas Schwentick, Lecture notes in computer science, Foundations of XML Based on Logic and Automata: A Snapshot, pp. 23-33, 2012, 10.1007/978-3-642-28472-4_2.

Benedikt Bollig;Aiswarya Cyriac;Paul Gastin;Marc Zeitoun, Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model Checking, pp. 132-144, 2011, 10.1007/978-3-642-22993-0_15, https://hal.science/hal-00591139.

Balder ten Cate;Gaëlle Fontaine, Lecture notes in computer science, An Easy Completeness Proof for the Modal μ-Calculus on Finite Trees, pp. 161-175, 2010, 10.1007/978-3-642-12032-9_12, https://doi.org/10.1007/978-3-642-12032-9_12.

Leonid Libkin, Encyclopedia of Database Systems, Expressive Power of Query Languages, pp. 1081-1083, 2009, 10.1007/978-0-387-39940-9_1239.

Paulo Caetano da Silva;Valéria Cesário Times, Lecture notes in computer science, XPath+: A Tool for Linked XML Documents Navigation, pp. 67-74, 2009, 10.1007/978-3-642-03555-5_6.

Wenfei Fan;Jeffrey Xu Yu;Jianzhong Li;Bolin Ding;Lu Qin, 2009, Query translation from XPath to SQL in the presence of recursive DTDs, Edinburgh Research Explorer (University of Edinburgh), 18, 4, pp. 857-883, 10.1007/s00778-008-0131-0, https://www.research.ed.ac.uk/portal/en/publications/query-translation-from-xpath-to-sql-in-the-presence-of-recursive-dtds(c2a4f431-8344-4916-b99d-1f4c8dd4bad4).html.

Blaise Genest;Anca Muscholl;Olivier Serre;Marc Zeitoun, Tree Pattern Rewriting Systems, pp. 332-346, 2008, 10.1007/978-3-540-88387-6_29, https://hal.archives-ouvertes.fr/hal-00344551.

Joost Engelfriet;Hendrik Jan Hoogeboom, 2007, Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure, Logical Methods in Computer Science, Volume 3, Issue 2, 10.2168/lmcs-3(2:3)2007, https://doi.org/10.2168/lmcs-3(2:3)2007.

Robson da Luz;Mírian Halfeld Ferrari;Martin A. Musicante, 2007, Regular expression transformations to extend regular languages (with application to a Datalog XML schema validator), Journal of Algorithms, 62, 3-4, pp. 148-167, 10.1016/j.jalgor.2007.04.004.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 2477 times.

This article's PDF has been downloaded 584 times.