Nondeterministic Bimachines and Rational Relations with Finite Codomain

• Autorzy: Santean N. , Yu S
• Języki publikacji: EN

Abstrakty

EN

Bimachines are important conceptual tools used for the characterization of rational word functions (realized by single-valued transducers). Despite the attention received in the past, these sequential machines are far from being exhaustively studied. A natural question which has not been addressed so far is what family of transductions are realized by bimachines that operate nondeterministically. We show that these machines characterize input-unambiguous (IU) rational transductions, i.e., those transductions that can be written as a composition of rational functions and finite substitutions. Two more families of rational transductions are defined and related in a natural way to IU transductions: input-deterministic transductions and rational transductions with finite codomain (FC). We have shown that FC transductions are recognizable and that they can be expressed as finite union of subsequential functions. Moreover, they can be realized by nondeterministic bimachines. Finally, we have defined the so called restricted nondeterministic bimachines and shown that, surprisingly, they are more powerful than nondeterministic bimachines: they characterize exactly the family of finitely ambiguous rational transductions.

Słowa kluczowe

EN

finite transducer; unambiguous automaton; nondetermistic bimachine; rational function; finite substitution

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 237--264
• Opis fizyczny: wykr., bibliogr. 29 poz.

Twórcy

autor

Santean N.

autor

Yu S

• Department of Computer Science, University of Western Ontario, N6A 5B8, London, Ontario, Canada,

Bibliografia

• [1] M.-P. Beal, O. Carton, C. Prieur, J. Sakarovitch: Squaring transducers: an efficient procedure for deciding functionality and sequentiality. LNCS 1776, Springer, Berlin, 2000, 397-406.
• [2] J. Berstel: Transductions and Context-Free Languages. B.G. Teubner, Stuttgart, 1979.
• [3] J. Berstel, C. Reutenauer: Rational Series and their Languages. Springer-Verlag, Berlin, 1988.
• [4] D. Breslauer: The suffix tree of a tree and minimizing sequential transducers. Theoretical Computer Science, 191 (1998), 131-144.
• [5] C. Choffrut: Une characterisation des fonctions sequentielles et des fonctions sous-sequentielles en tant que relations rationelles. Theoretical Computer Science, 5 (1977), 325-337.
• [6] C. Choffrut: Contribution a l'etude de quelques familles remarquables de fonctions rationnelles. These d'Etat, Universite Paris VII, 1978.
• [7] C. Choffrut: A generalization of Ginsburg and Rose's characterization of GSM mappings. LNCS 71, Springer-Verlag, Berlin, 1979, 88-103.
• [8] C. Choffrut: Minimizing subsequential transducers: a survey. Theoretical Computer Science, 292 (2003), 131-143.
• [9] C. Choffrut, K. Culik: Properties of finite and pushdown transducers. SIAM Journal on Computing, 12, 2 (1983).
• [10] S. Eilenberg: Automata, Languages and Machines, vol. A. Academic Press, New York and London, 1974.
• [11] C.C.Elgot, J.E. Mezei: On relations defined by generalized finite automata. IBM Journal of Research and Development, 9 (1965), 47-65.
• [12] J. Hopcroft, J. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Massachusetts and London, 1979.
• [13] S. Konstantinidis: Transducers and the properties of error-detection, error-correction, and finite-delay decodability. Journal of Universal Computer Science, 8 (2002), 278-291.
• [14] A. Mateescu, A. Salomaa: Aspects of classical language theory. In [22], vol. 1, 175-251.
• [15] J. McKnight: Kleene quotient theorems. Pacific Journal of Mathematics, 14 (1964), 1343-1352.
• [16] M. Mohri: Minimization of sequential transducers. LNCS 807, Springer-Verlag, Berlin, 1994, 151-163.
• [17] M.Mohri: Finite-state transducers in language and speech processing. Computational Linguistics, 23 (1997), 269-311.
• [18] M. Mohri: Edit-distance of weighted automata: General definitions and algorithms. International Journal of Foundations of Computer Science, 14, 6 (2003), 957-982.
• [19] M. Nivat: Transductions des langages de Chomsky. Ann. de l'Inst. Fourier, 18 (1968), 339-456.
• [20] C. Reutenauer: Subsequential functions: characterizations, minimization, examples. LNCS 464, Springer-Verlag, Berlin, 1990, 62-79.
• [21] C. Reutenauer,M.-P. Schutzenberger: Minimization of rational word functions. SIAMJournal on Computing, 30, 4 (1991), 669-685.
• [22] G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages. Springer-Verlag, Berlin, 1997.
• [23] J. Sakarovitch: éléments de Théorie des Automates, Vuibert Informatique, Paris, 2003.
• [24] N. Santean: Bimachines and structurally-reversed automata. Journal of Automata, Languages and Combinatorics, 9, 1 (2004), 121-146.
• [25] M.-P. Schutzenberger: On the definition of a family of automata. Information and Control, 4 (1961), 245-270.
• [26] M.-P. Schutzenberger: A remark on finite transducers. Information and Control, 4 (1961), 185-196.
• [27] M.-P. Schutzenberger: Sur les relations rationelles. LNCS 33, Springer-Verlag, Berlin, 1975, 209-213.
• [28] M.-P. Schutzenberger: Sur une variante des fonctions sequentielles. Theoretical Computer Science, 4 (1977), 47-57.
• [29] S. Yu: Regular Languages. In [22], vol. 1, 209-213.