AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
From MaRDI portal
Publication:5207571
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)
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
Cites work
- scientific article; zbMATH DE number 5605134 (Why is no real title available?)
- scientific article; zbMATH DE number 4148067 (Why is no real title available?)
- scientific article; zbMATH DE number 5379427 (Why is no real title available?)
- scientific article; zbMATH DE number 53661 (Why is no real title available?)
- scientific article; zbMATH DE number 194103 (Why is no real title available?)
- scientific article; zbMATH DE number 3628930 (Why is no real title available?)
- scientific article; zbMATH DE number 2040323 (Why is no real title available?)
- scientific article; zbMATH DE number 2047478 (Why is no real title available?)
- scientific article; zbMATH DE number 806746 (Why is no real title available?)
- scientific article; zbMATH DE number 1421070 (Why is no real title available?)
- scientific article; zbMATH DE number 1450824 (Why is no real title available?)
- scientific article; zbMATH DE number 5175704 (Why is no real title available?)
- scientific article; zbMATH DE number 3332554 (Why is no real title available?)
- scientific article; zbMATH DE number 3406215 (Why is no real title available?)
- Advice Automatic Structures and Uniformly Automatic Classes
- Algebraic structures computable without delay
- Automatic Structures: Richness and Limitations
- Automaticity of ordinals and of homogeneous graphs
- Breaking up finite automata presentable torsion-free Abelian groups.
- CONSTRUCTIVE ALGEBRAS I
- Combinatorial group theory.
- Computable Algebra, General Theory and Theory of Computable Fields
- Computable completely decomposable groups
- Computable structures and the hyperarithmetical hierarchy
- Describing free groups
- Describing free groups. II: \(\Pi ^{0}_{4}\) hardness and no \(\Sigma _{2}^{0}\) basis
- Effective procedures in field theory
- Eliminating unbounded search in computable algebra
- Enumerations of families of general recursive functions
- Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
- Existence and uniqueness of structures computable in polynomial time
- Finite automata presentable Abelian groups
- Finitely generated semiautomatic groups
- From automatic structures to automatic groups.
- Index sets for classes of high rank structures
- Logical Reversibility of Computation
- Model-theoretic complexity of automatic structures
- On direct products of automaton decidable theories
- On some games which are relevant to the theory of recursively enumerable sets
- Polynomial-time Abelian groups
- Polynomial-time versus recursive models
- Recursive Pseudo-Well-Orderings
- Recursive well-orderings
- STACS 2005
- Semiautomatic structures
- Space complexity of abelian groups
- Strong and weak constructivization and computable families
- The Mate-in-n Problem of Infinite Chess Is Decidable
- The additive group of the rationals does not have an automatic presentation
- The classification problem for torsion-free abelian groups of finite rank
- The complexity of computable categoricity
- The decomposability problem for torsion-free abelian groups is analytic-complete
- The diversity of categoricity without delay
- The index set of linear orderings that are autostable relative to strong constructivizations
- The isomorphism problem for torsion-free abelian groups is analytic complete
- The isomorphism relation on countable torsion free abelian groups
- There is no classification of the decidably presentable structures
- Three lectures on automatic structures
- Unary automatic graphs: an algorithmic perspective
Cited in
(30)- Definable Subsets of Polynomial-Time Algebraic Structures
- 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
- Punctual copies of algebraic structures
- scientific article; zbMATH DE number 1747445 (Why is no real title available?)
- Online presentations of finitely generated structures
- Punctual definability on structures
- On two types of concept lattices in the theory of numberings
- The complexity of inversion in groups
- Semiautomatic structures
- Punctual structures and primitive recursive reducibility
- There is no classification of the decidably presentable structures
- Rogers semilattices of punctual numberings
- scientific article; zbMATH DE number 3921962 (Why is no real title available?)
- Semiautomatic structures
- Computable topological abelian groups
- Automatic Structures of Bounded Degree Revisited
- Advice Automatic Structures and Uniformly Automatic Classes
- scientific article; zbMATH DE number 7407778 (Why is no real title available?)
- FOUNDATIONS OF ONLINE STRUCTURE THEORY
- Quotient structures and groups computable in polynomial time
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)
