AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES

DOI10.1017/jsl.2019.26zbMath1454.03042OpenAlexW2943660833WikidataQ128022821 ScholiaQ128022821MaRDI QIDQ5207571

Keng Meng Ng, Matthew Harrison-Trainor, Alexander Melkinov, Iskander Sh. Kalimullin, Nikolay Bazhenov

Publication date: 10 January 2020

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/d9c69d527e944c7bd20ae8dd5ee2b0e37354d1e5

zbMATH Keywords

computable structurespolynomial-time presentable structureautomata presentable structure

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Recursive functions and relations, subrecursive hierarchies (03D20) Applications of computability and recursion theory (03D80) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items (19)

Definable Subsets of Polynomial-Time Algebraic Structures ⋮ Rogers semilattices of punctual numberings ⋮ Punctual structures and primitive recursive reducibility ⋮ Punctual copies of algebraic structures ⋮ On two types of concept lattices in the theory of numberings ⋮ Effective categoricity of automatic equivalence and nested equivalence structures ⋮ Punctually presented structures I: Closure theorems ⋮ The complexity of inversion in groups ⋮ A note on decidable categoricity and index sets ⋮ Online presentations of finitely generated structures ⋮ A note on computable distinguishing colorings ⋮ Punctual definability on structures ⋮ Non-density in punctual computability ⋮ FOUNDATIONS OF ONLINE STRUCTURE THEORY ⋮ Unnamed Item ⋮ Quotient structures and groups computable in polynomial time ⋮ PUNCTUAL CATEGORICITY AND UNIVERSALITY ⋮ Computable topological abelian groups ⋮ Computable embeddability for algebraic structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Existence and uniqueness of structures computable in polynomial time
• The complexity of computable categoricity
• Algebraic structures computable without delay
• Model-theoretic complexity of automatic structures
• Finite automata presentable Abelian groups
• The isomorphism problem for torsion-free abelian groups is analytic complete
• Space complexity of abelian groups
• On direct products of automaton decidable theories
• Polynomial-time versus recursive models
• Polynomial-time Abelian groups
• Strong and weak constructivization and computable families
• Enumerations of families of general recursive functions
• On some games which are relevant to the theory of recursively enumerable sets
• Computable structures and the hyperarithmetical hierarchy
• Combinatorial group theory.
• The diversity of categoricity without delay
• Semiautomatic structures
• Automaticity of ordinals and of homogeneous graphs
• Eliminating unbounded search in computable algebra
• From automatic structures to automatic groups.
• Describing free groups
• Describing free groups, Part II: Π⁰₄ hardness and no Σ₂⁰ basis
• The Mate-in-n Problem of Infinite Chess Is Decidable
• Three Lectures on Automatic Structures
• The additive group of the rationals does not have an automatic presentation
• BREAKING UP FINITE AUTOMATA PRESENTABLE TORSION-FREE ABELIAN GROUPS
• Computable completely decomposable groups
• Recursive well-orderings
• Effective procedures in field theory
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• Unary automatic graphs: an algorithmic perspective
• There is no classification of the decidably presentable structures
• Finitely generated semiautomatic groups
• The classification problem for torsion-free abelian groups of finite rank
• The isomorphism relation on countable torsion free abelian groups
• Advice Automatic Structures and Uniformly Automatic Classes
• The decomposability problem for torsion-free abelian groups is analytic-complete
• Automatic Structures: Richness and Limitations
• CONSTRUCTIVE ALGEBRAS I
• Index sets for classes of high rank structures
• Computable Algebra, General Theory and Theory of Computable Fields
• Recursive Pseudo-Well-Orderings
• Logical Reversibility of Computation
• STACS 2005

This page was built for publication: AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES