AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
From MaRDI portal
Computable structure theory, computable model theory (03C57) Automata and formal grammars in connection with logical questions (03D05) Recursive functions and relations, subrecursive hierarchies (03D20) Theory of numerations, effectively presented structures (03D45) Applications of computability and recursion theory (03D80) Formal languages and automata (68Q45)
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
- 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.
- Combinatorial group theory.
- Computable Algebra, General Theory and Theory of Computable Fields
- Computable completely decomposable groups
- Computable structures and the hyperarithmetical hierarchy
- CONSTRUCTIVE ALGEBRAS I
- 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.
- 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?)
- 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
- Semiautomatic structures
- Space complexity of abelian groups
- STACS 2005
- Strong and weak constructivization and computable families
- 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
- The Mate-in-n Problem of Infinite Chess Is Decidable
- There is no classification of the decidably presentable structures
- Three lectures on automatic structures
- Unary automatic graphs: an algorithmic perspective
Cited in
(39)- Semiautomatic structures
- A note on computable distinguishing colorings
- Punctual definability on structures
- Non-density in punctual computability
- Quotient structures and groups computable in polynomial time
- Computable topological abelian groups
- Punctual structures and primitive recursive reducibility
- Punctual copies of algebraic structures
- Effective categoricity of automatic equivalence and nested equivalence structures
- A note on decidable categoricity and index sets
- Online presentations of finitely generated structures
- Automatic structures and the theory of lists
- Size and computation of injective tree automatic presentations
- Automatic Structures of Bounded Degree Revisited
- scientific article; zbMATH DE number 3921962 (Why is no real title available?)
- scientific article; zbMATH DE number 1747445 (Why is no real title available?)
- There is no classification of the decidably presentable structures
- Semiautomatic structures
- Definable Subsets of Polynomial-Time Algebraic Structures
- Rogers semilattices of punctual numberings
- Advice Automatic Structures and Uniformly Automatic Classes
- Foundations of online structure theory. II: The operator approach
- FOUNDATIONS OF ONLINE STRUCTURE THEORY
- STACS 2004
- Automatic Structures: Richness and Limitations
- PUNCTUAL CATEGORICITY AND UNIVERSALITY
- Computable embeddability for algebraic structures
- On two types of concept lattices in the theory of numberings
- Punctually presented structures I: Closure theorems
- The complexity of inversion in groups
- Simple classes of automatic structures
- The existence of primitive recursive structures
- Description of structures computable in polynomial time
- Computably enumerable equivalence relations via primitive recursive reductions
- A pathological punctually 1-decidable structure
- Punctually presented structures. II: Comparing presentations.
- Structures of finite punctual dimension \(n>2\)
- Punctual presentability in certain classes of algebraic structures
- Punctual numberings for families of sets
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)
