Denna artikel handlar om en speciell version av PDL, designad av Marcus Kracht för resonemang om syskon beställda träd. Den har fyra grundläggande program som motsvarar barnet, föräldern, vänster- och höger syskonrelationer i sådana träd. Den ursprungliga motivationen för detta språk är rotad i området modell-teoretisk syntax. Motiverad av den senaste utvecklingen inom området halvstrukturerade data, och särskilt inom området frågespråk för XML (eXtensible Markup Language) dokument, vi ser över språket. Detta förnyade intresse kommer med ett särskilt fokus på komplexitet och expressivitet aspekter av språket, aspekter som hittills i stor utsträckning har ignorerats. Vi undersöker och härleder komplexa resultat, och spenderar större delen av papperet på den viktigaste öppna frågan om språket: vad är dess uttryckskraft? Vi närmar oss denna fråga från två vinklar: Vilka första ordning egenskaper kan uttryckas? Och vilka andra order fastigheter? Medan vi fortfarande är något sätt från definitiva svar på dessa frågor, diskuterar vi två första ordning fragment av PDL språket för beställda träd, och visa hur språket kan användas för att uttrycka några typiska (andra ordningen) problem, som booleska kretsen och gränsproblemet.
I denna forskningslinje presenterar REF en särskild version av Propositional Dynamic Logic (PDL) för resonemang om ändliga syskonordnade träd.
PDL for Ordered Trees
{'venue': 'ICDT', 'journal': None, 'mag_field_of_study': ['Computer Science']}