Mauricio Aguirre1 Eric Jeltsch1 Gerardo Rosales1
1 Universidad de La Serena, Av. Cisternas 1200, La Serena, Chile. ejeltsch@userena.cl
RESUMEN
En este trabajo se desarrolla un algoritmo de inferencia gramatical, el cual posee como entrada un conjunto finito de árboles y como salida top-down tree generator (td generador), que consiste de una gramática de árbol regular y un conjunto finito de transductores. Se presenta también el sistema de software TreeBag (Tree Based Generador), herramienta útil para la generación y visualización de objetos de todo tipo: grafos, árboles, string, etc.
Palabras clave: Gramática de árboles, transductores, inferencia gramatical, sistema TreeBag.
ABSTRACT
In this paper, a grammatical inference algorithm is developed with finite sets of sample trees as inputs and top-down tree generator (td generator) consisting of regular tree grammars and a finite sequence of transducers as outputs. A software system called TreeBag (Tree Based Generator) is presented, its aim being allowing the generation and visualization of objects of all kinds such as: graphs, trees, strings, etc.
Keywords: Tree grammars, transducers, grammatical inference, TreeBag system.
AGRADECIMIENTOS
Este trabajo ha sido íntegramente financiado por Proyecto No 0220-2-20, DIULS (Dirección de Investigación de la Universidad de La Serena).
REFERENCIAS
[1] Michael Barnsley. Fractals Everywhere, Academic Press, Boston, 1988.
[2] C. Cook, A. Rosenfeld, A. Aronson. Grammatical Inference by Hill Climbing, Informational Sciences 10, 59-80. 1976.
[3] Frank Drewes. Tree-Based Picture Generation. Theo.Comp. Sc. No 246, pp. 1-51. 2000.
[4] Frank Drewes, A. Habel, H-J. Kreowski y S. Taubenberger. Generating self affine fractals by Collage Grammars. Theoretical Computer Science. No 187, pp. 145-159. 1995.
[5] Frank Drewes. Computation by tree transductions. Doctoral dissertation, University of Bremen, Germany. 1996.
[6] K.S. Fu, T. K. Booth. Grammatical Inference Introduction an Survey Part I y II. IEEE-Trans. Syst. Man and Cyber. No 5, pp. 95-111 y 409-423. 1975.
[7] Zoltán Fülöp, Heiko Vogler. Syntax-Directed Semantics:Formal Models Based on Tree Transducers. Springer. 1998.
[8] F. Gécseg, M. Steinby. Tree Automata. Akadémiai Kiadó, Budapest. 1984.
[9] F. Gécseg, M. Steinby. Tree Languages. G. Rozenberg and A. Salomaa, editors. Handbook of Formal Languages. Vol. III: Beyond Words, Cap. I, pp. 1-68. Springer. 1997.
[10] A. Habel, H.J. Kreowski. Collage Grammars, Lect. Not. Comp. Sci. No 532, pp. 411-429. 1991.
[11] H.J. Kreowski, Eric Jeltsch. Grammatical Inference based on hyperedge replacement. Lect. Not. Comp. Sci. No 532, pp. 461-474. 1991.
[12] H. Jürgensen, A. Lindenmayer. Inference Algorithms for Developmental Systems with Cell Lineages. Bulletin of Mathematical Biology. Vol. 49 No1, pp. 93-123. 1987.
[13] Heinz-Otto Peitgen, Hartmut Jürgens y Dietmar Saupe. Chaos and Fractals. New Frontiers of Science. Springer-Verlag. New York, EEUU. 1992.
[14] P. Prusinkiewicz, A. Lindenmayer. The Algorithmic Beauty of Plants. Springer-Verlag, New York, EEUU. 1990. [ Links ]
[15] V. Radhakrishnan, G. Nagaraja. Inference of Even Linear Grammar and Its Application to Picture Description Languages, Pattern Recognition, Vol 2 No 1, pp. 55-62. 1988.
[16] W. C. Rounds. Mapping and Grammars on Trees. Mathematical Systems Theory. No 4, pp. 257-287. 1970.
[17] James W. Thatcher. Generalized sequential machine maps. Journal of Computer and System Sciences. No 4, pp. 339-367. 1970.
[18] Homepage of the Grammatical Induction Community. http://eurise.univ-st-etienne.fr/gi/
[19] The TreeBag Homepage. http://www.informatik.uni-bremen.de/theorie/ treebag/
[20] Theodore W. Hong and Keith L. Clark Using Grammatical Inference to Automate Information Extraction from the {Web}. Lecture Notes in Computer Science. Vol. 2168, pp. 216-220. 2001.
[21] D. López, A. Caro, M. Vásquez de Parga, B. Calles, J. Sempere, T. Perez, J. Ruiz, P. García. Detection of functional Motifs in Biosequences: A grammatical approach. Proceeding 5th. Annual Spanish Bioinformatics Conference. Barcelona, España. 2004.
[22] E. Jeltsch, M. Aguirre, G. Rosales. Generación de formas pictóricas sobre un sistema de Inferencia a través de TreeBag. Actas del X Encuentro Chileno de Computación. Copiapó, Chile. 2002.
[23] E. Jeltsch, M. Aguirre, G. Rosales. Aplicaciones en TreeBag. Actas del IV Congreso de Educación Superior en Computación. Copiapó, Chile. 2002.