×

The equivalence problem for languages defined by transductions on D0L languages. (English) Zbl 1101.68051

Summary: We study the equivalence problem for languages defined by various types of transducers acting on D0L languages.
We show that, given \(e\)-free sequential transducers \(S_1,\dots, S_k, T_1,\dots, T_k\) and D0L languages \(L_1, L_2\), whether or not \(|S_1|(L_1) \cup \cdots \cup |S_k|(L_1) = |T_1|(L_2)\cup \cdots \cup |T_k|(L_2)\) is decidable.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1016/0304-3975(86)90134-9 · Zbl 0621.68049 · doi:10.1016/0304-3975(86)90134-9
[2] DOI: 10.1016/0020-0190(72)90039-7 · Zbl 0267.68033 · doi:10.1016/0020-0190(72)90039-7
[3] DOI: 10.1007/BF00571462 · Zbl 0264.68029 · doi:10.1007/BF00571462
[4] DOI: 10.1016/0012-365X(94)90254-2 · Zbl 0795.68158 · doi:10.1016/0012-365X(94)90254-2
[5] DOI: 10.1016/j.tcs.2004.09.014 · Zbl 1078.68086 · doi:10.1016/j.tcs.2004.09.014
[6] DOI: 10.1142/S0129054103001960 · Zbl 1101.68660 · doi:10.1142/S0129054103001960
[7] Berstel J., Transductions and Context-Free Languages (1979) · Zbl 0424.68040 · doi:10.1007/978-3-663-09367-1
[8] Rozenberg G., The Mathematical Theory of L Systems (1980) · Zbl 0508.68031
[9] DOI: 10.1007/978-3-642-59126-6 · doi:10.1007/978-3-642-59126-6
[10] Salomaa A., Automata-Theoretic Aspects of Formal Power Series (1978) · Zbl 0377.68039 · doi:10.1007/978-1-4612-6264-0
[11] DOI: 10.1017/CBO9780511546563 · Zbl 1086.11015 · doi:10.1017/CBO9780511546563
[12] DOI: 10.1016/S0019-9958(77)90512-5 · Zbl 0365.68074 · doi:10.1016/S0019-9958(77)90512-5
[13] DOI: 10.1016/S0019-9958(74)90857-2 · Zbl 0284.68065 · doi:10.1016/S0019-9958(74)90857-2
[14] Berstel J., Automata, Languages, Development pp 161– (1976)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.