Abstrakt. Forskning om informationsextrahering från webbsidor (inplastning) har varit mycket aktiv på senare tid (särskilt systemimplementeringar), men få insatser har gjorts för att formellt studera uttryckligheten i de formalismer som föreslås eller på de teoretiska grunderna för omslag. I den här artikeln studerar vi först monadiska datalogg över träd som ett omslagsspråk. Vi visar att detta enkla språk är likvärdigt med monadisk andra ordningen logik (MSO) i sin förmåga att ange omslag. Vi anser att MSO har rätt uttrycksförmåga som krävs för webbinformationsutdrag och föreslår MSO som måttstock för att utvärdera och jämföra omslag. Längs vägen, flera andra resultat på komplexiteten av frågeutvärdering och fråge inneslutning för monadiska datalogg över träd är etablerade, och en enkel normal form för detta språk presenteras. Med hjälp av ovanstående resultat studerar vi därefter kärnfragmentet Elog − i inslagningsspråket Elog som används i Lixto-systemet (en visuell omslagsgenerator). Märkligt nog fångar Elog – exakt MSO, men är ändå lättare att använda. Faktum är att program på detta språk kan vara helt visuellt specificerade.
Datalogg över träd har ursprungligen beaktats i REF.
Monadic datalog and the expressive power of languages for Web information extraction
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}