Abstract
A term rewriting system which effectively preserves recognizability (EPR-TRS) has good mathematical properties. In this paper, a new subclass of TRSs, layered transducing TRSs (LT-TRSs) is defined and its recognizability preserving property is discussed. The class of LT-TRSs contains some EPR-TRSs, e.g., f(x) → f(g(x)) which do not belong to any of the known decidable subclasses of EPR-TRSs. Bottom-up linear tree transducer, which is a well-known computation model in the tree language theory, is a special case of LT-TRS. We present a sufficient condition for an LT-TRS to be an EPR-TRS. Also some properties of LT-TRSs including reachability are shown to be decidable.
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
Baader, F. and Nipkow, T.: Term Rewriting and All That, Cambridge University Press, 1998.
Brained, W.S.: “Tree generating regular systems,” Inform. and control, 14, pp. 217–231, 1969.
Coquidé, J.L., Dauchet, M., Gilleron, R. and Vágvölgyi, S.: “Bottom-up tree pushdown automata: classification and connection with rewrite systems,” Theoretical Computer Science, 127, pp. 69–98, 1994.
Durand, I. and Middeldorp, A.: “Decidable call by need computations in term rewriting (extended abstract),” Proc. of CADE-14, North Queensland, Australia, LNAI 1249, pp. 4–18, 1997.
Genet, T.: “Decidable approximations of sets of descendants and sets of normal forms,” Proc. of RTA98, Tsukuba, Japan, LNCS 1379, pp. 151–165, 1998.
Gécseq, F. and Steinby, M.: Tree Automata, Académiai Kiadó, 1984.
Gilleron, R.: “Decision problems for term rewriting systems and recognizable tree languages,” Proc. of STACS’91, Hamburg, Germany, LNCS 480, pp. 148–159, 1991.
Gilleron, R. and Tison, S.: “Regular tree languages and rewrite systems,” Fundamenta Informaticae, 24, pp. 157–175, 1995.
Gyenizse, P. and Vágvölgyi, S.: “Linear generalized semi-monadic rewrite systems effectively preserve recognizability,” Theoretical Computer Science, 194, pp. 87–122, 1998.
Jacquemard, F.:“Decidable approximations of term rewriting systems,” Proc. of RTA96, New Brunswick, NJ, LNCS 1103, pp. 362–376, 1996.
Middeldorp, A.: “Approximating dependency graph using tree automata techniques,” Proc. of Int’l Joint Conf. on Automated Reasoning, LNAI 2083, pp. 593–610, 2001.
Nagaya, T. and Toyama, Y.: “Decidability for left-linear growing term rewriting systems,” Proc. of RTA99, Trento, Italy, LNCS 1631, pp. 256–270, 1999.
Réty, P.: “Regular sets of descendants for constructor-based rewrite systems,” Proc. of LPAR’99, Tbilisi, Georgia, LNCS 1705, pp. 148–160, 1999.
Salomaa, K.: “Deterministic tree pushdown automata and monadic tree rewriting systems,” J. Comput. system Sci., 37, pp. 367–394, 1988.
Takai, T., Kaji, Y. and Seki, H.: “Right-linear finite path overlapping term rewriting systems effectively preserve recognizability,” Proc. of RTA2000, Norwich, U.K., LNCS 1833, pp. 246–260, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Seki, H., Takai, T., Fujinaka, Y., Kaji, Y. (2002). Layered Transducing Term Rewriting System and Its Recognizability Preserving Property. In: Tison, S. (eds) Rewriting Techniques and Applications. RTA 2002. Lecture Notes in Computer Science, vol 2378. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45610-4_8
Download citation
DOI: https://doi.org/10.1007/3-540-45610-4_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43916-5
Online ISBN: 978-3-540-45610-0
eBook Packages: Springer Book Archive