Effective categoricity of automatic equivalence and nested equivalence structures

DOI10.1007/S00224-020-09974-9zbMATH Open1485.03109OpenAlexW3016195883MaRDI QIDQ2195573FDOQ2195573

J. Carson, Jeffrey Remmel, Douglas Cenzer

Publication date: 26 August 2020

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-020-09974-9

zbMATH Keywords

automatic structurescomputable structureseffective categoricityequivalence structuresnested equivalence structuresonline structures

Mathematics Subject Classification ID

Categoricity and completeness of theories (03C35) Computable structure theory, computable model theory (03C57)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On direct products of automaton decidable theories
• Automaticity of ordinals and of homogeneous graphs
• The isomorphism problem on classes of automatic structures with transitive relations
• Three Lectures on Automatic Structures
• Automatic Structures: Richness and Limitations
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Generic copies of countable structures
• Weak Second‐Order Arithmetic and Finite Automata
• Effective categoricity of equivalence structures
• Complexity and categoricity
• Existence and uniqueness of structures computable in polynomial time
• Finite-State Processes and Dynamic Programming
• Deciding the isomorphism problem in classes of unary automatic structures
• Automata theory and its applications
• Unary automatic graphs: an algorithmic perspective
• Structures computable in polynomial time. I
• FOUNDATIONS OF ONLINE STRUCTURE THEORY
• Structures computable in polynomial time. II
• Categoricity for primitive recursive and polynomial Boolean algebras
• Atomless Boolean algebras computable in polynomial time
• The back-and-forth method and computability without delay
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• Injection Structures Specified by Finite State Transducers
• Automatic Equivalence Structures of Polynomial Growth.

Cited In (2)

• Complexity and categoricity of injection structures induced by finite state transducers
• Equivalence structures and isomorphisms in the difference hierarchy

This page was built for publication: Effective categoricity of automatic equivalence and nested equivalence structures

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