TY - JOUR
TI - Fixed point languages of deterministic generalized sequential machines are context sensitive
DO - https://doi.org/doi:10.7282/t3-fyar-5k31
AU - Van der Mude, A.
AU - Walker, Adrian
PY - 1978-02
AB - 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.
LA - English
ER -