{"id":{"repo_id":"aachen","oai_identifier":"oai:publications.rwth-aachen.de:63210"},"canonical_url":"https://search.dev.ndltd.org/etd/aachen/oai:publications.rwth-aachen.de:63210","repository":{"repo_id":"aachen","name":"RWTH Aachen University","base_url":"https://publications.rwth-aachen.de/oai2d"},"display":{"title":"Finite automata on unranked trees : extensions by arithmetical and equality constraints","abstract":"The notion of unranked trees has attracted much interest in current research, especially due to their application as formal models of XML documents. In particular, several automata and logic formalisms on unranked trees have been considered (again) in the literature, and many results that had previously been shown for the ranked-tree setting have turned out to hold for the unranked-tree setting as well. In this thesis, we study two kinds of extensions of finite automata on unranked trees, namely, the extension by arithmetical constraints and the extension by subtree-equality constraints. In the first part of the thesis we introduce a framework of automata on unranked trees that unifies two different approaches to incorporating arithmetical constraints known from the literature, namely the global-constraint approach of Klaedtke and Rueß (2003) and the local-constraint approach of Seidl et al. (2003). We investigate the relationship between the two types of arithmetical constraints with respect to language recognition, and we show that the emptiness problem for this automaton model is decidable. In the second part of this thesis, we introduce automata on unranked trees that are equipped with equality and disequality constraints between direct subtrees, thereby extending the corresponding automaton model in the ranked-tree setting, which was introduced by Bogaert and Tison (1982). In the definition of the automaton model, we propose using formulas of monadic second-order logic to capture the possibility of comparing unboundedly many direct subtrees for equality, a feature that arises naturally in light of the unrankedness. Our main result is that the emptiness problem for this automaton model is decidable. Based upon this result, furthermore, we introduce a logic over data words (that is, words over an infinite alphabet) for which the satisfiability problem is decidable.","abstract_html":"The notion of unranked trees has attracted much interest in current research, especially due to their application as formal models of XML documents. In particular, several automata and logic formalisms on unranked trees have been considered (again) in the literature, and many results that had previously been shown for the ranked-tree setting have turned out to hold for the unranked-tree setting as well. In this thesis, we study two kinds of extensions of finite automata on unranked trees, namely, the extension by arithmetical constraints and the extension by subtree-equality constraints. In the first part of the thesis we introduce a framework of automata on unranked trees that unifies two different approaches to incorporating arithmetical constraints known from the literature, namely the global-constraint approach of Klaedtke and Rueß (2003) and the local-constraint approach of Seidl et al. (2003). We investigate the relationship between the two types of arithmetical constraints with respect to language recognition, and we show that the emptiness problem for this automaton model is decidable. In the second part of this thesis, we introduce automata on unranked trees that are equipped with equality and disequality constraints between direct subtrees, thereby extending the corresponding automaton model in the ranked-tree setting, which was introduced by Bogaert and Tison (1982). In the definition of the automaton model, we propose using formulas of monadic second-order logic to capture the possibility of comparing unboundedly many direct subtrees for equality, a feature that arises naturally in light of the unrankedness. Our main result is that the emptiness problem for this automaton model is decidable. Based upon this result, furthermore, we introduce a logic over data words (that is, words over an infinite alphabet) for which the satisfiability problem is decidable.","abstract_has_math":false,"creators":["Wong, Karianto"],"institution":"Publikationsserver der RWTH Aachen University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Löding, Christof","Thomas, Wolfgang","Schwentick, Thomas"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010","date_published":"2010","updated_at":"2026-07-30T19:43:35Z","subjects":["info:eu-repo/classification/ddc/004","Automatentheorie","Baumautomat","Monadische Logik","Presburger-Arithmetik","Informatik","Automaten auf unbeschränkt verzweigten Bäumen","monadische Logik zweiter Stufe","Gleichheitsbedingungen und Ungleichheitsbedingungen","unranked tree automata","Presburger arithmetic","monadic second-order logic","equality and disequality constraints"],"languages":["eng"],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124657%22"],"render_values":[{"text":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124657%22","href":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124657%22","code":true}]}]},"links":{"outbound_url":"https://publications.rwth-aachen.de/record/63210","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Löding, Christof","Thomas, Wolfgang","Schwentick, Thomas"]},{"key":"dc:creator","label":"Author","values":["Wong, Karianto"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:coverage","label":"Dc Coverage","values":["DE"]},{"key":"dc:date","label":"Dc Date","values":["2010"]},{"key":"dc:publisher","label":"Institution","values":["Publikationsserver der RWTH Aachen University"]},{"key":"dc:relation","label":"Dc Relation","values":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-33834"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["info:eu-repo/classification/ddc/004","Automatentheorie","Baumautomat","Monadische Logik","Presburger-Arithmetik","Informatik","Automaten auf unbeschränkt verzweigten Bäumen","monadische Logik zweiter Stufe","Gleichheitsbedingungen und Ungleichheitsbedingungen","unranked tree automata","Presburger arithmetic","monadic second-order logic","equality and disequality constraints"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/record/63210","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124657%22"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The notion of unranked trees has attracted much interest in current research, especially due to their application as formal models of XML documents. In particular, several automata and logic formalisms on unranked trees have been considered (again) in the literature, and many results that had previously been shown for the ranked-tree setting have turned out to hold for the unranked-tree setting as well. In this thesis, we study two kinds of extensions of finite automata on unranked trees, namely, the extension by arithmetical constraints and the extension by subtree-equality constraints. In the first part of the thesis we introduce a framework of automata on unranked trees that unifies two different approaches to incorporating arithmetical constraints known from the literature, namely the global-constraint approach of Klaedtke and Rueß (2003) and the local-constraint approach of Seidl et al. (2003). We investigate the relationship between the two types of arithmetical constraints with respect to language recognition, and we show that the emptiness problem for this automaton model is decidable. In the second part of this thesis, we introduce automata on unranked trees that are equipped with equality and disequality constraints between direct subtrees, thereby extending the corresponding automaton model in the ranked-tree setting, which was introduced by Bogaert and Tison (1982). In the definition of the automaton model, we propose using formulas of monadic second-order logic to capture the possibility of comparing unboundedly many direct subtrees for equality, a feature that arises naturally in light of the unrankedness. Our main result is that the emptiness problem for this automaton model is decidable. Based upon this result, furthermore, we introduce a logic over data words (that is, words over an infinite alphabet) for which the satisfiability problem is decidable."]},{"key":"dc:source","label":"Dc Source","values":["Aachen : Publikationsserver der RWTH Aachen University VIII, 180 S. (2010). = Aachen, Techn. Hochsch., Diss., 2010"]},{"key":"dc:title","label":"Title","values":["Finite automata on unranked trees : extensions by arithmetical and equality constraints"]}]}],"canonical_facts":{"dc:contributor":["Löding, Christof","Thomas, Wolfgang","Schwentick, Thomas"],"dc:coverage":["DE"],"dc:creator":["Wong, Karianto"],"dc:date":["2010"],"dc:description":["The notion of unranked trees has attracted much interest in current research, especially due to their application as formal models of XML documents. In particular, several automata and logic formalisms on unranked trees have been considered (again) in the literature, and many results that had previously been shown for the ranked-tree setting have turned out to hold for the unranked-tree setting as well. In this thesis, we study two kinds of extensions of finite automata on unranked trees, namely, the extension by arithmetical constraints and the extension by subtree-equality constraints. In the first part of the thesis we introduce a framework of automata on unranked trees that unifies two different approaches to incorporating arithmetical constraints known from the literature, namely the global-constraint approach of Klaedtke and Rueß (2003) and the local-constraint approach of Seidl et al. (2003). We investigate the relationship between the two types of arithmetical constraints with respect to language recognition, and we show that the emptiness problem for this automaton model is decidable. In the second part of this thesis, we introduce automata on unranked trees that are equipped with equality and disequality constraints between direct subtrees, thereby extending the corresponding automaton model in the ranked-tree setting, which was introduced by Bogaert and Tison (1982). In the definition of the automaton model, we propose using formulas of monadic second-order logic to capture the possibility of comparing unboundedly many direct subtrees for equality, a feature that arises naturally in light of the unrankedness. Our main result is that the emptiness problem for this automaton model is decidable. Based upon this result, furthermore, we introduce a logic over data words (that is, words over an infinite alphabet) for which the satisfiability problem is decidable."],"dc:identifier":["https://publications.rwth-aachen.de/record/63210","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124657%22"],"dc:language":["eng"],"dc:publisher":["Publikationsserver der RWTH Aachen University"],"dc:relation":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-33834"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:source":["Aachen : Publikationsserver der RWTH Aachen University VIII, 180 S. (2010). = Aachen, Techn. Hochsch., Diss., 2010"],"dc:subject":["info:eu-repo/classification/ddc/004","Automatentheorie","Baumautomat","Monadische Logik","Presburger-Arithmetik","Informatik","Automaten auf unbeschränkt verzweigten Bäumen","monadische Logik zweiter Stufe","Gleichheitsbedingungen und Ungleichheitsbedingungen","unranked tree automata","Presburger arithmetic","monadic second-order logic","equality and disequality constraints"],"dc:title":["Finite automata on unranked trees : extensions by arithmetical and equality constraints"],"dc:type":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]},"updated_at":"2026-07-30T19:43:35Z"}