Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking

DOI10.1016/j.tcs.2013.04.023zbMath1294.68066OpenAlexW2045457289MaRDI QIDQ391129

L. Pardini, Carlo Sartiani, Giorgio Ghelli, Dario Colazzo

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.04.023

zbMATH Keywords

XMLregular expressionssubtypingXML schematype-checking algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05)

Related Items

Distributed XML design, The inclusion problem for regular expressions

Cites Work

• Unnamed Item
• Efficient inclusion for a class of XML types with interleaving and counting
• Efficient inclusion checking for deterministic tree automata and XML schemas
• Shuffle languages are in P
• One-unambiguity of regular expressions with numeric occurrence indicators
• The Inclusion Problem for Regular Expressions
• Complexity of Decision Problems for XML Schemas and Chain Regular Expressions
• Inclusion Test Algorithms for One-Unambiguous Regular Expressions
• Derivatives of Regular Expressions
• Regular Expressions with Counting: Weak versus Strong Determinism
• One-unambiguous regular languages