Tree-automatic scattered linear orders

DOI10.1016/J.TCS.2016.02.008zbMATH Open1339.03030DBLPjournals/tcs/JainKSS16OpenAlexW2253092483WikidataQ59864155 ScholiaQ59864155MaRDI QIDQ264574FDOQ264574

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

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

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)

Cites Work

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

Cited In (12)

• Automatic linear orders and trees
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)