We study first order logic definitions of structured and XML languages. We prove that bounded semilinear languages can be defined by formulas in FO[+]. Then, we exhibit meaningful classes of XML languages definable by FOC[+] formulas, and hence parsable in TC0. .
Logical description of structured and XML languages / A. Malcher, C. Mereghetti, B.S. Palano - In: theoretical computer science / [a cura di] A. Cherubini, M. Coppo, G. Persiano. - Milano : Politecnico di Milano, 2009. - pp. 161-167 (( Intervento presentato al 11. convegno Italian Conference on Theoretical Computer Science tenutosi a Cremona nel 2009.
Logical description of structured and XML languages
C. MereghettiSecondo
;B.S. PalanoUltimo
2009
Abstract
We study first order logic definitions of structured and XML languages. We prove that bounded semilinear languages can be defined by formulas in FO[+]. Then, we exhibit meaningful classes of XML languages definable by FOC[+] formulas, and hence parsable in TC0. .
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
ictcs09.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
136.12 kB
Formato
Adobe PDF
|
136.12 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
