Special Issue: Implementation and Application of Automata: Contributed PapersNo Access

PURE AND O-SUBSTITUTION

ANDREAS MALETTI

Department of Computer Science, Technische Universitt Dresden, 01062 Dresden, Germany

https://doi.org/10.1142/S0129054107005005Cited by:2 (Source: Crossref)

Abstract

The basic properties of distributivity and deletion of pure and o-substitution are investigated. The obtained results are applied to show preservation of recognizability in a number of interesting cases. It is proved that linear and recognizable tree series are closed under o-substitution provided that the underlying semiring is commutative, continuous, and additively idempotent. It is known that, in general, pure substitution does not preserve recognizability (not even for linear target tree series), but it is shown that recognizable linear probability distributions (represented as tree series) are closed under pure substitution.

This article is an extended version of: Andreas Maletti: Does O-Substitution Preserve Recognizability? Proc. 11th Int. Conf. Implementation and Application of Automata. LNCS 4094: 150–161. Springer 2006.

Keywords:

References

J. Berstel and C. Reutenauer, Theoret. Comput. Sci. 18, 115 (1982), DOI: 10.1016/0304-3975(82)90019-6. Crossref, Web of Science, Google Scholar
B. Borchardt, "The theory of recognizable tree series," Ph. D. Thesis, Technische Universität Dresden, 2005 . Google Scholar
S. Bozapalidis, Theory Comput. Systems 32, 1 (1999), DOI: 10.1007/s002240000110. Crossref, Web of Science, Google Scholar
S. Bozapalidis and G. Rahonis, J. Autom. Lang. Combin. 10, 185 (2005). Web of Science, Google Scholar
J. Engelfriet, "Tree automata and tree grammars," Tech. Rep. DAIMI FN-10, Aarhus University, 1975 . Google Scholar
J. Engelfriet, Z. Fülöp and H. Vogler, J. Autom. Lang. Combin. 7, 11 (2002). Web of Science, Google Scholar
Z. Ésik and W. Kuich, J. Autom. Lang. Combin. 8, 219 (2003). Google Scholar
Z. Fülöp and H. Vogler, Theory Comput. Systems 36, 247 (2003). Crossref, Web of Science, Google Scholar
Z. Fülöp and H. Vogler, J. Autom. Lang. Combin. 9, 31 (2004). Google Scholar
F. Gécseg and M. Steinby , Tree Automata ( Akadémiai Kiadó , Budapest , 1984 ) . Google Scholar
J. S. Golan , Semirings and their Applications ( Kluwer Academic , Dordrecht , 1999 ) . Crossref, Google Scholar
U. Hebisch and H. J. Weinert , Semirings — Algebraic Theory and Applications in Computer Science ( World Scientific , 1998 ) . Link, Google Scholar
K. Knight and J. Graehl , An overview of probabilistic tree transducers for natural language processing , Proc. 6th Int. Conf. Comput. Ling, and Int. Text Proc. , LNCS 3406 ( Springer , 2005 ) . Google Scholar
K. Knopp, Theorie und Anwendung der unendlichen Reihen, 5th edn., Die Grundlehren der mathematischen Wissenschaften 2 (Springer, 1964). Crossref, Google Scholar
W. Kuich, Formal power series over trees, Proc. 3rd Int. Conf. Develop, in Lang. Theory, ed. S. Bozapalidis (Aristotle University of Thessaloniki, 1998) pp. 61–101. Google Scholar
W. Kuich, Acta Cybernet. 14, 135 (1999). Google Scholar
A. Maletti, Int. J. Found. Comput. Sci. 16, 723 (2005), DOI: 10.1142/S012905410500325X. Link, Web of Science, Google Scholar
A. Maletti, Theoret. Comput. Sci. 366, 248 (2006), DOI: 10.1016/j.tcs.2006.08.026. Crossref, Web of Science, Google Scholar
A. Maletti, Does o-substitution preserve recognizability?, Proc. 11th Int. Conf. Implem. and Appl. of Automata, LNCS 4094, eds. O. H. Ibarra and H.-C. Yen (Springer, 2006) pp. 150–161. Google Scholar
A. Maletti, "Pure and o-substitution," Tech. Rep. TUD-FI06-05, Technische Uni-versität Dresden, 2006 . Google Scholar
C. Pech, "Kleene-type results for weighted tree automata," Ph. D. Thesis, Technische Universität Dresden, 2003 . Google Scholar
W. C. Rounds, Math. Systems Theory 4, 257 (1970), DOI: 10.1007/BF01695769. Crossref, Google Scholar
J. W. Thatcher, J. Comput. System Sci. 4, 339 (1970). Crossref, Web of Science, Google Scholar