On twist-closed trios

URN urn:nbn:de:gbv:18-228-7-382
URL
Dokumentart: Report (Bericht)
Schriftenreihe: Berichte des Fachbereichs Informatik der Universität Hamburg
Bandnummer: 204
Sprache: Englisch
Erstellungsjahr: 1997
Publikationsdatum:
SWD-Schlagwörter: Sprachtheorie , Theoretische Informatik
Freie Schlagwörter (Englisch): language theory , language theoretic operation twist, , theoretical computer science
DDC-Sachgruppe: Informatik
BK - Klassifikation: 54.10

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.

Hinweis zum Urherberrecht

Für Dokumente, die in elektronischer Form über Datenenetze angeboten werden, gilt uneingeschränkt das Urheberrechtsgesetz (UrhG). Insbesondere gilt:

Einzelne Vervielfältigungen, z.B. Kopien und Ausdrucke, dürfen nur zum privaten und sonstigen eigenen Gebrauch angefertigt werden (Paragraph 53 Urheberrecht). Die Herstellung und Verbreitung von weiteren Reproduktionen ist nur mit ausdrücklicher Genehmigung des Urhebers gestattet.

Der Benutzer ist für die Einhaltung der Rechtsvorschriften selbst verantwortlich und kann bei Mißbrauch haftbar gemacht werden.