Finitary Compositions of Two-way Finite-State Transductions

• Autorzy: Engelfriet J. , Hoogeboom H.J.
• Języki publikacji: EN

Abstrakty

EN

The hierarchy of arbitrary compositions of two-way nondeterministic finite-state transductions collapses when restricted to finitary transductions, i.e., transductions that produce a finite set of outputs for each input. The hierarchy collapses to the class of nondeterministic mso definable transductions, which is inside the second level of that hierarchy. It is decidable whether a composition of two-way nondeterministic finite-state transducers realizes a finitary transduction (i.e., is mso definable).

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 80, nr 1-3
• Strony: 111--123
• Opis fizyczny: bibliogr. 20 poz., wykr.

Twórcy

autor

Engelfriet J.

autor

Hoogeboom H.J.

• L.I.A.C.S., Leiden University, PO Box 9512 2300 RA Leiden, The Netherlands,

Bibliografia

• [1] Aalbersberg, IJ. J., Engelfriet, J.: The recognition of trace languages, Tech. Report 86-18, Leiden University, 1986.
• [2] Aalbersberg, IJ. J., Hoogeboom, H. J.: Characterizations of the decidability of some problems for regular trace languages, Mathematical Systems Theory, 22, 1989, 1-19.
• [3] Bloem, R., Engelfriet, J.: A comparison of tree transductions defined by monadic second order logic and by attribute grammars, Journal of Computer and System Sciences, 61, 2000, 1-50.
• [4] Courcelle, B.: Monadic second-order definable graph transductions: a survey, Theoretical Computer Science, 126, 1994, 53-75.
• [5] Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic, in: Handbook of Graph Grammars and Computing by Graph Transformation, vol.1: Foundations (G. Rozenberg, Ed.),World Scientific, 1997, 313-400.
• [6] Engelfriet, J.: Proving correctness by head and tail relations, Manuscript, Twente University of Technology, 1972.
• [7] Engelfriet, J.: Three hierarchies of transducers, Mathematical Systems Theory, 15, 1982, 95-125.
• [8] Engelfriet, J.: Iterated stack automata and complexity classes, Information and Computation, 95, 1991, 21-75.
• [9] Engelfriet, J., Hoogeboom, H. J.: MSO definable string transductions and two-way finite-state transducers, ACM Transactions on Computational Logic, 2, 2001, 216-254.
• [10] Engelfriet, J., Maneth, S.: Macro tree transducers, attribute grammars, and MSO definable tree translations, Information and Computation, 154, 1999, 34-91.
• [11] Engelfriet, J., Maneth, S.: Macro tree translations of linear size increase are MSO definable, SIAM Journal on Computing, 32, 2003, 950-1006.
• [12] Greibach, S. A.: Hierarchy theorems for two-way finite state transducers, Acta Informatica, 11, 1978, 89-101.
• [13] Hennie, F. C.: One-tape, off-line Turing machine computations, Information and Control, 8, 1965, 553-578.
• [14] Hoogeboom, H. J., Muscholl, A.: The code problem for traces - improving the boundaries, Theoretical Computer Science, 172, 1997, 309-321.
• [15] Hoogeboom, H. J., Rozenberg, G.: Dependence graphs, in: The Book of Traces (V. Diekert, G. Rozenberg, Eds.), World Scientific, 1995, 43-68.
• [16] Maneth, S.: The macro tree transducer hierarchy collapses for functions of linear size increase, in: Proc. FSTTCS'2003 (P. K. Pandya, J. Radhakrishnan, Eds.), Lecture Notes in Computer Science 2914, Springer-Verlag, 2003, 326-337.
• [17] Mazurkiewicz, A. W.: Proving algorithms by tail functions, Information and Control, 18, 1971, 220-226.
• [18] Mazurkiewicz, A. W.: Concurrent program schemes and their interpretations, DAIMI PB-78, Aarhus University, 1977.
• [19] Mazurkiewicz, A. W.: Trace theory, in: Petri Nets: Central Models and Their Properties (W. Brauer, W. Reisig, G. Rozenberg, Eds.), Lecture Notes in Computer Science 255, Springer-Verlag, 1987, 279-324.
• [20] Shepherdson, J. C.: The reduction of two-way automata to one-way automata, IBM Journal of Research and Development, 3, 1959, 198-200.