Abstract
Several extensions of tree automata have been defined, in order to take in account non-linearity in terms. Roughly, these automata allow equality or disequality constraints between subterms. They have been used to get decision results, e.g. in term rewriting. One natural question arises when we consider a language recognized by such an automaton: is this language recognizable, i.e. are the constraints necessary? Here we study this problem in the class REC≠ corresponding to comparisons between brothers and we prove its decidability. It gives e.g. a decision procedure for testing whether the image by a quasi-alphabetic homomorphism of a recognizable tree language is recognizable.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
A. Arnold. Le théorème de transversale rationnelle dans les arbres. Mathematical System Theory, 13:275–282, 1980.
B. Bogaert, F. Seynhaeve, and S. Tison. The recognizability problem for tree automata with comparisons between brothers. Technical Report IT. 317, Laboratoire d’Informatique Fondamentale de Lille, Nov. 1998.
B. Bogaert and S. Tison. Equality and disequality constraints on direct subterms in tree automata. In P. Enjalbert, A. Finkel, and K. W. Wagner, editors, 9th Annual Symposium on Theoretical Aspects of Computer Science, volume 577 of Lecture Notes in Computer Science, pages 161–171, 1992.
A. Caron, H. Comon, J. Coquidé, M. Dauchet, and F. Jacquemard. Pumping, cleaning and symbolic constraints solving. In Proceedings, International Colloquium Automata Languages and Programming, volume 820 of Lecture Notes in Computer Science, pages 436–449, 1994.
A. Caron, J. Coquidé, and M. Dauchet. Encompassment properties and automata with constraints. In C. Kirchner, editor, Proceedings. Fifth International Conference on Rewriting Techniques and Applications, volume 690 of Lecture Notes in Computer Science, pages 328–342, 1993.
H. Comon, M. Dauchet, R. Gilleron, S. Tison, and M. Tommasi. Tree automata techniques and applications, 1998. available through WWW from http://l3ux02.univ-lille3.fr/tata.
M. Dauchet, A.-C. Caron, and J.-L. Coquidé. Reduction properties and automata with constraints. Journal of Symbolic Computation, 20:215–233, 1995.
M. Dauchet and S. Tison. Réduction de la non-linéarite des morphismes d’arbres. Technical Report IT-196, Laboratoire d’Informatique Fondamentale de Lille, Université des Sciences et Technologies de Lille, Villeneuve d’Ascq, France, 1990.
F. Gécseg and M. Steinby. Tree Automata. Akademiai Kiado, 1984.
T. Genet. Decidable approximations of sets of descendants and sets of normal forms. volume 1379 of Lecture Notes in Computer Science, pages 151–165, Tsukuba, 1998.
J.-P. Jouannaud and E. Kounalis. Automatic proofs by induction in theories without constructors. Information and Computation, 82(1):1–33, July 1989.
G. Kucherov and M. Tajine. Decidability of regularity and related properties of ground normal form languages. In Proceedings of 3rd International Workshop on Conditional Rewriting Systems, pages 150–156, 1992.
J. Mongy. Transformation de noyaux reconnaissables d’arbres. Forêts RATEG. PhD thesis, Laboratoire d’Informatique Fondamentale de Lille, Université des Sciences et Technologies de Lille, Villeneuve d’Ascq, France, 1981.
S. Vágvölgyi and R. Gilleron. For a rewrite system it is decidable whether the set of irreducible ground terms is recognizable. Bulletin of the European Association of Theoretical Computer Science, 48:197–209, Oct. 1992.
J. Waldmann. Normalization of s-terms is decidable. volume 1379 of Lecture Notes in Computer Science, pages 138–150, Tsukuba, 1998.
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
Bogaert, B., Seynhaeve, F., Tison, S. (1999). The Recognizability Problem for Tree Automata with Comparisons between Brothers. In: Thomas, W. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 1999. Lecture Notes in Computer Science, vol 1578. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49019-1_11
Download citation
DOI: https://doi.org/10.1007/3-540-49019-1_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65719-4
Online ISBN: 978-3-540-49019-7
eBook Packages: Springer Book Archive