Summary
In this paper we present algorithms to decide: 1) single-valuedness of nondeterministic finite transducers, 2) equivalence of single-valued transducers, and 3) whether a given nondeterministic finite transduction can be realized by a deterministic transducer. When such a deterministic realization is possible our proof gives an effective construction of the deterministic transducer.
The decidability of single-valuedness and equivalence for a-transducers has been obtained independently by Blattner and Head [3]. Our results introduce different characterizations for decidability and use a different proof that is interesting on its own.
We began this research by generalizing the results about decoding automata presented in [5]. A report of these results with a heavy emphasis placed on applications to crytography appears in [6]. This paper presents results applicable in the more general area of finite state translations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho, A.V., Ullman, J.D.: The theory of parsing, translation and compiling. Vols. 1 and 2. New York: Prentice-Hall, 1973
Bird, M.: The equivalence problem for deterministic two-tape automata. JCSS 7, (1973)
Blattner, M., Head, T.: Single-valued a-transducers. JCSS 15, 310–327 (1977)
Brosgol, B.: Deterministic translation grammars, Ph.D. Thesis, Harvard University, Cambridge, Massachusetts, 1974
Bruckner, I.: Zur Konstruktion von Decodierautomaten GI-5 Jahrestagung. Lecture Notes in Computer Science, Vol. 34, pp. 269–279. Berlin-Heidelberg-New York: Springer 1975
Demers, A., Keleman, C.F., Reusch, B.: On encryption systems realized by finite transducers. Cornell University Technical Report TR 76–291
Griffiths, T.V.: The unsolvability of the equivalence problem for ^-free nondeterministic generalized machines. JACM 15, 409–413 (1968)
Gurari, E.M.: The decidability of the equivalence problem for deterministic two-way sequential transducers. Proc. 21st FOCS Conference (1980)
Gurari, E.M., Ibarra, O.H.: Some decision problems concerning sequential transducers and checking automata. JCSS 18, 18–34 (1979)
Hopcroft, J.E.: On the equivalence and containment problems for context-free languages. Math. Systems Theory 3
Hopcroft, J.E., Ullman, J.D.: Formal languages and their relation to automata. New York: Addison-Wesley, 1969
Maurer, H.A., Nivat, M.: Bijective a-transducers. Proc. 20th FOCS, pp. 97–100 (1979)
Sardinas, A.A., Patterson, G.W.: A necessary and sufficient condition for unique decomposition of encoded messages. IRE Convention Record, pt. 8, pp. 104–108 (1953)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Demers, A., Keleman, C. & Reusch, B. On some decidable properties of finite state translations. Acta Informatica 17, 349–364 (1982). https://doi.org/10.1007/BF00264358
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00264358