Isomorphisms of scattered automatic linear orders
From MaRDI portal
Publication:2446106
DOI10.1016/j.tcs.2014.03.022zbMath1358.03062arXiv1204.5653MaRDI QIDQ2446106
Publication date: 16 April 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1204.5653
03D35: Undecidability and degrees of sets of sentences
03D05: Automata and formal grammars in connection with logical questions
03C57: Computable structure theory, computable model theory
Related Items
Tree-automatic scattered linear orders, The isomorphism problem for tree-automatic ordinals with addition, The ordinal generated by an ordinal grammar is computable
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- On direct products of automaton decidable theories
- Finite presentations of infinite structures: Automata and interpretations
- Automaticity of ordinals and of homogeneous graphs
- An undecidable property of context-free linear orders
- Isomorphism of regular trees and words
- The FC-rank of a context-free language
- Deciding the isomorphism problem in classes of unary automatic structures
- The isomorphism problem on classes of automatic structures with transitive relations
- Logical Aspects of the Lexicographic Order on 1-Counter Languages
- Cayley Graph Automatic Groups Are Not Necessarily Cayley Graph Biautomatic
- A Context-Free Linear Ordering with an Undecidable First-Order Theory
- The Rank of Tree-Automatic Linear Orderings
- BREAKING UP FINITE AUTOMATA PRESENTABLE TORSION-FREE ABELIAN GROUPS
- What’s Decidable about Weighted Automata?
- Automata Presenting Structures: A Survey of the Finite String Case
- Describing Groups
- Decision Problems of Finite Automata Design and Related Arithmetics
- THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
- Automatic linear orders and trees
- Automatic Structures: Richness and Limitations