Vi föreslår reguljära uttrycksformer som grund för statiskt inskrivna XML-behandlingsspråk. Typer av reguljära uttryck, liksom de flesta schemaspråk för XML, introducerar reguljära uttrycksuppgifter som upprepning (*), alternering (.), etc., för att beskriva XML-dokument. Nyheten i vårt typsystem är en semantisk presentation av subtyping, som inkluderar mellan de uppsättningar av dokument som betecknas av två typer. Vi ger flera exempel som illustrerar nyttan av denna form av undertypning i XML-behandling. Beslutsproblemet för subtypsförhållandet minskar till integrationsproblemet mellan trädautomaten, som är känd för att vara EXPTIME-fullständig. För att undvika denna höga komplexitet i typiska fall utvecklar vi en praktisk algoritm som, till skillnad från klassiska algoritmer baserade på determinisering av trädautomata, kontrollerar inklusionsförhållandet genom en top-down traversal av de ursprungliga typuttrycken. Den största fördelen med denna algoritm är att den kan utnyttja den egenskap som typ uttryck jämförs ofta dela delar av sina representationer. Vår algoritm är en variant av Aikens och Murphys set-integrationsrestriktionslösning, till vilken läggs flera nya implementationstekniker, korrekturbevis och preliminära prestandamätningar på några små program inom området för typad XML-behandling.
Det seminala arbetet av REF på ett typsystem för XML tillämpade teorin om reguljära uttryck typer och ändliga trädautomata i samband med XML.
Regular expression types for XML
{'venue': 'TOPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}