Hereditary undecidability of some theories of finite structures

Journal of Symbolic Logic 59 (4):1254-1262 (1994)

Abstract
Using a result of Gurevich and Lewis on the word problem for finite semigroups, we give short proofs that the following theories are hereditarily undecidable: (1) finite graphs of vertex-degree at most 3; (2) finite nonvoid sets with two distinguished permutations; (3) finite-dimensional vector spaces over a finite field with two distinguished endomorphisms
Keywords Undecidable theory   interpretable   finite graphs   word problem
Categories (categorize this paper)
DOI 10.2307/2275703
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 45,685
Through your library

References found in this work BETA

Add more references

Citations of this work BETA

An Optimal Construction of Hanf Sentences.Benedikt Bollig & Dietrich Kuske - 2012 - Journal of Applied Logic 10 (2):179-186.

Add more citations

Similar books and articles

On Finite Rigid Structures.Yuri Gurevich & Saharon Shelah - 1996 - Journal of Symbolic Logic 61 (2):549-562.
Finite Mathematics.Shaughan Lavine - 1995 - Synthese 103 (3):389 - 420.
The Ordertype of Β-R.E. Sets.Klaus Sutner - 1990 - Journal of Symbolic Logic 55 (2):573-576.
The First-Order Structure of Weakly Dedekind-Finite Sets.A. C. Walczak-Typke - 2005 - Journal of Symbolic Logic 70 (4):1161 - 1170.
Pseudo-Finite Homogeneity and Saturation.Jörg Flum & Martin Ziegler - 1999 - Journal of Symbolic Logic 64 (4):1689-1699.
Finitary Sketches.J. Adámek, P. T. Johnstone, J. A. Makowsky & J. Rosický - 1997 - Journal of Symbolic Logic 62 (3):699-707.

Analytics

Added to PP index
2009-01-28

Total views
36 ( #248,593 of 2,280,832 )

Recent downloads (6 months)
6 ( #195,919 of 2,280,832 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature