2012/01/24 by Martin Huschenbett, Huschenbett, Martin
Computer Science · #Algorithms and Data Compression #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Natural Language Processing Techniques #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1201.5070
openalex publication_date 2012/01/24 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
A tree automatic structure is a structure whose domain can be encoded by a\nregular tree language such that each relation is recognisable by a finite\nautomaton processing tuples of trees synchronously. Words can be regarded as\nspecific simple trees and a structure is word automatic if it is encodable\nusing only these trees. The question naturally arises whether a given tree\nautomatic structure is already word automatic. We prove that this problem is\ndecidable for tree automatic scattered linear orderings. Moreover, we show that\nin case of a positive answer a word automatic presentation is computable from\nthe tree automatic presentation.\n