Comparing Classes of Finite Structures

Details Comparing Classes of Finite Structures Comparing Classes of Finite Structures

2008-03-22

arxiv.org/abs/0803.3291v1

Algebra and Logic 43 (2004), 374--392

Mathematics

Logic

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Comparing Classes of Finite Structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Comparing Classes of Finite Structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Comparing Classes of Finite Structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-528737