4 videos

21 videos

5 videos

5 videos

# Collection Research School

00:00:00 / 00:00:00
41 65

## Semistructured data, logic, and automata – part 2

Semistructured data is an umbrella term encompassing data models which are not logically organized in tables (i.e., the relational data model) but rather in hierarchical structures using markers such as tags to separate semantic elements and data fields in a ‘self-describing’ way. In this lecture we survey some of the multiple connections between formal language theory and semi-structured data, in particular concerning the XML format. We will cover ranked and unranked tree automata, and its connections to Monadic Second Order logic, First Order logic, and XPath. The aim is to take a glimpse at the landscape of closure properties, algorithms and expressiveness results for these formalisms.

### Citation data

• DOI 10.24350/CIRM.V.19519603
• Cite this video Figueira Diego (4/9/19). Semistructured data, logic, and automata – part 2. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.19519603
• URL https://dx.doi.org/10.24350/CIRM.V.19519603

### Bibliography

• Rajeev Alur and P. Madhusudan. Visibly pushdown languages. In Symposium on Theory of Computing (STOC), pages 202–211. ACM Press, 2004. - http://doi.org/10.1145/1007352.1007390
• Saguy Benaim, Michael Benedikt, Witold Charatonik, Emanuel Kieronski, Rastislav Lenhardt, Filip Mazowiecki, and James Worrell. Complexity of two-variable logic on finite trees. ACM Transactions on Computational Logic, 17(4):32:1–32:38, 2016. - https://doi.org/10.1145/2996796
• Mikołaj Bojańczyk and Thomas Colcombet. Tree-walking automata cannot be determinized. Theoretical Computer Science, 350(2-3):164–173, 2006 - https://doi.org/10.1016/j.tcs.2005.10.031
• Mikołaj Bojańczyk and Thomas Colcombet. Tree-walking automata do not recognize all regular languages. SIAM J. Comput., 38(2):658–701, 2008 - https://doi.org/10.1137/050645427
• Mikołaj Bojańczyk, Claire David, Anca Muscholl, Thomas Schwentick, and Luc Segoufin. Two-variable logic on data words. ACM Transactions on Computational Logic, 2010
• Mikołaj Bojańczyk, Anca Muscholl, Thomas Schwentick, and Luc Segoufin. Two-variable logic on data trees and XML reasoning. Journal of the ACM, 56(3):1–48, 2009. - https://doi.org/10.1145/1516512.1516515
• Mikołaj Bojańczyk and Paweł Parys. XPath evaluation in linear time. Journal of the ACM, 58(4):17:1–17:33, 2011 - https://doi.org/10.1145/1989727.1989731
• Mikołaj Bojańczyk, Mathias Samuelides, Thomas Schwentick, and Luc Segoufin. Expressive power of pebble automata. In International Colloquium on Automata, Languages and Programming (ICALP), volume 4051 of Lecture Notes in Computer Science, pages 157–168. Springer, 2006. - https://doi.org/10.1007/11786986_15.
• J Richard Büchi. Weak second-order arithmetic and finite automata. Mathematical Logic Quarterly, 6(1-6):66–92, 1960 - https://doi.org/10.1002/malq.19600060105
• Balder ten Cate and Luc Segoufin. Transitive closure logic, nested tree walking automata, and XPath. Journal of the ACM, 57(3):18, 2010 - https://doi.org/10.1145/1706591.1706598
• Ashok K. Chandra, Dexter Kozen, and Larry J. Stockmeyer. Alternation. Journal of the ACM, 28(1):114–133, 1981 - https://doi.org/10.1145/322234.322243
• H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree automata techniques and applications (TATA) - [http://tata.gforge.inria.fr, 2007](http://tata.gforge.inria.fr, 2007)
• Stephen A. Cook. An observation on time-storage trade off. Journal of Computer and System Sciences (JCSS), 9(3):308–316, 1974 - https://doi.org/10.1016/S0022-0000(74)80046-2
• Julien Cristau, Christof Löding, and Wolfgang Thomas. Deterministic automata on unranked trees. In Fundamentals of Computation Theory, volume 3623 of Lecture Notes in Computer Science, pages 68–79. Springer, 2005. - https://doi.org/10.1007/11537311_7
• Wojciech Czerwiński, Wim Martens, Matthias Niewerth, and Paweł Parys. Minimization of tree patterns. Journal of the ACM, 65(4):26:1–26:46, 2018 - https://doi.org/10.1145/3180281
• Stéphane Demri and Ranko Lazić. LTL with the freeze quantifier and register automata. ACM Transactions on Computational Logic, 10(3), 2009. - https://doi.org/10.1145/1507244.1507246.
• Diego Figueira. Alternating register automata on finite data words and trees. Logical Methods in Computer Science (LMCS), 8(1), 2012. - https://doi.org/10.2168/LMCS-8(1:22)2012
• Diego Figueira. Decidability of downward XPath. ACM Transactions on Computational Logic, 13(4), 2012. - https://doi.org/10.1145/2362355.2362362.
• Diego Figueira. On XPath with transitive axes and data tests. In ACM Symposium on Principles of Database Systems (PODS), pages 249–260. ACM Press, 2013 - https://doi.org/10.1145/2463664.2463675
• Diego Figueira. Satisfiability of XPath on data trees. SIGLOG News, 5(2):4–16, 2018. - https://doi.org/10.1145/3212019.3212021
• Diego Figueira and Luc Segoufin. Bottom-up automata on data trees and vertical XPath. Logical Methods in Computer Science (LMCS), 13(4), 2017. - https://doi.org/10.23638/LMCS-13(4:5)2017
• Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. - https://doi.org/10.1007/3-540-29953-X
• Georg Gottlob and Christoph Koch. Monadic datalog and the expressive power of languages for Web information extraction. Journal of the ACM, 51(1):74–113, 2004 - https://doi.org/10.1145/962446.962450
• Georg Gottlob, Christoph Koch, and Reinhard Pichler. Efficient algorithms for processing XPath queries. ACM Transactions on Database Systems (TODS), 30(2):444–491, 2005. - https://doi.org/doi:10.1145/1071610.1071614
• Georg Gottlob, Christoph Koch, Reinhard Pichler, and Luc Segoufin. The complexity of XPath query evaluation and XML typing. Journal of the ACM, 52(2):284–335, 2005 - https://doi.org/10.1145/1059513.1059520
• Marcin Jurdziński and Ranko Lazić. Alternating automata on data trees and XPath satisfiability. ACM Transactions on Computational Logic, 12(3):19, 2011. - [https://doi.org/10.1145/ 1929954.1929956](https://doi.org/10.1145/ 1929954.1929956)
• Michael Kaminski and Nissim Francez. Finite-memory automata. Theoretical Computer Science, 134(2):329–363, 1994 - https://doi.org/10.1016/0304-3975(94)90242-9
• Leonid Libkin. Logics for unranked trees: An overview. Logical Methods in Computer Science (LMCS), 2(3), 2006. - https://doi.org/10.2168/LMCS-2(3:2)2006
• Wim Martens and Stijn Vansummeren. Automata and logic on trees. ESSLLI 2017 summer school. Course slides. - [https://www.theoinf.uni-bayreuth.de/pool/ documents/Other/ESSLLI07.zip](https://www.theoinf.uni-bayreuth.de/pool/ documents/Other/ESSLLI07.zip)
• Maarten Marx. Conditional XPath. ACM Transactions on Database Systems (TODS), 30(4):929–959, 2005 - https://doi.org/10.1145/1114244.1114247.
• Maarten Marx and Maarten de Rijke. Semantic characterizations of navigational XPath. SIGMOD Record, 34(2):41–46, 2005 - https://doi.org/10.1145/1083784.1083792
• Gerome Miklau and Dan Suciu. Containment and equivalence for a fragment of XPath. Journal of the ACM, 51(1):2–45, 2004 - https://doi.org/10.1145/962446.962448.
• Frank Neven. Automata, logic, and XML. In EACSL Annual Conference on Computer Science Logic (CSL), volume 2471 of Lecture Notes in Computer Science, pages 2–26. Springer, 2002 - https://doi.org/10.1007/3-540-45793-3_2
• Frank Neven. Automata theory for XML researchers. SIGMOD Record, 31(3):39–46, 2002. - http://doi.org/10.1145/601858.601869
• Frank Neven and Thomas Schwentick. Query automata over finite trees. Theoretical Computer Science, 275(1-2):633–674, 2002 - https://doi.org/10.1016/S0304-3975(01)00301-2
• Klaus Reinhardt. The complexity of translating logic to finite automata. In Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science, pages 231–238. Springer, 2001. - https://doi.org/10.1007/3-540-36387-4_13
• Thomas Schwentick. Formal methods for XML: Algorithms and complexity. EDBT 2004 summer school - [https://ls1-www.cs.tu-dortmund.de/de/ vortraege-thomas-schwentick.](https://ls1-www.cs.tu-dortmund.de/de/ vortraege-thomas-schwentick.)
• Thomas Schwentick. Automata for XML – A survey. Journal of Computer and System Sciences (JCSS), 73(3):289–315, 2007. - https://doi.org/10.1016/j.jcss.2006.10.003
• Thomas Schwentick. Foundations of XML based on logic and automata: A snapshot. In Foundations of Information and Knowledge Systems (FoIKS), volume 7153 of Lecture Notes in Computer Science, pages 23–33. Springer, 2012. - https://doi.org/10.1007/978-3-642-28472-4_2
• Luc Segoufin. Automata and logics for words and trees over an infinite alphabet. In EACSL Annual Conference on Computer Science Logic (CSL), volume 4207 of Lecture Notes in Computer Science, pages 41–57. Springer, 2006 - http://dx.doi.org/10.1007/11874683_3
• Luc Segoufin. Static analysis of XML processing with data values. SIGMOD Record, 36(1):31–38, 2007. - https://doi.org/10.1145/1276301.1276308
• Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time: Preliminary report. In Symposium on Theory of Computing (STOC), pages 1–9. ACM Press, 1973 - https://doi.org/10.1145/800125.804029
• Larry Joseph Stockmeyer. The complexity of decision problems in automata theory and logic. PhD thesis, Massachusetts Institute of Technology, 1974 - http://hdl.handle.net/1721.1/15540
• Dan Suciu. Typechecking for semistructured data. In Database Programming Languages (DBPL), volume 2397 of Lecture Notes in Computer Science, pages 1–20. Springer, 2001 - https://doi.org/10.1007/3-540-46093-4_1
• Ivan Hal Sudborough. On the tape complexity of deterministic context-free languages. Journal of the ACM, 25(3):405–414, 1978. - https://doi.org/10.1145/322077.322083
• Balder ten Cate. The expressivity of XPath with transitive closure. In ACM Symposium on Principles of Database Systems (PODS), pages 328–337. ACM Press, 2006 - https://doi.org/10.1145/1142351.1142398
• Moshe Y. Vardi. The complexity of relational query languages (extended abstract). In Symposium on Theory of Computing (STOC), pages 137–146. ACM Press, 1982 - https://doi.org/10.1145/800070.802186
• Moshe Y. Vardi. Reasoning about the past with two-way automata. In International Colloquium on Automata, Languages and Programming (ICALP), volume 1443 of Lecture Notes in Computer Science, pages 628–641. Springer, 1998. - https://doi.org/10.1007/BFb0055090
• János Virágh. Deterministic ascending tree automata I. Acta Cybernetica, 5(1):33–42, 1980. - http://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3203

### Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

### Ask a question on MathOverflow

• 59:03
published on March 24, 2016

## Bestiaire de chaînes de Markov à mémoire variable et marches aléatoires persistantes

By Peggy Cénac-Guesdon

56:28
published on March 24, 2016

## Le Laplacien massique Z-invariant sur les graphes isoradiaux

By Béatrice de Tilière

01:11:04
published on March 24, 2016

## Introduction aux processus de fragmentation - Partie 2

By Bénédicte Haas

01:54:43
published on May 3, 2016

## Calabi-Yau manifolds, mirror symmetry, and $F$-theory - part I

By David R. Morrison

01:58:36
published on May 3, 2016

## Calabi-Yau manifolds, mirror symmetry, and $F$-theory - part II

By David R. Morrison

01:37:54
published on March 16, 2017

## The KPZ fixed point - Lecture 1

By Daniel Remenik

01:29:51
published on March 16, 2017

## The KPZ fixed point - Lecture 2

By Daniel Remenik

01:38:35
published on March 16, 2017

## Variational formulas, Busemann functions, and fluctuation exponents for the corner growth model with exponential weights - Lecture 2

By Timo Seppäläinen

01:34:58
published on March 16, 2017

## Variational formulas, Busemann functions, and fluctuation exponents for the corner growth model with exponential weights - Lecture 3

By Timo Seppäläinen

28:47
published on March 30, 2017

## Processus de Pólya à valeur mesure

By Cécile Mailler

01:01:40
published on March 30, 2017

## Une histoire de mots inattendus et de génomes

By Sophie Schbath

01:27:53
published on April 13, 2017

## Collective dynamics in life sciences - Lecture 2. The Vicsek model as a paradigm for self-organization: from particles to fluid via kinetic descriptions

By Pierre Degond

32:39
published on April 13, 2017

## Collective dynamics in life sciences - Lecture 3. Phase transitions in the Vicsek model: mathematical analyses in the kinetic framework

By Pierre Degond

01:31:01
published on April 13, 2017

## Steady states and long range correlations in driven systems - Lecture 1

By David Mukamel

01:29:32
published on April 13, 2017

## Steady states and long range correlations in driven systems - Lecture 2

By David Mukamel

01:05:15
published on July 26, 2017

## Capacity expansion games with application to competition in power generation investments

By René Aïd

54:55
published on July 26, 2017

## Mean field games with major and minor players

By René Carmona

01:48:41
published on July 26, 2017

## An introduction to BSDE

By Peter Imkeller

01:05:24
published on July 26, 2017

## On the interplay between kinetic theory and game theory

By Pierre Degond

01:04:34
published on July 26, 2017

## Model-free control and deep learning

By Marc Bellemare

01:33:54
published on July 31, 2017

## Branching for PDEs

By Xavier Warin

01:03:25
published on August 1, 2017

## Bandits in auctions (& more)

By Vianney Perchet

01:24:58
published on February 1, 2018

## Calcul tensoriel formel sur les variétés différentielles - Partie 2

By Éric Gourgoulhon

33:27
published on March 22, 2018

## Sur les mesures stationnaires des VLMC

By Nicolas Pouyanne

01:09:00
published on April 24, 2018

## Introduction to quantum optics - Lecture 4

By Peter Zoller

01:27:35
published on November 2, 2016

## Mutually enriching connections between ergodic theory and combinatorics - part 1

By Vitaly Bergelson

01:12:01
published on November 2, 2016

## Mutually enriching connections between ergodic theory and combinatorics - part 3

By Vitaly Bergelson

01:01:00
published on November 2, 2016

## Mutually enriching connections between ergodic theory and combinatorics - part 4

By Vitaly Bergelson

01:26:28
published on November 2, 2016

## Mutually enriching connections between ergodic theory and combinatorics - part 5

By Vitaly Bergelson

01:30:32
published on November 2, 2016

## Mutually enriching connections between ergodic theory and combinatorics - part 6

By Vitaly Bergelson

01:13:50
published on November 2, 2016

## Mutually enriching connections between ergodic theory and combinatorics - part 7

By Vitaly Bergelson

58:41
published on November 2, 2016

## Mutually enriching connections between ergodic theory and combinatorics - part 8

By Vitaly Bergelson

01:10:22
published on July 26, 2018

## A new continuum theory for incompressible swelling materials

By Pierre Degond

01:58:23
published on November 12, 2018

## Bayesian computational methods

By Christian P. Robert

01:46:08
published on November 1, 2018

## Bayesian computation with INLA

By Havard Rue

01:59:38
published on November 12, 2018

## An introduction to particle filters

By Nicolas Chopin

02:05:23
published on October 31, 2018

## Model assessment, selection and averaging

By Aki Vehtari

01:26:05
published on March 21, 2019

## Transductions - Partie 1

By Emmanuel Filiot

01:27:49
published on March 25, 2019

## Transductions - Partie 2

By Pierre-Alain Reynier

01:26:36
published on May 13, 2019

## Semistructured data, logic, and automata – part 1

By Diego Figueira

01:16:55
published on May 13, 2019

## Semistructured data, logic, and automata – part 2

By Diego Figueira

01:19:29
published on May 21, 2019

## Cohomological obstructions to local-global principles - lecture 1

By Cyril Demarche

01:14:07
published on May 21, 2019

## Cohomological obstructions to local-global principles - lecture 2

By Cyril Demarche

01:17:29
published on May 21, 2019

## Cohomological obstructions to local-global principles - lecture 3

By Cyril Demarche

01:18:09
published on May 21, 2019

## Interactions of analytic number theory and geometry - lecture 2

By Damaris Schindler

01:15:24
published on May 21, 2019

## Interactions of analytic number theory and geometry - lecture 3

By Damaris Schindler

01:14:39
published on May 21, 2019

## Cohomological obstructions to local-global principles - lecture 4

By Cyril Demarche

01:07:32
published on May 21, 2019

## Interactions of analytic number theory and geometry - lecture 4

By Damaris Schindler

01:00:52
published on July 30, 2019

## Noise sensitivity for random walks

By Itai Benjamini

01:20:26
published on July 30, 2019

## Condensation in random trees 1/3

By Igor Kortchemski

01:11:24
published on July 30, 2019

## Condensation in random trees 2/3

By Igor Kortchemski

01:12:11
published on July 30, 2019

## Condensation in random trees 3/3

By Igor Kortchemski

56:53
published on August 30, 2019

## Scales in geophysical flows - Lecture 1

By Rupert Klein

01:02:11
published on August 30, 2019

## Asymptotic methods for the study of oceanographic models - Lecture 1: model hierarchy

By Anne-Laure Dalibard

01:23:10
published on August 30, 2019

## Internal wave dynamics in the atmosphere - Lecture 2

By Rupert Klein

01:28:54
published on August 30, 2019

## Modelling shallow water waves - Lecture 1

By David Lannes

01:35:09
published on August 30, 2019

## Asymptotic methods for the study of oceanographic models - Lecture 2: filtering methods

By Anne-Laure Dalibard

01:12:35
published on August 30, 2019

## Internal wave dynamics in the atmosphere, take-home messages - Lecture 3

By Rupert Klein

01:04:46
published on August 30, 2019

## Modelling shallow water waves - Lecture 2

By David Lannes

01:33:00
published on August 30, 2019

## Asymptotic methods for the study of oceanographic models - Lecture 3: boundary layer methods

By Anne-Laure Dalibard

01:34:37
published on August 30, 2019

## Modelling shallow water waves - Lecture 3

By David Lannes

01:36:05
published on September 20, 2019

## Basics on affine Grassmanianns

By Timo Richarz

01:41:31
published on February 21, 2020

## Stochastic modeling for population dynamics: simulation and inference - Part 1

By Benoîte de Saporta

01:33:26
published on February 21, 2020

## Stochastic modeling for population dynamics: simulation and inference - Part 2

By Benoîte de Saporta

59:27
published on November 2, 2020

## PDMPs and Integrals PDMPs in risk theory and QMC integration II

By Stefan Thonhauser

## Register

• Bookmark videos
• Add videos to see later &