Abstract
In this paper we study applications of relations based on rewrite systems to regular tree languages. For instance, we want to deal with decidability problems of the form “R el(L 1) ⊆ L 2” where L 1, L 2 are regular tree languages and R el can be either IO, OI, parallel, or one step rewriting for a given rewrite system. Our method somehow standardizes previous ones because it reveals conditions R el must fulfill to preserve recognizability for the language R el(L 1). Thanks to classes of recognizable languages wider than the regular one, we get some new results. We pursue this method to tackle the problem of computing the set of descendants of a regular tree language by a rewrite system.
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
A. Arnold and M. Dauchet. Morphismes et bimorphismes d’arbres. Theorical Computer Science, 20:33–93, 1982.
B. Bogaert, F. Seynhaeve, and S. Tison. The recognizability problem for tree automata with comparisons between brothers. In W. Thomas, editor, Proceedings, Foundations of Software Science and Computation Structures, number 1578 in Lecture Notes in Computer Science, Amsterdam, 1999. Springer Verlag.
[CDG+97]_H. Comon, M. Dauchet, R. Gilleron,, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata, 1997.
J.L. Coquidè, M. Dauchet, R. Gilleron, and S. Vágvolgyi. Bottom-up tree push-down automata: Classification and connection with rewrite systems. Theorical Computer Science, 127:69–98, 1994.
M. Dauchet, A.-C. Caron, and J.-L. Coquidè. Reduction properties and auto-mata with constraints. Journal of Symbolic Computation, 20:215–233, 1995.
M. Dauchet and S. Tison. The theory of ground rewrite systems is decidable. In Proceedings, Fifth Annual IEEE Symposium on Logic in Computer Science, pages 242–248. IEEE Computer Society Press, 1990.
J. Engelfriet. Bottom-up and top-down tree transformations. a comparision. Mathematical System Theory, 9:198–231, 1975.
J. Engelfriet. A hierarchy of tree transducers. In Proceedings of the third Les Arbres en Algèbre et en Programmation, pages 103–106, Lille, 1978.
J. Engelfriet and E.M. Schmidt. IO and OI I. Journal of Comput. and Syst. Sci., 15:328–353, 1977.
J. Engelfriet and E.M. Schmidt. IO and OI II. Journal of Comput. and Syst. Sci., 16:67–99, 1978.
A. Fülöp, E. Jurvanen, M. Steinby, and S. Vágvölgy. On one-pass term rewriting. In L. Brim, J. Gruska, and J. Zlatusaksv, editors, Proceedings of Mathematical Foundations of Computer Science, volume 1450 of Lecture Notes in Computer Science, pages 248–256. Springer Verlag, 1998.
T. Genet. Decidable approximations of sets of descendants and sets of normal forms. In Nipkow [Nip98], pages 151–165.
F. Gècseg and M. Steinby. Tree Automata. Akademiai Kiado, 1984.
F. Jacquemard. Automates d'arbres et rèècriture de termes. PhD thesis, Universitè de Paris XI, 1996.
F. Jacquemard. Decidable approximations of term rewriting systems. In H. Ganzinger, editor, Proceedings. Seventh International Conference on Rewriting Techniques and Applications, volume 1103 of Lecture Notes in Computer Science, 1996.
T. Nipkow, editor. Proceedings. Ninth International Conference on Rewriting Techniques and Applications, volume 1379 of Lecture Notes in Computer Science, Tsukuba, 1998.
K. Salomaa. Deterministic tree pushdown automata and monadic tree rewrit-ing systems. Journal of Comput. and Syst. Sci., 37:367–394, 1988.
J. Waldmann. Normalization of s-terms is decidable. In Nipkow [Nip98], pages 138–150.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Seynhaeve, F., Tison, S., Tommasi, M. (1999). Homomorphisms and concurrent term rewriting. In: Ciobanu, G., Păun, G. (eds) Fundamentals of Computation Theory. FCT 1999. Lecture Notes in Computer Science, vol 1684. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48321-7_40
Download citation
DOI: https://doi.org/10.1007/3-540-48321-7_40
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66412-3
Online ISBN: 978-3-540-48321-2
eBook Packages: Springer Book Archive