AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
From MaRDI portal
Publication:5207571
DOI10.1017/JSL.2019.26zbMATH Open1454.03042OpenAlexW2943660833WikidataQ128022821 ScholiaQ128022821MaRDI QIDQ5207571FDOQ5207571
Authors: Matthew Harrison-Trainor, Alexander Melkinov, Keng Meng Ng, Nikolay Bazhenov, Iskander Kalimullin 
Publication date: 10 January 2020
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/d9c69d527e944c7bd20ae8dd5ee2b0e37354d1e5
Recommendations
- There is no classification of the decidably presentable structures
- Automatic Structures: Richness and Limitations
- Searching for applicable versions of computable structures
- Size and computation of injective tree automatic presentations
- Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree
- Finite presentations of infinite structures: Automata and interpretations
- Finitely generated structures computable in polynomial time
- Automata Presenting Structures: A Survey of the Finite String Case
- Polynomial-time versus recursive models
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Recursive functions and relations, subrecursive hierarchies (03D20) Applications of computability and recursion theory (03D80)
Cites Work
- On direct products of automaton decidable theories
- Automaticity of ordinals and of homogeneous graphs
- 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.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Automatic Structures: Richness and Limitations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Logical Reversibility of Computation
- Model-theoretic complexity of automatic structures
- Finite automata presentable Abelian groups
- Strong and weak constructivization and computable families
- Computable structures and the hyperarithmetical hierarchy
- From automatic structures to automatic groups.
- Title not available (Why is that?)
- Combinatorial group theory.
- The classification problem for torsion-free abelian groups of finite rank
- CONSTRUCTIVE ALGEBRAS I
- Computable completely decomposable groups
- Effective procedures in field theory
- Computable Algebra, General Theory and Theory of Computable Fields
- Polynomial-time versus recursive models
- Polynomial-time Abelian groups
- Existence and uniqueness of structures computable in polynomial time
- Title not available (Why is that?)
- Title not available (Why is that?)
- Describing free groups
- Describing free groups. II: \(\Pi ^{0}_{4}\) hardness and no \(\Sigma _{2}^{0}\) basis
- Recursive Pseudo-Well-Orderings
- The isomorphism relation on countable torsion free abelian groups
- The isomorphism problem for torsion-free abelian groups is analytic complete
- Unary automatic graphs: an algorithmic perspective
- Title not available (Why is that?)
- The complexity of computable categoricity
- STACS 2005
- Title not available (Why is that?)
- The index set of linear orderings that are autostable relative to strong constructivizations
- Space complexity of abelian groups
- Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
- Title not available (Why is that?)
- Algebraic structures computable without delay
- Recursive well-orderings
- Enumerations of families of general recursive functions
- Advice Automatic Structures and Uniformly Automatic Classes
- On some games which are relevant to the theory of recursively enumerable sets
- Eliminating unbounded search in computable algebra
- The diversity of categoricity without delay
- Index sets for classes of high rank structures
- The decomposability problem for torsion-free abelian groups is analytic-complete
- Title not available (Why is that?)
- Title not available (Why is that?)
- Semiautomatic structures
- There is no classification of the decidably presentable structures
- Finitely generated semiautomatic groups
- The Mate-in-n Problem of Infinite Chess Is Decidable
Cited In (30)
- Automatic Structures: Richness and Limitations
- STACS 2004
- PUNCTUAL CATEGORICITY AND UNIVERSALITY
- Punctually presented structures I: Closure theorems
- Effective categoricity of automatic equivalence and nested equivalence structures
- Automatic structures and the theory of lists
- Computable embeddability for algebraic structures
- A note on decidable categoricity and index sets
- Size and computation of injective tree automatic presentations
- A note on computable distinguishing colorings
- Non-density in punctual computability
- Title not available (Why is that?)
- On two types of concept lattices in the theory of numberings
- Punctual copies of algebraic structures
- Online presentations of finitely generated structures
- Punctual definability on structures
- The complexity of inversion in groups
- Semiautomatic structures
- There is no classification of the decidably presentable structures
- Rogers semilattices of punctual numberings
- Punctual structures and primitive recursive reducibility
- Title not available (Why is that?)
- Semiautomatic structures
- Computable topological abelian groups
- Advice Automatic Structures and Uniformly Automatic Classes
- Automatic Structures of Bounded Degree Revisited
- Title not available (Why is that?)
- FOUNDATIONS OF ONLINE STRUCTURE THEORY
- Quotient structures and groups computable in polynomial time
- Definable Subsets of Polynomial-Time Algebraic Structures
This page was built for publication: AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207571)
