Spectrum hierarchies and subdiagonal functions

被引:5
作者
Hunter, A [1 ]
机构
[1] Simon Fraser Univ, Dept Comp Sci, Burnaby, BC V5A 1S6, Canada
来源
18TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS | 2003年
关键词
D O I
10.1109/LICS.2003.1210068
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The spectrum of a first-order sentence is the set of cardinalities of its finite models. Relatively little is known about the subclasses of spectra that are obtained by looking only at sentences with a specific signature. In this paper we study natural subclasses of spectra and their closure properties under simple subdiagonal functions. We show that many natural closure properties turn out to be equivalent to the collapse of potential spectrum hierarchies. We prove all of our results using explicit transformations on first-order structures.
引用
收藏
页码:281 / 290
页数:10
相关论文
共 12 条
[1]  
Asser G, 1955, Z MATH LOGIK GRUNDLA, V1, P252
[2]  
Chang CC., 1973, MODEL THEORY
[3]  
Durand A, 1998, LECT NOTES COMPUT SC, V1414, P189, DOI 10.1007/BFb0028015
[4]   First-order spectra with one binary predicate [J].
Durand, A ;
Ranaivoson, S .
THEORETICAL COMPUTER SCIENCE, 1996, 160 (1-2) :305-320
[5]  
FAGIN R, 1975, Z MATH LOGIK, V21, P123, DOI 10.1002/malq.19750210117
[6]  
Fagin Ronald, 1974, Complexity of Computation, P43
[7]   UNIVERSAL QUANTIFIERS AND TIME-COMPLEXITY OF RANDOM-ACCESS MACHINES [J].
GRANDJEAN, E .
MATHEMATICAL SYSTEMS THEORY, 1985, 18 (02) :171-187
[8]   1ST-ORDER SPECTRA WITH ONE VARIABLE [J].
GRANDJEAN, E .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1990, 40 (02) :136-153
[9]   TURING MACHINES AND SPECTRA OF FIRST-ORDER FORMULAS [J].
JONES, ND ;
SELMAN, AL .
JOURNAL OF SYMBOLIC LOGIC, 1974, 39 (01) :139-150
[10]   One unary function says less than two in existential second order logic [J].
Loescher, B .
INFORMATION PROCESSING LETTERS, 1997, 61 (02) :69-75