@article{Martens2007550,
    Abstract = {Automata for unranked trees form a foundation for \{XML\} Schemas, querying and pattern languages. We study the problem of efficiently minimizing such automata. First, we study unranked tree automata that are standard in database theory, assuming bottom-up determinism and that horizontal recursion is represented by deterministic finite automata. We show that minimal automata in that class are not unique and that minimization is np-complete. Second, we study more recent automata classes that do allow for polynomial time minimization. Among those, we show that bottom-up deterministic stepwise tree automata yield the most succinct representations. Third, we investigate abstractions of \{XML\} schema languages. In particular, we show that the class of one-pass preorder typeable schemas allows for polynomial time minimization and unique minimal models.},
    Author = {Martens, Wim and Niehren, Joachim},
    File = {On the minimization of {XML} Schemas and tree automata for unranked trees - Martens, Niehren (0) (0) - a - a - t.pdf},
    ISSN = {0022-0000},
    Journal = {Journal of Computer and System Sciences},
    Keywords = {XML schema languages, unranked trees},
    Note = {Special Issue: Database Theory 2005},
    Number = {4},
    Pages = {550--583},
    Title = {On the minimization of XML Schemas and tree automata for unranked trees},
    URL = {http://www.sciencedirect.com/science/article/pii/S0022000006001401},
    Volume = {73},
    Year = {2007},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0022000006001401},
    bdsk-url-2 = {http://dx.doi.org/10.1016/j.jcss.2006.10.021},
    date-added = {2017-01-17 11:16:04 +0000},
    date-modified = {2017-01-17 11:16:36 +0000},
    doi = {10.1016/j.jcss.2006.10.021}
}

@article{Martens2007550, Abstract = {Automata for unranked trees form a foundation for {XML} Schemas, querying and pattern languages. We study the problem of efficiently minimizing such automata. First, we study unranked tree automata that are standard in database theory, assuming bottom-up determinism and that horizontal recursion is represented by deterministic finite automata. We show that minimal automata in that class are not unique and that minimization is np-complete. Second, we study more recent automata classes that do allow for polynomial time minimization. Among those, we show that bottom-up deterministic stepwise tree automata yield the most succinct representations. Third, we investigate abstractions of {XML} schema languages. In particular, we show that the class of one-pass preorder typeable schemas allows for polynomial time minimization and unique minimal models.}, Author = {Martens, Wim and Niehren, Joachim}, File = {On the minimization of {XML} Schemas and tree automata for unranked trees - Martens, Niehren (0) (0) - a - a - t.pdf}, ISSN = {0022-0000}, Journal = {Journal of Computer and System Sciences}, Keywords = {XML schema languages, unranked trees}, Note = {Special Issue: Database Theory 2005}, Number = {4}, Pages = {550--583}, Title = {On the minimization of XML Schemas and tree automata for unranked trees}, URL = {http://www.sciencedirect.com/science/article/pii/S0022000006001401}, Volume = {73}, Year = {2007}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0022000006001401}, bdsk-url-2 = {http://dx.doi.org/10.1016/j.jcss.2006.10.021}, date-added = {2017-01-17 11:16:04 +0000}, date-modified = {2017-01-17 11:16:36 +0000}, doi = {10.1016/j.jcss.2006.10.021} }