More about complexity and decidability
Michel,
Thanks for sending that excerpt (below) to SUO
list. Since many people working on ontology
don't pay much attention to theoretical papers
in mathematics, I'd like to comment about the
relevance of such work.
The basic point of the paper is the following
restriction: "all quantifications are bounded
by some variables". This kind of restriction
is very common for most practical applications.
For database queries and constraints, an even
stronger restriction holds: every quantifier is
bounded by a *constant*, namely the cardinality
(number of rows) of the corresponding table.
In natural languages, it is extremely rare to
find any sentence with an unrestricted quantifier.
Even when the word "everything" is used, some
implicit domain is almost always intended.
Furthermore, those domains are almost always
finite. (The major exceptions are books, papers,
and courses on mathematics.)
In logic, a noun phrase such as "every employee"
maps to a typed, sorted, or restricted quantifier
of the form (Ax:Employee). Those quantifiers
usually have a constant upper bound, although
that bound may be very large for the domains
of people, bacteria, or web pages.
This means that for most practical applications,
theories stated in first-order logic with restricted
quantifiers are decidable. However, the domains
might be so large that even a polynomial amount
of time is beyond the age of the universe.
Bottom line: The most important issue is
scalability, not decidability.
John Sowa
-------- Original Message --------
Subject: RudimentaryRelationsToolbox -- extract
Date: Wed, 18 Aug 2004 11:48:43 +0200
From: Michel Eytan <eytan@umb.u-strasbg.fr>
To: standard-upper-ontology@listserv.ieee.org
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