Tree-automatic scattered linear orders

DOI10.1016/J.TCS.2016.02.008MaRDI QIDQ264574zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Bakhadyr Khoussainov, Philipp Schlicht, Sanjay Jain, Frank Stephan

Publication date 31 March 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.02.008

zbMATH Keywords

automatic structureslinear orderstree automata

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Computable structure theory, computable model theory (03C57) Total orders (06A05)

Recommendations

• Word automaticity of tree automatic scattered linear orderings is decidable
• Isomorphisms of scattered automatic linear orders
• Structures without scattered-automatic presentation
• Automatic linear orders and trees
• Isomorphisms of scattered automatic linear orders

Cites work

• scientific article; zbMATH DE number 3841819 (Why is no real title available?)
• scientific article; zbMATH DE number 5605134 (Why is no real title available?)
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 2086419 (Why is no real title available?)
• scientific article; zbMATH DE number 806750 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• A hierarchy of tree-automatic structures
• Automata Presenting Structures: A Survey of the Finite String Case
• Automata on ordinals and automaticity of linear orders
• Automatic Structures: Richness and Limitations
• Automatic linear orders and trees
• Automaticity of ordinals and of homogeneous graphs
• Breaking up finite automata presentable torsion-free Abelian groups.
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Decision methods in the theory of ordinals
• Finite automata and ordinals
• Finite automata presentable Abelian groups
• Isomorphisms of scattered automatic linear orders
• MSO on the Infinite Binary Tree: Choice and Order
• Model-theoretic complexity of automatic structures
• Monadic theories of wellorders
• On direct products of automaton decidable theories
• Pumping for ordinal-automatic structures1
• Rabin's uniformization problem
• STACS 2004
• Size and computation of injective tree automatic presentations
• The additive group of the rationals does not have an automatic presentation
• The isomorphism problem for \(\omega \)-automatic trees
• The isomorphism problem on classes of automatic structures with transitive relations
• The rank of tree-automatic linear orderings
• Three lectures on automatic structures
• Transforming structures by set interpretations
• Word automaticity of tree automatic scattered linear orderings is decidable

Cited in

(12)

• Automatic linear orders and trees
• scientific article; zbMATH DE number 2051168 (Why is no real title available?)
• Isomorphism of regular trees and words
• Scattered Context-Free Linear Orderings
• Word automaticity of tree automatic scattered linear orderings is decidable
• Structures without scattered-automatic presentation
• scientific article; zbMATH DE number 2053214 (Why is no real title available?)
• Isomorphisms of scattered automatic linear orders
• The isomorphism problem for tree-automatic ordinals with addition
• Interpretations in trees with countably many branches
• Isomorphisms of scattered automatic linear orders
• The order type of scattered context-free orderings of rank one is computable

This page was built for publication: Tree-automatic scattered linear orders

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