Abstract
By weakly ambiguous (finite) transducers we mean those transducers that, although being ambiguous, may be viewed to be at arm’s length from unambiguity. We define input-unambiguous (IU) and input-deterministic (ID) transducers, and transducers with finite codomain (FC). IU transductions are characterized by nondeterministic bimachines and ID transductions can be represented as a composition of sequential functions and finite substitutions. FC transductions are recognizable and can be expressed as finite unions of subsequential functions. We place these families along with uniformly ambiguous (UA) and finitely ambiguous (FA) transductions in a hierarchy of ambiguity. Finally, we show that restricted nondeterministic bimachines characterize FA transductions. Perhaps the most important aspect of this work consists in defining nondeterministic bimachines and describing their power by linking them with weakly ambiguous finite transducers (IU and FA).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berstel, J.: Transductions and Context-Free Languages. B. G. Teubner, Stuttgart (1979)
Blattner, M., Head, T.: Single Valued a-Transducers. Journal of Computer and System Sciences 15(3), 310–327 (1977)
Eilenberg, S.: Automata, Languages and Machines, vol. A. Academic Press, Inc., Orlando, FL (1974)
Gurari, E.M., Ibarra, O.H.: A Note on Finite-Valued and Finitely Ambiguous Transducers. Mathematical Systems Theory 16(1), 61–66 (1983)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 1st edn. Addison-Wesley Longman Publishing Co. Inc., Boston, MA (1979)
Roche, E., Schabes, Y.: Introduction to Finite-State Devices in Natural Language Processing. Technical Report TR-96-13, Mitsubishi Electric Research Laboratories (1996)
Rozenberg, G., Salomaa, A.: Handbook of Formal Languages. Springer, Heidelberg (1997)
Sakarovitch, J.: Éléments de Théorie des Automates. Vuibert Informatique, Paris (2003)
Santean, N.: Bimachines and Structurally-Reversed Automata. Journal of Automata, Languages and Combinatorics 9(1), 121–146 (2004)
Santean, N., Yu, S.: Nondeterministic Bimachines and Rational Relations with Finite Codomain. Technical Report 649, University of Western Ontario (2005), ISBN-10: 0-7714-2552-X, ISBN-13: 978-0-7714-2552-X
Schützenberger, M.-P.: A Remark on Finite Transducers. Information and Control 4(2-3), 185–196 (1961)
Schützenberger, M.-P.: Sur les Relations Rationelles. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol. 33, pp. 209–213. Springer, Heidelberg (1975)
Yu, S.: Regular Languages. In: [7], vol. 1, pp. 41–110 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Santean, N., Yu, S. (2006). On Weakly Ambiguous Finite Transducers. In: Ibarra, O.H., Dang, Z. (eds) Developments in Language Theory. DLT 2006. Lecture Notes in Computer Science, vol 4036. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11779148_15
Download citation
DOI: https://doi.org/10.1007/11779148_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35428-4
Online ISBN: 978-3-540-35430-7
eBook Packages: Computer ScienceComputer Science (R0)