RudimentaryRelationsToolbox -- extract
Folks,
here is a (non-authorized) extract from the paper with above title -- the
field is vast: I have copied the References infra... I hope I am not too far
from the discussion on Complexity and Decidadability:
> Theoretical Computer Science 193 (1998) 129-148
> Rudimentary relations and primitive recursion: A toolbox
> Henri-Alex EsbelinÓ,Ò, Malika More
> LLAICI. IUT Clermont I, BP 86, 63172 Aubi?re Cedex, France
> bDkpartement de MathPmatiques. UniversitP de Caen, 14032 Caen. France
> Received October 1996; revised December 1996
> Communicated by M. Nivat
>
> Abstract
> Rudimentary relations are those relations over natural integers that are
>defined by a first-order
> arithmetical formula, in which all quantifications are bounded by some
>variables. The question of
> whether a given primitive recursive relation is rudimentary is in some
>cases difficult and related
> to several well-known open questions in theoretical computer science. In
>this paper, we present
> systematic tools to study this question, and various applications. One of
>them gives a sufficient
> condition of the collapsing of the first classes of the GrzegorczykÕs
>hierarchy.
>
> Definition 1.1. Let us denote by R the smallest class of relations over
>integers containing
> the graphs of addition and multiplication (seen as ternary relations) and
>closed
> under the following operations:
> l boolean operations (not, and, or, impl);
> l explicit transformations, i.e. adding, cancelling, renaming, permuting
>and confusing
> variables, (see a precise definition in [24]);
> l variable bounded quantifications (i.e. Allx <y impl . . . meaning Allx
>(x<Y . . .) and Existx <
> Y . . . meaning Existx (x < y A . . .).
>
> R is intriguing: rudimentary relations are linked with a lot of well-known
>open
> questions in computational complexity, finite model theory, weak
>arithmetics and recursivity
> theory. Let us denote by RUD the class of rudimentary sets (i.e. unary
> rudimentary relations) and by L2(RUD) the class of their dyadic
>representations
> (Òrudimentary languagesÓ). Wrathall proved that reasonable encoding of k-ary
> H.-A. Esbelin, M. Morel Theoretical Computer Science 193 (1998) 125148 131
> rudimentary relations into languages provides rudimentary languages (see
>[27]), so
> that whenever it is convenient we confuse the two notions.
> In computationul complexity theory, L2(RUD) is proved to be equal to the
> linear hierarchy LinH defined in [27], and consequently that L2(RUD) contains
> NLINTIME. Nepomnjascii proved that Qz(RUD) contains LOGSPACE, Myhil proved
> that f!z(RUD) is contained in LZNSPACE (see [18,21]), hence f!z(RUD) is
>also contained
> in NEXPTIME, but none of these inclusions is known to be strict. Also, it is
> known that &(RUD) contains many NP-complete problems, namely all the
>classical
> problems listed by Karp in [ 121 (see also [ 171).
> In descriptive complexity, RUD is equal to a class of binary spectra (see
>[26]). The
> question whether RUD contains all binary spectra is still open, and a
>positive answer
> would imply NP #co - NP. On the other hand, (second-order) spectra are
>represented
> in rudimentary sets up to some exponential functions (see [ 171). Also,
>concerning finite
> model theory, it is proved that L2(RUD) corresponds to monadic second-order
>logic
> with addition (see [ 171).
> In formal languages theory, L2(RUD) is proved to be the smallest class of
>languages
> containing the regular languages and { 1Ó2Ó, n > 0) and closed under boolean
> operations, inverse homomorphisms and length-preserving homomorphisms (see
>[27]).
> Jones proved that L2(RUD) strictly contains context-free languages (see [
>111) and Myhi1
> proved it is contained into context-sensitive languages (see [ 1 S]), but
>none of these
> inclusions is known to be strict.
[snip]
References
[I] J.H. Bennett, On Spectra, Doctoral Dissertation, Princeton University,
Princeton, NJ, 1962.
[2] P. Cegielski, Le thtoreme de Dirichlet est finitiste, Preprint LITP
92.40, Universite Paris 6-Paris 7,
1992.
[3] C. Dimitracopoulos, MatijasevicÕs theorem and fragments of arithmetic,
Ph. D. Thesis, University of
Manchester, 1980.
[4] H.A. Esbelin, Relations rudimentaires et petites classes de fonctions
recursives. Doctoral Dissertation,
Universite dÕAuvergne, 1994.
[5] H.A. Esbelin, Une classe minimale de fonctions recursives contenant les
relations rudimentaires, C. R.
Acad. Sci. Paris, Serie I, Paris, 1994, pp. 505-508.
[6] H.A. Esbelin, M. More, LÕensemble des nombres de Fibonacci est
rudimentaire, Preprint LLAICI, 39,
Universite dÕAuvergne, 1994.
[7] K. Godel, Uber formal unentscheidbare Siitze der Principia Mathematics
und verwandter Systeme, I.
Monatshefte fur Math. Phys. 38 (193 I ) 173-198.
[8] A. Grzegorczyk, Some Classes of Recursive Functions, Rozprawy
Matematyczne 4 (1953) l-46.
[9] K. Harrow, Sub-elementary classes of functions and relations, Doctoral
Dissertation, New York
University, Department of Mathematics, 1973.
[lo] K. Harrow, Small Grzegorczyk classes and limited minimum, Z. Math. Logik
Grundlagen Math. I I
(1975) 417-426.
[I I] N.D. Jones, Context-free languages and rudimentary attributes, Math.
System Theory 3 (1969) 102-109.
[12] R.M. Karp, Reducibility among combinatorial problems, IBM Symp. 1972,
Complexity of Computers
Computations, Plenum Press, New York, 1972.
[I31 M. Kutylovski, Small Grzegorczyk classes, J. London Math. Sot. 2 (36)
(1987) 1933210.
[14] J. Malifaud, Contribution a IÕttude des fonctions calculables de
croissance limit&, Doctoral Dissertation,
Universite Paris 7, 1985.
[ 151 J. Meloul, Rudimentary predicates, low complexity classes and related
automata, Ph.D. Dissertation,
Oxford University, 1979.
[I61 M. More, Rudimentary representations of spectra, Prepublication du
LLAICI, Numero 40, 1994.
[ 171 M. More, F. Olive, Rudimentary languages and second-order logic,
Preprint GRAL, 1996-1, 1996.
[I 81 G. Myhill, Linear bounded automata, Wright Air Devel. Div., Tech. Note
60-165, Wright-Patterson
Air Force Base, OH, 1960.
[I91 J.B. Paris, A.J. Wilkie, Counting Ac sets, Fund. Math. 127 (1987).
[20] W. Quine, Concatenation as a basis for arithmetic from a logical point
of view, J. Symbol. Logic I I
(1946) I0551 14. Selected Logic Papers, Random House, 1966, ch. V, pp. 70-82.
[2l] R.W. Ritchie, Classes of Predictably Computable Functions, Trans. Amer.
Math. Sot. 106 (1963)
139-173.
[22] H.Jr. Rogers, Theory of Recursive Functions and Effective Computability,
McGraw-Hill, New York,
1967.
[23] H. Shapiro, Introduction to the Theory of numbers, Wiley, New York, 1982.
[23] H. Shapiro, Introduction to the Theory of numbers, Wiley, New York, 1982.
148 H.-A. Esbelin, M. Morel Theoretical Computer Science 193 11998) 129-148
[24] R. Smullyan, Theory of Formal Systems, Ann. Math. Studies, vol. 47,
Princeton University Press,
Princeton, NJ, 196 1.
[25] L.J. Stockmeyer, The polynomial time hierarchy, Theor. Comput. Sci. 3
(1976) l-22.
[26] A. Woods, Some problems in logic and number theory, and their
connections, Doctoral Dissertation,
University of Manchester, 1981.
[27] C. Wrathall, Rudimentary predicates and relative computation, SIAM J
Comput. 7(2) (1978) 194-209.
[28] C. Calude, Super-exponential non primitive recursive, but rudimentary,
Information Processing Letters
25 (1987) 311-315.
--
Michel Eytan eytan@umb.u-strasbg.fr
I say what I mean and mean what I say