Minimality and Decidability Results Concerning

Generating Systems of

Primitive Recursive Functions

S?andor Horv?ath

Department of Computer Science

Eötvös Lor?and University

M?uzeum kör?ut 6-8., II. 2-3, Budapest

H-1088, Hungary

email: horvath@cs.elte.hu

Joint work with Holger Petersen

We consider the class of primitive recursive functions (the definition can be found in textbooks on computability, e.g. [3, 7, 8, 9]). As this class includes most of the functions usually encountered in elementary arithmetic it is of some interest to find simple characterizations for it. Significant simplifications in the recursion scheme employed in the definition of the primitive recursive functions have been found by Gladstone [4, 5]. Further research in this direction is reported in [2].

We are interested in the initial functions underlying the class of primitive recursive functions. We reduce the set of initial functions to a minimum that cannot be simplified further without losing some functions.
We also deal with the class of partial recursive functions and eliminate some initial functions from a known generating system for this class.
Finally, we consider some decidability questions concerning program length and recursiondepth.

Lemma 1 If from a set of initial functions all primitive recursive functions can be obtained by composition and primitive recursion then it necessarily contains an n- or (n + 1)-place function for every n >= 1.

Theorem 1 Every primitive recursive function can be obtained by a finite number of applications of composition and primitive recursion from the following functions:

1. The successor function S.

2. The projections U31 and U2n+5
2 , n >= 0.

Moreover this set of initial functions is minimal in the sense that not all primitive recursive functions can be obtained from a proper subset of these functions.

If the 0-place functions (constants) are also considered as primitive recursive we get the following statement:

Theorem 2 Every primitive recursive function including constants can be obtained by a finite number of applications of composition and primitive recursion from the initial functions given in the preceding theorem and any 0-place function. This set of initial functions is minimal.

Workshop 9 Stuttgart, January 1998

Seite 9: vorherige Seite | nächste Seite | Übersicht

It is possible to show results analogous to the preceding theorem if the role of the projection U31 is interchanged with U2m+1
1 for some m >= 2 (U31 is replaced by U32 and U2m+1
2 is replaced
by U2m+1
1 ). If ? is added to the operations in Theorem 1 all partial recursive functions can be derived. However Lemma 1 does not remain valid. We have:

Theorem 3 Every partial recursive function can be obtained by a finite number of applications of composition, primitive recursion, and unbounded minimization from the initial functions S, U31, and any infinite subset of fUk2 j k >= 2g.

In [6] a generating system for the set of partial recursive functions is given equipped with the initial functions N , U11, and S. Its operations are composition, primitive recursion, minimization, and attachments of new variables to the left or to the right. The function N can be omitted by applying ? to U21. From Theorem 1 we get another reduction of the set of initial functions:

Theorem 4 Every partial recursive function can be obtained from the initial functions S and N by composition, primitive recursion, minimization, and attachments of new variables.

By a standard numerical encoding of the representations of the one-place partial recursive functions (in Kleene's classical generating system), regarding the code numbers as \abstract programs", and assigning to every abstract program, as its \length", the length of the original representation (of the corresponding partial recursive function), we clearly get an (axiomatic) Blum program size measure. Within the above encoding, the (abstract) programs of the one-place primitive recursive functions form a subrecursive enumeration, see [1]. So by a general result we have that the set SP (primrec) of the shortest programs of the one-place primitive recursive functions is recursively enumerable. On the other hand it is also known that the analogous set SP (partrec) (of the shortest programs of all the one-place partial recursive functions) is immune (i.e., infinite, and contains no infinite r.e. subset). Now we formulate the following

Problem 1 Is SP (primrec) not recursive?

Meyer and Ritchie's loop programs compute exactly the primitive recursive functions. It is known (see [1]) that the \complexity problem" of loop programs is undecidable for loop-depth >= 3. (This means that if an arbitrary loop program ß has loop-depth n >= 3 then it is undecidable whether there exists an equivalent loop program ß0 with loop-depth n ? 1.) According to loopdepth we obtain Meyer and Ritchie's well-known hierarchy fLngn>=0 (within the class of primitive recursive functions). A related hierarchy is Axt's hierarchy fKngn>=0, in which the role of loopdepth is played by the depth of primitive recursion. If we allow the more general simultaneous primitive recursion, too, we get a modification fKsim
n gn>=0 of Axt's hierarchy. It is known that
the hierarchies fLngn>=0 and fKsim
n gn>=0 coincide, and Ln = Kn for n >= 4. Clearly we can
construct an effective translation of the loop programs into the representations of the primitive recursive functions in which simultaneous primitive recursion is allowed, too, such that, under this translation, loop-depth n is always mapped into recursion-depth n, for every n >= 0. We can get an analogous effective translation of the loop programs into the \simple" representations of the primitive recursive functions (in which simultaneous primitive recursion is not allowed), for loop-depth n >= 4. So, in view of the above we have:

Proposition 1 The problem of reducibility of recursion-depth n in the hierarchy fKsim n gn>=0 is
undecidable for n >= 3, and the analogous problem in the Axt hierarchy is undecidable for n >= 5.

Problem 2 Is the reducibility of recursion-depth n in the Axt hierarchy undecidable for n = 3; 4, too?

References

[1] Giorgio Ausiello. Complessit?a di calcolo delle funzioni. Editore Boringhieri, Torino, 1975.

Workshop 10 Stuttgart, January 1998

Seite 10: vorherige Seite | nächste Seite | Übersicht

[2] Christian Calude and Lila S^antean. On a theorem of Günter Asser. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 36:143{147, 1990.

[3] Martin Davis. Computability & Unsolvability. McGraw-Hill Series in Information Processing and Computers. McGraw-Hill Book Company, New York, Toronto, London, 1958.

[4] M. D. Gladstone. A reduction of the recursion scheme. Journal of Symbolic Logic, 32:505{ 508, 1967.

[5] M. D. Gladstone. Simplifications of the recursion scheme. Journal of Symbolic Logic, 36:653{665, 1971.

[6] S?andor Horv?ath. Finite, simple generating systems for partial recursive functions|a short note. Bulletin of the European Association for Theoretical Computer Science (EATCS), 28:30{32, 1986.

[7] Michael Machtey and Paul Young. An Introduction to the General Theory of Algorithms. Theory of Computation Series. North Holland, New York, 1978.

[8] Claus-Peter Schnorr. Rekursive Funktionen und ihre Komplexität. B. G. Teubner, Stuttgart, 1974.

[9] George J. Tourlakis. Computability. Reston Publ. Co., Inc., A Prentice-Hall Company, Reston, Virginia, 1984.

Workshop 11 Stuttgart, January 1998

Seite 11: vorherige Seite | nächste Seite | Übersicht

Once More on the Context-Freeness of Q \ (ab?)n

L?aszl?o K?aszonyi

Department of Mathematics

Berzsenyi College

H-9700 Szombathely

Let Q be the language consisting of primitive words over the alphabet fa; bg and consider the language Ln = Q \ (ab?)n. It is conjectured that Ln is context-free for all n 2 N . The validity of the conjecture is proved for n-s having special number-theoretic character. The proofs of these results are based on the well-known theorem of Ginsburg, which asserts | applied to our case | that Ln is context-free iff the set

E(Ln) = f(e0; : : : ; en?1) 2 Nn j abe0 ? ? ? aben?1 2 Lng

is a stratified semilinear set. Here we give a decomposition of E(Ln) in special components and conjecture that each of these components is a stratified semilinear set. We prove the validity of the conjecture in a special case.
(Joint work with M. Katsura)

Workshop 12 Stuttgart, January 1998

Seite 12: vorherige Seite | nächste Seite | Übersicht

On General Iteration Lemmata

Manfred Kudlek

Fachbereich Informatik, Universität Hamburg

Vogt-Kölln-Straße 30, 22527 Hamburg

email: kudlek@informatik.uni-hamburg.de

1 Introduction

The iteration lemmata for regular, linear and context-free languages are well known. They are based on the catenation operation ( with unit element >= ) on the free monoid V ? over some alphabet V , and the norm jwj ( length of words ).

In this paper other binary operations ffi on the power set on underlying monoids M are introduced, as well as other general norms ?. The operations have to be associative with zero element ; and unit element f>=g, and distributive with [ such that the resulting structure is an !-complete semiring. The norm ? has to be monotone with respect to ffi and [, with some minimal norms for ; and f>=g, and be defined for all finite sets.

If rational, linear and algebraic languages are defined as fixed points of corresponding systems of equations on !-complete semirings, it can be shown that iteration lemmata similar to the classical ones hold for such languages.

2 Definitions

Let M be a monoid with binary operation ffi and unit element >=. Extend ffi to an associative binary operation ffi : P(M) ? P(M)!P(M ), distributive with [ ( A ffi (B [ C) = (A ffi B) [ (A ffi C) and (A [ B) ffi C = (A ffi B) [ (B ffi C) ), with unit element f>=g ( f>=g ffi A = A ffi f>=g = A ), and zero element ; ( ; ffi A = A ffi ; = ; ).
Then S = (P(M); [; ffi; ;; f>=g) is an !-complete semiring, i.e. if Ai ? Ai+1 for 0 <= i then B ffi S
i>=0 Ai = S
i>=0(B ffi Ai) and (S
i>=0 Ai) ffi B = S
i>=0(Ai ffi B).

Define also Affi(0) = f>=g; Affi(1) = A; Affi(k+1) = A ffi Affi(k); Affi = S
k>=0 Affi(k):
Let ? : P(M)!IN be a ( partial ) function ( norm ) defined for all finite sets, with the following properties :
?(;) <= 1 ; ?(f>=g) <= 1 ; A ? B)?(A) <= ?(B) ; ?(A); ?(B) <= ?(A [ B) <= maxf?(A); ?(B)g; ?(A); ?(B) <= ?(A ffi B) <= ?(A) + ?(B) ; (A 6= ; ^ A 6= f>=g))?(Affi) = 1 :

Example 1 : Let ffi = ?, the usual catenation ( being associative with unit element >= on M = V ? ), and ? be defined by
?(;) = ?(f>=g) = 0 ; w 2 V ?)?(fwg) = jwj ; ?(A ffi B) = ?(A) + ?(B) ;
?(A [ B) = maxf?(A); ?(B)g ; ?(Affi) = 1 :

Example 2 : Let ffi = , the shuffle operation ( being associative and commutative on M = V ? with unit element >= ), and ? be defined as in Example 1.

Example 3 : Let V be an alphabet and I ? V ? V a symmetric, not necessarily reflexive, relation, called an independence relation. Define uabv ? ubav if (a; b) 2 I and consider its reflexive and transitive closure ??. Then ?? is an equivalence relation, and the set M = V ?= ??, also written V ?=I , being a monoid, is called the trace monoid of V with respect to I . For t1 = [u]; t2 = [v] 2 M the binary operation on traces is defined by t1 ffi t2 = [uv], and the neutral element is [>=]. For t = [w] 2 M a norm can be defined by ?(t) = jwj.

Workshop 13 Stuttgart, January 1998

Seite 13: vorherige Seite | nächste Seite | Übersicht

Let X = fX1; : : : ; Xng be a set of variables such that X \ M = ;.
A monomial over S with variables in X is a finite string of the form : A1 ffiA2 ffi : : : ffiAk ; where Ai 2 X or Ai ? M; jAij < 1; i = 1; : : : ; k: ( without loss of generality, Ai = fffig with ffi 2 M suffices ). A polynomial p(X) over S is a finite union of monomials where X = (X1; ? ? ? ; Xn). A system of equations over S is a finite set of equations : E = fXi = pi(X) j i = 1; : : : ; ng; where pi(X) are polynomials.

The solution of E is a n-tuple (L1; : : : ; Ln) of languages over M , with Li = pi(L1; : : : ; Ln) and the n-tuple is minimal with this property, i.e. if (L01; : : : ; L0n) is another n-tuple that satisfies E, then (L1; : : : ; Ln) <= (L01; : : : ; L0n) ( where the order is defined componentwise with respect to inclusion ).
From the theory of semirings follows that any system of equations over S has a unique solution, and this is the least fixed point starting with (X1; ? ? ? ; Xn) = (;; ? ? ? ; ;).

A system of equations is called linear if all monomials are of the form A ffi X ffi B or A, and rational if they are of the form X ffi A or A, with A ? M and B ? M . Corresponding families of languages ( solutions of such systems of equations ) are denoted by ALG(ffi), LIN(ffi), and RAT (ffi). If ffi is commutative then ALG(ffi) = LIN(ffi) = RAT (ffi).

3 Results

The following theorems can be proven in a way analogous to the classical iteration lemmata.

Theorem 1 : Let L 2 RAT (ffi) with L ? M . Then there exist n(L) > 0 such that, for any w 2 L with ?(fwg) >= n(L), there exist x1; x2; x3 2 M such that :
(i) w 2 fx1g ffi fx2g ffi fx3g.
(ii) 0 < ?(fx1g ffi fx2g) <= n(L).
(iii) fx1g ffi fx2gffi ffi fx3g ? L.

Theorem 2 : Let L 2 LIN(ffi) with L ? M . Then there exist n(L) > 0 such that, for any w 2 L with ?(fwg) >= n(L), there exist x1; x2; x3; x4; x5 2 M such that :
(i) w 2 fx1g ffi fx2g ffi fx3g ffi fx4g ffi fx5g.
(ii) ?(fx1g ffi fx2g ffi fx4g ffi fx5g) <= n(L).
(iii) 0 < ?(fx2g ffi fx4g)
(iv) 8k >= 0 : fx1g ffi fx2gffi(k) ffi fx3g ffi fx4gffi(k) ffi fx5g ? L.

Theorem 3 : Let L 2 ALG(ffi) with L ? M . Then there exist n(L) > 0 such that, for any w 2 L with ?(fwg) >= n(L), there exist x1; x2; x3; x4; x5 2 M such that :
(i) w 2 fx1g ffi fx2g ffi fx3g ffi fx4g ffi fx5g.
(ii) ?(fx2g ffi fx3g ffi fx4g) <= n(L).
(iii) 0 < ?(fx2g ffi fx4g)
(iv) 8k >= 0 : fx1g ffi fx2gffi(k) ffi fx3g ffi fx4gffi(k) ffi fx5g ? L.

To prove these theorems the systems of equations are first converted into equivalent systems of equations ( with additional variables ) where all monomials are in normal form ( X ffi Y or ff for algebraic, ff ffi X or X ffi ff or ff for linear, and X ffi ff or ff for rational systems ).

Any w 2 L can be generated as w 2 ffi1g ffi ? ? ? ffi ffikg where the fij 2 M are the leaves of a binary derivation tree with respect to ffi, and the children of each node correspond to monomials. Note that ? is monotone with respect to [ and ffi, but bounded by the sum.

References

1 J. S. Golan : The Theory of Semirings with Applications in Mathematics and Theoretical Computer Science. Longman Scientific and Technical, 1992.

2 W. Kuich, A. Salomaa : Semirings, Automata, Languages. EATCS Monographs on Theoretical Computer Science, Springer, Berlin, 1986.

Workshop 14 Stuttgart, January 1998

Seite 14: vorherige Seite | nächste Seite | Übersicht

Dense Completeness

Klaus-Jörn Lange

Theoretische Informatik / Formale Sprachen

Wilhelm-Schickard-Institut für Informatik

Sand 13, D-72076 Tübingen

Formal Language Theory and Structural Complexity Theory exhibit close relationships. In spite of the fact that both theories pursue comparable questions like, e.g., the comparison of determinism and nondeterminism, they both succeed quite differently in answering these questions. While Complexity Theory is to a large extent a collection of open problems and most of its results relate open problems, the phenomenon of open problems is almost unknown in Formal Language Theory. This raises the question, how close their mutual relationship is.

Almost all formal languages that are in some way context-free, are related to the classes NP, NAuxPDApt, NSPACE(log n), or NC1. Analogous relations hold between deterministic versions of these families and the classes P, DAuxPDApt, DSPACE(logn), and NC1. The type of these relations is that a family of formal languages A is contained in a complexity class B and that A contains a B-complete language.

Based on an observation by Richard Beigel it is now possible to construct in a systematic way for a class of formal languages A, defined by sequential one-way automata and for which the class B is closed under logspace reductions, a type of nondeterministic one-way automata, such that for a corresponding class of languages A0 it holds that A ? A0 ? B and

8B2B9A2A0 : LOG(A) = LOG(B):

The family A0 thus lies dense in the class B. The construction and some of its properties will be presented in the lecture. It is open whether a comparable construction can be found for deterministic families or classes below DSPACE(logn).

Workshop 15 Stuttgart, January 1998

Seite 15: vorherige Seite | nächste Seite | Übersicht

Confluence of Terminating 2{Dimensional String

Rewriting Systems is Undecidable

Markus Lohrey

Institut für Informatik

Universität Stuttgart

Breitwiesenstr. 20{22, D-70565 Stuttgart

2{dimensional string rewriting systems are a straight forward generalization of ordinary string rewriting systems. Given two finite alphabets ?1 and ?2, a 2{dimensional string rewriting system over (?1; ?2) is a finite set R of rules of the form (l1; l2) ! (r1; r2), where l1; r1 2 ?1 and l2; r2 2 ?2. As expected, R defines a 1{step rewrite relation !R by (u1; u2) !R (v1; v2) iff there exist a rule (l1; l2) ! (r1; r2) in R and strings u01; u002 2 ?1, u02; u002 2 ?2 such that u1 = u01l1u001, u2 = u02l2u002 and v1 = u01r1u001, v2 = u02r2u002. Thus, 2{dimensional string rewriting is a special case of trace rewriting.

For ordinary string rewriting systems it is known to be decidable whether a given terminating string rewriting system is confluent. In contrast to this result, I will prove that the question whether a terminating 2{dimensional string rewriting system over (f1g; ?) is confluent is undecidable. The proof is based on a technique developed by Narendran and Otto.

Workshop 16 Stuttgart, January 1998

Seite 16: vorherige Seite | nächste Seite | Übersicht

The Code Problem for Trace Monoids

Anca Muscholl

Institut für Informatik

Universität Stuttgart

Breitwiesenstr. 20{22, D-70565 Stuttgart

The topic of codes in the framework of trace monoids leads to interesting and challenging decision problems of combinatorial flavour. We consider in this talk the unique decipherability problem (code problem), i.e. the question whether a (finite) subset X of a trace monoid generates a free monoid.

The code problem is in general undecidable, yet there is no exact characterization of the trace monoids where this problem is decidable. We establish in this talk the decidability resp. undecidability of the code problem for some particular families of graphs (i.e., commutation relations I). These results are tightly connected to the emptiness problem for certain types of multicounter automata.

Workshop 17 Stuttgart, January 1998

Seite 17: vorherige Seite | nächste Seite | Übersicht

On Some Recognizable Picture-Languages ?

Klaus Reinhardt

Wilhelm-Schickard-Institut für Informatik

Universität Tübingen

Sand 13, D-72076 Tübingen, Germany

email: reinhard@informatik.uni-tuebingen.de

In [GRST94] pictures are defined as two-dimensional rectangular arrays of symbols of a given alphabet. A set (language) of pictures is called recognizable if it is recognized by a finite tiling system. It was shown in [GRST94] that a picture language is recognizable iff it is definable in existential monadic second-order logic. In [Wil97] it was shown that star-free picture expressions are strictly weaker than first-order logic. A comparison to other regular and contextfree formalisms to describe picture languages can be found in [Mat97b, Mat97a].

We show that the language of pictures over fa; bg, where all occurring b's are connected is recognizable, which solves an open problem in [Mat97a]. (Connectedness is not recognizable in general [FSV95].)

Furthermore we show that the language of pictures over fa; bg, where the number of a's is equal to the number of b's is nonuniformly recognizable. Hereby we use counters similar to those used in [Für82].

References

FSV95 Ronald Fagin, Larry J. Stockmeyer, and Moshe Y. Vardi. On monadic NP vs. monadic co-NP. Information and Computation, 120(1):78{92, July 1995.

Für82 Martin Fürer. The tight deterministic time hierarchy. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 8{16, San Francisco, California, 5{7 May 1982.

GRST94 Dora Giammarresi, Antonio Restivo, Sebastian Seibert, and Wolfgang Thomas. Monadic second-order logic over pictures and recognizability by tiling systems. Proceedings of the 11th STACS 94, LNCS 775, pages 365{375, 1994.

Mat97a Oliver Matz. On Piecewise Testable, Starfree, amd Recignizable Picture Languages, 1997.

Mat97b Oliver Matz. Regular expressions and context-free grammars for picture languages. In 14th Annual Symposium on Theoretical Aspects of Computer Science, volume 1200 of lncs, pages 283{294, Lübeck, Germany, 27 February{ March 1 1997. Springer.

Wil97 Thomas Wilke. Star-free picture expressions are strictly weaker than first-order logic. In Automata, Languages and Programming, LNCS 1256 , pages 347{357, 1997.

?This research has been supported by the DFG Project La 618/3-1 KOMET.

Workshop 18 Stuttgart, January 1998

Seite 18: vorherige Seite | nächste Seite | Übersicht