Mauricio Aguirre¹   Eric Jeltsch¹   Gerardo Rosales¹

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 N^o 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. N^o 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. N^o 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. N^o 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. N^o 532, pp. 411-429. 1991.

[11] H.J. Kreowski, Eric Jeltsch. Grammatical Inference based on hyperedge replacement. Lect. Not. Comp. Sci. N^o 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 N^o1, 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 N^o 1, pp. 55-62. 1988. 

[16] W. C. Rounds. Mapping and Grammars on Trees. Mathematical Systems Theory. N^o 4, pp. 257-287. 1970.

[17] James W. Thatcher. Generalized sequential machine maps. Journal of Computer and System Sciences. N^o 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.