Abstrakt. Vi undersöker i detta papper den rumsliga logiken TQL för att fråga semistrukturerade data, representeras som orankade beställda träd över ett oändligt alfabet. Denna logik består av vanliga booleska bindväv, rumsliga bindväv (härledda från konstruktörerna av en träd algebra), trädvariabler och en fixpoint operator för rekursion. Motiverade av XML-orienterade uppgifter undersöker vi det bevakade TQL-fragmentet. Vi bevisar att för slutna formler är detta fragment MSO-komplett. I närvaro av trädvariabler är detta fragment mycket mer uttrycksfullt än MSO, eftersom det möjliggör tester av trädkvalitet, d.v.s. testa om två underträd är isomorfa eller inte. Vi utformar en ny klass av trädautomata, Taged, som utökar trädautomata med global jämlikhet och ojämlikhet begränsningar. Vi visar att tillfredsställandet problem för bevakade TQL formler minskar till tomhet Taged. Sedan fokuserar vi på avgränsade TQL-formler: intuitivt begränsas en formel om för något träd, antalet av dess positioner där ett underträd fångas av en variabel begränsas. Vi bevisar att detta fragment motsvarar en underklass av Taged, kallad avgränsad Taged, för vilken vi bevisar att tomheten är decimerbar. Detta innebär att det avgränsade skyddade TQL-fragmentet kan fastställas. Slutligen jämför vi avgränsade Taged med ett fragment av MSO utsträckt med subtree isomorfism tester.
Det senare har införts som ett verktyg för att bestämma ett fragment av den rumsliga logiken TQL REF.
Satisfiability of a spatial logic with tree variables
{'venue': 'In Proc. 21st Int. Workshop on Computer Science Logic (CSL', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}