INFDok - Dokumentenvolltextserver des Fachbereichs Informatik

Kurzfassung auf Englisch:

The language theoretic operation twist from \cite{JaPe87} is studied in connection with the semiAFLs of languages accepted by reversal bounded multipushdown and multicounter acceptors. It is proved that the least twist-closed trio generated by $\MIR := \{ ww^{rev} \mid w \in\{a, b\}^* \}$ is equal to the family of languages accepted in quasi-realtime by nondeterministic one-way multipushdown acceptors which operate in such a way that in every computation each pushdown makes at most one reversal. Thus, the intersection-closed trio generated by \MIR equals the twist-closed trio with the same generator. and this family is principal both as a twist-closed and as an intersection-closed semiAFL. This is in contrast to the semiAFL of languages accepted by reversal-bounded multicounter machines in quasi-realtime. This family is a well known semiAFL which is principal as an intersection-closed semiAFL with generator $B_1\ := \{a_1^n\Bar{a}_1^n \mid n\in \N \}$, see \cite{Grei78}, but is not principal as a semiAFL. It is here shown that it forms a hierarchy of twist-closed semiAFLs and therefore cannot be principal as twist-closed semiAFL.