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
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)
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