Word automaticity of tree automatic scattered linear orderings is decidable

DOI10.1007/978-3-642-30870-3_32MaRDI QIDQ2904421zbMATH OpenOpenAlexFDO

Authors Martin Huschenbett

Publication date 14 August 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.5070

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Computable structure theory, computable model theory (03C57) Automata and formal grammars in connection with logical questions (03D05)

Abstract: A tree automatic structure is a structure whose domain can be encoded by a regular tree language such that each relation is recognisable by a finite automaton processing tuples of trees synchronously. Words can be regarded as specific simple trees and a structure is word automatic if it is encodable using only these trees. The question naturally arises whether a given tree automatic structure is already word automatic. We prove that this problem is decidable for tree automatic scattered linear orderings. Moreover, we show that in case of a positive answer a word automatic presentation is computable from the tree automatic presentation.

Recommendations

• Tree-automatic scattered linear orders
• Structures without scattered-automatic presentation
• Tree Automata and Automata on Linear Orderings
• Isomorphisms of scattered automatic linear orders
• Isomorphisms of scattered automatic linear orders

Cited in

(8)

• Isomorphism of regular trees and words
• Isomorphisms of scattered automatic linear orders
• Tree-automatic scattered linear orders
• scientific article; zbMATH DE number 2053214 (Why is no real title available?)
• Isomorphisms of scattered automatic linear orders
• Structures without scattered-automatic presentation
• Tree-automatic well-founded trees
• On automatic and decidable linear orderings

This page was built for publication: Word automaticity of tree automatic scattered linear orderings is decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904421)