Information Technology Reference
In-Depth Information
12. Church, A.: An unsolvable problem of elementary number theory. Amer. J.
Math. 58, 345-363 (1936)
13. Comon-Lundh, H., Dauchet, M., Gilleron, R., Loding, C., Jacquemard, F., Lugiez,
D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications (Novem-
ber 2007)
14. Courcelle, B.: Monadic second-order definable graph transductions: A survey. The-
oretical Computer Science 126(1), 53-75 (1994)
15. Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic -
A Language-Theoretic Approach. Encyclopedia of mathematics and its applica-
tions, vol. 138. Cambridge University Press (2012)
16. Culik II, K., Karhumaki, J.: The equivalence problem for single-valued two-way
transducers (on NPDTOL languages) is decidable. SIAM J. Comput. 16(2), 221-
230 (1987)
17. Curry, H.B.: Functionality in Combinatory Logic. Proceedings of the National
Academy of Sciences of the United States of America 20, 584-590 (1934)
18. Diekert, V., Gastin, P.: First-order definable languages. In: Logic and Automata:
History and Perspectives, Texts in Logic and Games, pp. 261-306. Amsterdam
University Press (2008)
19. Ebbinghaus, H.D., Flum, J.: Finite Model Theory. Springer, Berlin (1995)
20. Elgot, C.C.: Decision problems of finite automata design and related arithmetics.
Transactions of the American Mathematical Society 98(1), 21-51 (1961)
21. Engelfriet, J., Hoogeboom, H.J.: MSO definable string transductions and two-way
finite-state transducers. ACM Trans. Comput. Logic 2, 216-254 (2001)
22. Engelfriet, J., Maneth, S.: Macro tree transducers, attribute grammars, and MSO
definable tree translations. Inf. Comput. 154(1), 34-91 (1999)
23. Engelfriet, J., Maneth, S.: Macro tree translations of linear size increase are MSO
definable. SIAM J. Comput. 32(4), 950-1006 (2003)
24. Engelfriet, J., Maneth, S.: The equivalence problem for deterministic MSO tree
transducers is decidable. Inf. Process. Lett. 100(5), 206-212 (2006)
25. Filiot, E., Gauwin, O., Reynier, P.A., Servais, F.: From two-way to one-way finite
state transducers. In: LICS, pp. 468-477 (2013)
26. Filiot, E., Krishna, S.N., Trivedi, A.: First-order definable string transformations.
To appear in FSTTCS (2014)
27. Fulop, Z., Vogler, H.: Syntax-Directed Semantics - Formal Models Based on Tree
Transducers. Monographs in Theoretical Computer Science. An EATCS Series.
Springer (1998)
28. Griths, T.V.: The unsolvability of the equivalence problem for -free nondeter-
ministic generalized machines. Journal of the ACM (1968)
29. Howard, W.: The formulae-as-types notion of construction. In: To H.B.Curry:
Essays on Combinatory Logic, Lambda-Calculus and Formalism. Academic Press
(1980)
30. Immerman, N.: Languages that capture complexity classes. SIAM Journal on
Computing 16(4), 760-778 (1987)
31. Berstel, J.: Transductions and Context-Free Languages. Teubner, Stuttgart (1979)
32. Lautemann, C., McKenzie, P., Schwentick, T., Vollmer, H.: The descriptive com-
plexity approach to LOGCFL. Journal of Computer and System Sciences 62
(2001)
33. Maneth, S.: Equivalence problems for tree transducers: A brief survey. In: AFL,
pp. 74-93 (2014)
34. McKenzie, P., Schwentick, T., Therienand, D., Vollmer, H.: The many faces of a
translation. Journal of Computer and System Sciences 72 (2006)
Search WWH ::




Custom Search