Comparing Classes of Finite Structures

DOI10.1023/B:ALLO.0000048827.30718.2CMaRDI QIDQ5476777zbMATH OpenOpenAlexFDO

Authors Wesley Calvert, D. F. Cummins, Sara Miller, J. F. Knight

Publication date 18 July 2006

Published in Algebra and Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0803.3291

zbMATH Keywords

computable transformation of the class of structurese-reducibilityfinite modelfinite structure

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Computable structure theory, computable model theory (03C57) Other degrees and reducibilities in computability and recursion theory (03D30) Theory of numerations, effectively presented structures (03D45)

Abstract: We introduce a reducibility on classes of structures, essentially a uniform enumeration reducibility. This reducibility is inspired by the Friedman-Stanley paper on using Borel reductions to compare classes of countable structures. This reducibility is calibrated by comparing several classes of structures. The class of cyclic graphs and the class of finite prime fields are equivalent, and are properly below the class of arbitrary finite graphs. The class of finite graphs and the class of finite linear orders are maximal among all classes of finite structures. We also prove some general characterizations of reducibility to certain classes. Examples of large chains and antichains of classes are constructed.

Recommendations

• Isomorphism relations on computable structures
• Computable transformations of structures
• Equivalence Relations on Classes of Computable Structures
• Reducibilities among equivalence relations induced by recursively enumerable structures
• scientific article; zbMATH DE number 701112

Cited in

(35)

• Index sets for some classes of structures
• Scott sentences for certain groups
• Computable transformations of structures
• Turing computable embeddings, computable infinitary equivalence, and linear orders
• Computable embeddings for pairs of linear orders
• A note on computable embeddings for ordinals and their reverses
• Learning families of algebraic structures from informant
• Using computability to measure complexity of algebraic structures and classes of structures
• On the degree structure of equivalence relations under computable reducibility
• Index set of structures with two equivalence relations that are autostable relative to strong constructivizations
• On functors enumerating structures
• Computable embeddings of classes of structures under enumeration and Turing operators
• Learning algebraic structures with the help of Borel equivalence relations
• Comparing classes of finite sums
• Finitary reducibility on equivalence relations
• On Σ¹ ₁ equivalence relations over the natural numbers
• Equivalence Relations on Classes of Computable Structures
• scientific article; zbMATH DE number 2047478 (Why is no real title available?)
• Measuring complexities of classes of structures
• INTERPRETING A FIELD IN ITS HEISENBERG GROUP
• Categoricity spectra for polymodal algebras
• CODING IN GRAPHS AND LINEAR ORDERINGS
• Computability theoretic classifications for classes of structures
• Isomorphism relations on computable structures
• Turing computable embeddings of equivalences other than isomorphism
• Copyable structures
• Ranked structures and arithmetic transfinite recursion
• Agreement reducibility
• On the effective universality of mereological theories
• Classes of algebraic structures
• On learning for families of algebraic structures
• A Lopez-Escobar theorem for continuous domains
• The computable embedding problem
• Learning families of algebraic structures from text
• Computable numberings of the class of Boolean algebras with distinguished endomorphisms

This page was built for publication: Comparing Classes of Finite Structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5476777)