×

On deterministic multi-pass analysis. (English) Zbl 0611.68051

Chains (or cascade composition) of push-down transducers are introduced as a model of multi-pass compilers. We focus on deterministic chains, since nondeterministic transducer chains of length two define the recursively enumerable sets. Deterministic chains recognize in linear time a superset of context-free deterministic languages. This family \({\mathcal C}{\mathcal H}\) is closed under Boolean operations, disjoint shuffle, and reverse deterministic pushdown translation, but not under homomorphism. Equivalent definitions of the family in terms of composition of syntax-directed translation schemes and control languages are considered. The family is a strict hierarchy ordered by the length of the chain. The complexity of \({\mathcal C}{\mathcal H}\) is obviously linear, but not all linear-time parsable languages are in \({\mathcal C}{\mathcal H}\). On the other hand it strictly includes the Boolean closure of deterministic languages. Finally \({\mathcal C}{\mathcal H}\) is not comparable with another classical Boolean algebra of formal languages, namely real-time languages.

MSC:

68Q45 Formal languages and automata
68N20 Theory of compilers and interpreters
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI