Fixed point languages of deterministic generalized sequential machines are context sensitive

Fixed points of operators are widely studied, and they have been used to describe, for example, the semantics of recursive function definitions (Manna & Shamir [1977]), stability in discrete models for biological development (Herman and Walker [1976]), and to obtain results about cellular spaces (Takahashi [1976]). The regular languages have been characterized by Van Leewen [1975] as homomorphic images of the fixed points of monogenic functions. Herman and Walker [1976] have shown that the set of fixed points of an L-scheme, that is the set of all strings over an alphabet such that each string derives only itself under parallel replacement rules, is a regular language. This result was obtained by showing that, in a self-derivation step, a descendant sub string could only be located a bounded distance to the left or right of its parent sub string. Since the parallel replacement rules of an L-scheme can easily be encoded as a deterministic generalized sequential machine (DGSM) transduction, see e.g. Ginsburg [1966] for a description of a DGSM, - the question arises whether the fixed-point language of a DSGM is also a regular language. A related question is whether, during a DGSM transduction of a string into itself, the amount by which the output lags or leads the input is bounded by a constant. In this paper we show that such a constant bound does not exist, and that the device of defining a language as the set of fixed points of a DGSM has surprising power, namely, some of the languages so generated are not context-free. Since we show that the fixed point languages of DGSMs are accepted by deterministic LBAs, and since it has been pointed out by Ginsburg [1966] that the complement of the fixed point language of a DGSM is a context-free language, our results may suggest some new ways of studying the well known LBA problem, - whether or not there exists a language accepted by an LBA but not by any deterministic LBA.Technical report DCS-TR-6