Automaticity of ordinals and of homogeneous graphs

DOI10.1016/j.crma.2004.03.035zbMath1077.68071OpenAlexW2025670714MaRDI QIDQ1876889

Christian Delhommé

Publication date: 20 August 2004

Published in: Comptes Rendus. Mathématique. Académie des Sciences, Paris (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.crma.2004.03.035

zbMATH Keywords

tree-automaticity

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05)

Related Items (28)

Tree-automatic scattered linear orders ⋮ Pumping for ordinal-automatic structures1 ⋮ UNARY FA-PRESENTABLE SEMIGROUPS ⋮ Height of a superposition ⋮ Automatic models of first order theories ⋮ Model Theoretic Complexity of Automatic Structures (Extended Abstract) ⋮ Automata Presenting Structures: A Survey of the Finite String Case ⋮ Semiautomatic structures ⋮ Effective categoricity of automatic equivalence and nested equivalence structures ⋮ A note on ordinal DFAs ⋮ An undecidable property of context-free linear orders ⋮ Model-theoretic complexity of automatic structures ⋮ Injection Structures Specified by Finite State Transducers ⋮ Isomorphisms of scattered automatic linear orders ⋮ Subalgebras of FA-presentable algebras. ⋮ Automatic Presentations for Cancellative Semigroups ⋮ Model-theoretic properties of \(\omega\)-automatic structures ⋮ The isomorphism relation between tree-automatic structures ⋮ The isomorphism problem for tree-automatic ordinals with addition ⋮ Tree-Automatic Well-Founded Trees ⋮ AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES ⋮ ALGEBRAIC LINEAR ORDERINGS ⋮ Automata on Ordinals and Linear Orders ⋮ Where Automatic Structures Benefit from Weighted Automata ⋮ Automatic presentations for semigroups. ⋮ The isomorphism problem on classes of automatic structures with transitive relations ⋮ On decidability of list structures ⋮ Complexity and categoricity of injection structures induced by finite state transducers

Cites Work

• Synchronized rational relations of finite and infinite words
• Theory of relations. Transl. from the French by P. Clote
• Arithmetic of ordinals with applications to the theory of ordered Abelian groups
• Unnamed Item
• Unnamed Item

This page was built for publication: Automaticity of ordinals and of homogeneous graphs