zbMATH — the first resource for mathematics

On the lengths of values in a finite transducer. (English) Zbl 0790.68038
We investigate finite transducers and their inner structure with regard to the lengths of values. Our transducer models are the normalized finite transducer (NET) and the nondeterministic generalized sequential machine (NGSM), which is a real-time NFT. The length-degree of an NFT is defined to be the maximal number of different lengths of values for an input word or is infinite, depending on whether or not a maximum exists. We show: An NGSM \(M\) with finite length-degree can be effectively decomposed into finitely many NGSMs \(M_ 1,\dots,M_ N\) having length-degree at most 1 such that the transduction realized by \(M\) is the union of the transductions realized by \(M_ 1,\dots,M_ N\). Using this decomposition, the equivalence of NGSMs with finite length-degree is recursively decidable. Whether or not an NGSM has finite length-degree can be decided in deterministic polynomial time. By reduction, all these results can be generalized to NFTs.

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q45 Formal languages and automata
Full Text: DOI
[1] [AHU74] Aho, A., Hopcroft, J., Ullman, J.: The design and analysis of computer algorithms. Reading, MA: Addison-Wesley 1974 · Zbl 0326.68005
[2] [AL78] Anisimov, A.V., Lisovik, L.P.: Equivalence problems for finite-automaton mappings into free and commutative semigroups. Cybernetics14, 321-327 (1978)
[3] [B79] Berstel, J.: Transductions and context-free languages. Stuttgart: Teubner 1979 · Zbl 0424.68040
[4] [BH77] Blattner, M., Head, T.: Single-valued a-transducers. J. Comput. Syst. Sci.15, 310-327 (1977) · Zbl 0367.94071
[5] [C90] Culik II, K.: New techniques for proving the decidability of equivalence problems. Theor. Comput. Sci.71, 29-45 (1990) · Zbl 0699.68092
[6] [CK86] Culik II, K., Karhumäki, J.: The equivalence of finite valued transducers (on HDTOL languages) is decidable. Theor. Comput. Sci.47, 71-84 (1986) · Zbl 0621.68049
[7] [FS91] Frougny, C., Sakarovitch, J.: Rational relations with bounded delay. Proc. 8th STACS 1991. (Lect. Notes Comput. Sci., vol. 480, pp 50-63) Berlin Heidelberg New York: Springer 1991 · Zbl 0773.68045
[8] [GJ79] Garey, M., Johnson, D.: Computers and intractability. San Francisco, CA: Freeman 1979
[9] [G68] Griffiths, T.: The unsolvability of the equivalence problem forA-free nondeterministic generalized machines. J. ACM15, 409-413 (1968) · Zbl 0162.02302
[10] [GI83] Gurari, E., Ibarra, O.: A note on finite-valued and finitely ambiguous transducers. Math. Syst. Theory16, 61-66 (1983) · Zbl 0502.68022
[11] [HW91] Head, T., Weber, A.: Deciding code related properties by means of finite transducers. Proc. SEQUENCES 1991 (to appear)
[12] [HU79] Hopcroft, J., Ullman, J.: Introduction to automata theory, languages, and computation. Reading, MA: Addison-Wesley 1979 · Zbl 0426.68001
[13] [I78] Ibarra, O.: The unsolvability of the equivalence problem for ?-free NGSM’s with unary input (output) alphabet and applications. SIAM J. Comput.7, 524-532 (1978) · Zbl 0386.68054
[14] [K86] Karhumäki, J.: The equivalence of mapping on languages. Proc. 4th IMYCS 1986. (Lect. Notes Comput. Sci., vol. 281, pp. 26-38) Berlin Heidelberg New York: Springer 1987
[15] [K87] Karkumäki, J.: On recent trends in formal language theory. Proc. 14th ICALP 1987. (Lect. Notes Comput. Sci., vol. 267, pp. 136-162) Berlin Heidelberg New York: Springer 1987
[16] [L79] Lisovik, L.P.: The identity problem for regular events over the direct product of free and cyclic semigroups (in Ukrainian and Russian). Dopov. Akad. Nauk Ukr. RSR Ser. A6, 410-413 (1979)
[17] [L83] Lisovik, L.P.: Minimal undecidable identity problem for finite-automaton mappings. Cybernetics19, 160-165 (1983) · Zbl 0532.68058
[18] [N79] Nozaki, A.: Equivalence problem of non-deterministic finite automata. J. Comput. Syst. Sci.18, 8-17 (1979) · Zbl 0401.68028
[19] [Sch76] Schützenberger, M.P.: Sur les relations rationnelles entre monoïdes libres. Theor. Comput. Sci.3, 243-259 (1976) · Zbl 0358.68129
[20] [S90] Seidl, H.: Equivalence of finite-valued bottom-up finite state tree transducers is decidable. Proc. CAAP 1990. (Lect. Notes Comput. Sci., vol. 431, pp. 269-284) Berlin Heidelberg New York: Springer 1990 · Zbl 0758.68049
[21] [W87] Weber, A.: Über die Mehrdeutigkeit und Wertigkeit von endlichen Automaten und Transducern, Dissertation, Goethe-Universität, Frankfurt am Main, 1987
[22] [W89] Weber, A.: On the lengths of values in a finite transducer. Proc. MFCS 1989. (Lect. Notes Comput. Sci., vol. 379, pp 523-533) Berlin Heidelberg New York: Springer 1989 · Zbl 0755.68109
[23] [W90] Weber, A.: On the valuedness of finite transducers. Acta Inf.27, 749-780 (1990) · Zbl 0672.68027
[24] [W92a] Weber, A.: Decomposing finite-valued transducers and deciding their equivalence. SIAM J. Comput. (to appear) (see also Proc. MFCS 1988). (Lect. Notes Comput. Sci., vol. 324, pp 552-562) Berlin Heidelberg New York: Springer 1988
[25] [W92b] Weber, A.: Decomposing ak-valued transducer intok unambiguous ones. Proc. LATIN 1992. (Lect. Notes Comput. Sci., vol. 583, pp. 503-515) Berlin Heidelberg New York: Springer 1992
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.