A Characterization of ET0L and EDT0L Languages

Peter R.J. Asveld

Research output: Book/ReportReportOther research output

10 Downloads (Pure)

Abstract

There exists a PT0L language $L_0$ such that the following holds. A language $L$ is an ET0L language if and only if there exists a mapping $T$ induced by an a-NGSM (nondeterministic generalized sequential machine with accepting states) such that $L = T(L_0)$. There exists an infinite collection of EPDT0L languages $D_{mn}\subseteq\Sigma_{mn}^\star$ ($n\geq m\geq 1$) such that the family EDT0L is characterized in the following way. A language $L$ is an EDT0L language if and only if there exists $n\geq m\geq 1$, a homomorphism $h$ and a regular language $R \subseteq \Sigma_{mn}^\star$ such that $L = h(D_{mn} \cap R)$.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages13
Publication statusPublished - 1976

Publication series

NameMemorandum / Department of Applied Mathematics
PublisherDepartment of Applied Mathematics, University of Twente
No.129
ISSN (Print)0169-2690

Fingerprint

Star
If and only if
Regular Languages
Homomorphism
Language
Cap
Family

Keywords

  • HMI-SLT: Speech and Language Technology

Cite this

Asveld, P. R. J. (1976). A Characterization of ET0L and EDT0L Languages. (Memorandum / Department of Applied Mathematics; No. 129). Enschede: University of Twente, Department of Applied Mathematics.
Asveld, Peter R.J. / A Characterization of ET0L and EDT0L Languages. Enschede : University of Twente, Department of Applied Mathematics, 1976. 13 p. (Memorandum / Department of Applied Mathematics; 129).
@book{b2d39b82f9324dc8a9206ca7751e9e86,
title = "A Characterization of ET0L and EDT0L Languages",
abstract = "There exists a PT0L language $L_0$ such that the following holds. A language $L$ is an ET0L language if and only if there exists a mapping $T$ induced by an a-NGSM (nondeterministic generalized sequential machine with accepting states) such that $L = T(L_0)$. There exists an infinite collection of EPDT0L languages $D_{mn}\subseteq\Sigma_{mn}^\star$ ($n\geq m\geq 1$) such that the family EDT0L is characterized in the following way. A language $L$ is an EDT0L language if and only if there exists $n\geq m\geq 1$, a homomorphism $h$ and a regular language $R \subseteq \Sigma_{mn}^\star$ such that $L = h(D_{mn} \cap R)$.",
keywords = "HMI-SLT: Speech and Language Technology",
author = "Asveld, {Peter R.J.}",
note = "Research supported by Netherlands Organization for the Advancement of Pure Research (ZWO). [N.B. The original typescript of this report had 13 pages; the more recent LaTeX version reduced this number to 10.]",
year = "1976",
language = "English",
series = "Memorandum / Department of Applied Mathematics",
publisher = "University of Twente, Department of Applied Mathematics",
number = "129",

}

Asveld, PRJ 1976, A Characterization of ET0L and EDT0L Languages. Memorandum / Department of Applied Mathematics, no. 129, University of Twente, Department of Applied Mathematics, Enschede.

A Characterization of ET0L and EDT0L Languages. / Asveld, Peter R.J.

Enschede : University of Twente, Department of Applied Mathematics, 1976. 13 p. (Memorandum / Department of Applied Mathematics; No. 129).

Research output: Book/ReportReportOther research output

TY - BOOK

T1 - A Characterization of ET0L and EDT0L Languages

AU - Asveld, Peter R.J.

N1 - Research supported by Netherlands Organization for the Advancement of Pure Research (ZWO). [N.B. The original typescript of this report had 13 pages; the more recent LaTeX version reduced this number to 10.]

PY - 1976

Y1 - 1976

N2 - There exists a PT0L language $L_0$ such that the following holds. A language $L$ is an ET0L language if and only if there exists a mapping $T$ induced by an a-NGSM (nondeterministic generalized sequential machine with accepting states) such that $L = T(L_0)$. There exists an infinite collection of EPDT0L languages $D_{mn}\subseteq\Sigma_{mn}^\star$ ($n\geq m\geq 1$) such that the family EDT0L is characterized in the following way. A language $L$ is an EDT0L language if and only if there exists $n\geq m\geq 1$, a homomorphism $h$ and a regular language $R \subseteq \Sigma_{mn}^\star$ such that $L = h(D_{mn} \cap R)$.

AB - There exists a PT0L language $L_0$ such that the following holds. A language $L$ is an ET0L language if and only if there exists a mapping $T$ induced by an a-NGSM (nondeterministic generalized sequential machine with accepting states) such that $L = T(L_0)$. There exists an infinite collection of EPDT0L languages $D_{mn}\subseteq\Sigma_{mn}^\star$ ($n\geq m\geq 1$) such that the family EDT0L is characterized in the following way. A language $L$ is an EDT0L language if and only if there exists $n\geq m\geq 1$, a homomorphism $h$ and a regular language $R \subseteq \Sigma_{mn}^\star$ such that $L = h(D_{mn} \cap R)$.

KW - HMI-SLT: Speech and Language Technology

M3 - Report

T3 - Memorandum / Department of Applied Mathematics

BT - A Characterization of ET0L and EDT0L Languages

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Asveld PRJ. A Characterization of ET0L and EDT0L Languages. Enschede: University of Twente, Department of Applied Mathematics, 1976. 13 p. (Memorandum / Department of Applied Mathematics; 129).