<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//TaxonX//DTD Taxonomic Treatment Publishing DTD v0 20100105//EN" "../../nlm/tax-treatment-NS0.dtd">
<article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:tp="http://www.plazi.org/taxpub" article-type="research-article" dtd-version="3.0" xml:lang="en">
  <front>
    <journal-meta>
      <journal-id journal-id-type="publisher-id">109</journal-id>
      <journal-id journal-id-type="index">urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891</journal-id>
      <journal-title-group>
        <journal-title xml:lang="en">JUCS - Journal of Universal Computer Science</journal-title>
        <abbrev-journal-title xml:lang="en">jucs</abbrev-journal-title>
      </journal-title-group>
      <issn pub-type="ppub">0948-695X</issn>
      <issn pub-type="epub">0948-6968</issn>
      <publisher>
        <publisher-name>Journal of Universal Computer Science</publisher-name>
      </publisher>
    </journal-meta>
    <article-meta>
      <article-id pub-id-type="doi">10.3217/jucs-022-02-0180</article-id>
      <article-id pub-id-type="publisher-id">22967</article-id>
      <article-categories>
        <subj-group subj-group-type="heading">
          <subject>Research Article</subject>
        </subj-group>
        <subj-group subj-group-type="scientific_subject">
          <subject>F.1.1 - Models of Computation</subject>
          <subject>F.4.3 - Formal Languages</subject>
        </subj-group>
      </article-categories>
      <title-group>
        <article-title>A Taxonomy of Minimisation Algorithms for Deterministic Tree Automata</article-title>
      </title-group>
      <contrib-group content-type="authors">
        <contrib contrib-type="author" corresp="yes">
          <name name-style="western">
            <surname>Björklund</surname>
            <given-names>Johanna</given-names>
          </name>
          <email xlink:type="simple">johanna@cs.umu.se</email>
          <xref ref-type="aff" rid="A1">1</xref>
        </contrib>
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>Cleophas</surname>
            <given-names>Loek</given-names>
          </name>
          <xref ref-type="aff" rid="A1">1</xref>
        </contrib>
      </contrib-group>
      <aff id="A1">
        <label>1</label>
        <addr-line content-type="verbatim">Umeå University, Umeå, Sweden</addr-line>
        <institution>Umeå University</institution>
        <addr-line content-type="city">Umeå</addr-line>
        <country>Sweden</country>
      </aff>
      <author-notes>
        <fn fn-type="corresp">
          <p>Corresponding author: Johanna Björklund (<email xlink:type="simple">johanna@cs.umu.se</email>).</p>
        </fn>
        <fn fn-type="edited-by">
          <p>Academic editor: </p>
        </fn>
      </author-notes>
      <pub-date pub-type="collection">
        <year>2016</year>
      </pub-date>
      <pub-date pub-type="epub">
        <day>01</day>
        <month>02</month>
        <year>2016</year>
      </pub-date>
      <volume>22</volume>
      <issue>2</issue>
      <fpage>180</fpage>
      <lpage>196</lpage>
      <uri content-type="arpha" xlink:href="http://openbiodiv.net/9464CD28-96AF-5EDD-9B7E-0B1B6586CE09">9464CD28-96AF-5EDD-9B7E-0B1B6586CE09</uri>
      <uri content-type="zenodo_dep_id" xlink:href="https://zenodo.org/record/5504821">5504821</uri>
      <history>
        <date date-type="received">
          <day>23</day>
          <month>09</month>
          <year>2015</year>
        </date>
        <date date-type="accepted">
          <day>22</day>
          <month>01</month>
          <year>2016</year>
        </date>
      </history>
      <permissions>
        <copyright-statement>Johanna Björklund, Loek Cleophas</copyright-statement>
        <license license-type="creative-commons-attribution" xlink:href="" xlink:type="simple">
          <license-p>This article is freely available under the J.UCS Open Content License.</license-p>
        </license>
      </permissions>
      <abstract>
        <label>Abstract</label>
        <p>We present a taxonomy of algorithms for minimising deterministic bottomup tree automata (dtas) over ranked and ordered trees. Automata of this type and its extensions are used in many application areas, including natural language processing (nlp) and code generation. In practice, dtas can grow very large, but minimisation keeps things manageable. The proposed taxonomy serves as a unifying framework that makes algorithms accessible and comparable, and as a foundation for efficient implementation. Taxonomies of this type are also convenient for correctness and complexity analysis, as results can frequently be propagated through the hierarchy. The taxonomy described herein covers a broad spectrum of algorithms, ranging from novel to well-studied ones, with a focus on computational complexity.</p>
      </abstract>
    </article-meta>
  </front>
</article>
