@article{Colazzo:Efficient:TCS:2013,
    Abstract = {Abstract The inclusion of Regular Expressions (REs) is the kernel of any type-checking algorithm for \{XML\} manipulation languages. \{XML\} applications would benefit from the extension of \{REs\} with interleaving and counting, but this is not feasible in general, since inclusion is EXPSPACE-complete for such extended REs. In Colazzo et al. (2009) [1] we introduced a notion of ``conflict-free REs'', which are extended \{REs\} with excellent complexity behaviour, including a polynomial inclusion algorithm [1] and linear membership (Ghelli et al., 2008 [2]). Conflict-free \{REs\} have interleaving and counting, but the complexity is tamed by the ``conflict-free'' limitations, which have been found to be satisfied by the vast majority of the content models published on the Web. However, a type-checking algorithm needs to compare machine-generated subtypes against human-defined supertypes. The conflict-free restriction, while quite harmless for the human-defined supertype, is far too restrictive for the subtype. We show here that the \{PTIME\} inclusion algorithm can be actually extended to deal with totally unrestricted \{REs\} with counting and interleaving in the subtype position, provided that the supertype is conflict-free. This is exactly the expressive power that we need in order to use subtyping inside type-checking algorithms, and the cost of this generalized algorithm is only quadratic, which is as good as the best algorithm we have for the symmetric case (see [1]). The result is extremely surprising, since we had previously found that symmetric inclusion becomes NP-hard as soon as the candidate subtype is enriched with binary intersection, a generalization that looked much more innocent than what we achieve here.},
    Author = {Colazzo, D. and Ghelli, G. and Pardini, L. and Sartiani, C.},
    File = {Efficient asymmetric inclusion of regular expressions with interleaving and counting for {XML} type-checking - Colazzo, Ghelli, Pardini, Sartiani (0) (0) - a - a - l.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Keywords = {XML schema, Relax NG, shuffle regular expressions, inclusion problem},
    Pages = {88 - 116},
    Title = {Efficient asymmetric inclusion of regular expressions with interleaving and counting for \{XML\} type-checking},
    URL = {http://www.sciencedirect.com/science/article/pii/S0304397513003319},
    Volume = {492},
    Year = {2013},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0304397513003319},
    bdsk-url-2 = {http://dx.doi.org/10.1016/j.tcs.2013.04.023},
    date-added = {2017-01-10 10:51:58 +0000},
    date-modified = {2017-01-10 11:10:35 +0000},
    file-2 = {Efficient asymmetric inclusion of regular expressions with interleaving and counting for {XML} type-checking - Colazzo, Ghelli, Pardini, Sartiani (1) (0) - a - a - l.pdf},
    doi = {10.1016/j.tcs.2013.04.023}
}

@article{Colazzo:Efficient:TCS:2013, Abstract = {Abstract The inclusion of Regular Expressions (REs) is the kernel of any type-checking algorithm for {XML} manipulation languages. {XML} applications would benefit from the extension of {REs} with interleaving and counting, but this is not feasible in general, since inclusion is EXPSPACE-complete for such extended REs. In Colazzo et al. (2009) [1] we introduced a notion of conflict-free REs'', which are extended \{REs\} with excellent complexity behaviour, including a polynomial inclusion algorithm [1] and linear membership (Ghelli et al., 2008 [2]). Conflict-free \{REs\} have interleaving and counting, but the complexity is tamed by theconflict-free'' limitations, which have been found to be satisfied by the vast majority of the content models published on the Web. However, a type-checking algorithm needs to compare machine-generated subtypes against human-defined supertypes. The conflict-free restriction, while quite harmless for the human-defined supertype, is far too restrictive for the subtype. We show here that the {PTIME} inclusion algorithm can be actually extended to deal with totally unrestricted {REs} with counting and interleaving in the subtype position, provided that the supertype is conflict-free. This is exactly the expressive power that we need in order to use subtyping inside type-checking algorithms, and the cost of this generalized algorithm is only quadratic, which is as good as the best algorithm we have for the symmetric case (see [1]). The result is extremely surprising, since we had previously found that symmetric inclusion becomes NP-hard as soon as the candidate subtype is enriched with binary intersection, a generalization that looked much more innocent than what we achieve here.}, Author = {Colazzo, D. and Ghelli, G. and Pardini, L. and Sartiani, C.}, File = {Efficient asymmetric inclusion of regular expressions with interleaving and counting for {XML} type-checking - Colazzo, Ghelli, Pardini, Sartiani (0) (0) - a - a - l.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Keywords = {XML schema, Relax NG, shuffle regular expressions, inclusion problem}, Pages = {88 - 116}, Title = {Efficient asymmetric inclusion of regular expressions with interleaving and counting for {XML} type-checking}, URL = {http://www.sciencedirect.com/science/article/pii/S0304397513003319}, Volume = {492}, Year = {2013}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0304397513003319}, bdsk-url-2 = {http://dx.doi.org/10.1016/j.tcs.2013.04.023}, date-added = {2017-01-10 10:51:58 +0000}, date-modified = {2017-01-10 11:10:35 +0000}, file-2 = {Efficient asymmetric inclusion of regular expressions with interleaving and counting for {XML} type-checking - Colazzo, Ghelli, Pardini, Sartiani (1) (0) - a - a - l.pdf}, doi = {10.1016/j.tcs.2013.04.023} }