Monadic queries over tree-structured data



Download 43.9 Kb.
Date30.04.2018
Size43.9 Kb.

MONADIC QUERIES over TREE-STRUCTURED DATA

Talk Outline

Strings, Trees, Graphs, & Logic

  • Büchi: MSO=REG over strings
  • Rabin: decidability of S2S
  • Thatcher and Wright: MSO = REG over ranked trees (tree automata)
  • Brüggemann-Klein/Wood/Murata: MSO = REG over unranked trees
  • Fagin: ESO = NP
  • Note: over graphs ESO NP-hard, MSO hard for Pol. Hierarchy.
  • Grädel/Immerman/Vardi: ESO(Horn)=Datalog=LFP=PTIME
  • (on ordered structures)
  • Courcelle MSO in LinTime on tree-like structures (treewidth <= k)
  • Clarke, Emerson, Pnueli, et al: CTL, LTL …
  • A few well-known results:

Web documents are trees !

HTML Example

  • People @ DBAI

  • Georg Gottlob gottlob@dbai.tuwien.ac.at 18420
    Christoph Koch koch@dbai.tuwien.ac.at 18449

  • Download 43.9 Kb.

    Share with your friends:




The database is protected by copyright ©sckool.org 2020
send message

    Main page