Lecture Notes in Artificial Intelligence
Subseries of Lecture Notes in Computer Science
Edited by J. G. Carbonell and J. Siekmann
Lecture Notes in Computer Science
Edited by G. Goos, J. Hartmanis, and J. van Leeuwen
2507
3
Berlin
Heidelberg
New York
Barcelona
Hong Kong
London
Milan
Paris
Tokyo
Guilherme Bittencourt Geber L. Ramalho (Eds.)
Advances in
Artificial Intelligence
16th Brazilian Symposium on Artificial Intelligence, SBIA 2002
Porto de Galinhas/Recife, Brazil, November 11-14, 2002
Proceedings
13
Series Editors
Jaime G. Carbonell, Carnegie Mellon University, Pittsburgh, PA, USA
Jörg Siekmann, University of Saarland, Saarbrücken, Germany
Volume Editors
Guilherme Bittencourt
Universidade Federal de Santa Catarina
Departamento de Automação e Sistemas
88040-900 Florianópolis, SC, Brazil
E-mail: [email protected]
Geber L. Ramalho
Universidade Federal de Pernambuco
Centro de Informática
Cx. Postal 7851, 50732-970 Recife, PE, Brazil
E-mail: [email protected]
Cataloging-in-Publication Data applied for
Bibliographic information published by Die Deutsche Bibliothek
Die Deutsche Bibliothek lists this publication in the Deutsche Nationalbibliographie;
detailed bibliographic data is available in the Internet at <http://dnd.ddb.de>.
CR Subject Classification (1998): I.2, F.4.1, H.2.8
ISSN 0302-9743
ISBN 3-540-00124-7 Springer-Verlag Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,
reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication
or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,
in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are
liable for prosecution under the German Copyright Law.
Springer-Verlag Berlin Heidelberg New York,
a member of BertelsmannSpringer Science+Business Media GmbH
http://www.springer.de
© Springer-Verlag Berlin Heidelberg 2002
Printed in Germany
Typesetting: Camera-ready by author, data conversion by Da-TeX Gerd Blumenstein
Printed on acid-free paper
SPIN: 10870871
06/3142
543210
Preface
The biennial Brazilian Symposium on Artificial Intelligence (SBIA 2002) – of
which this is the 16th event – is a meeting and discussion forum for artificial
intelligence researchers and practitioners worldwide. SBIA is the leading conference in Brazil for the presentation of research and applications in artificial
intelligence. The first SBIA was held in 1984, and since 1995 it has been an
international conference, with papers written in English and an international
program committee, which this year was composed of 45 researchers from 13
countries. SBIA 2002 was held in conjunction with the VII Brazilian Symposium
on Neural Networks (SBRN 2002). SBRN 2002 focuses on neural networks and
on other models of computational intelligence.
SBIA 2002, supported by the Brazilian Computer Society (SBC), was held
in Porto de Galinhas/Recife, Brazil, 11–14 November 2002. The call for papers
was very successful, resulting in 146 papers submitted from 18 countries. A total
of 39 papers were accepted for publication in the proceedings. We would like to
thank the SBIA 2002 sponsoring organizations, CNPq, Capes, and CESAR, and
also all the authors who submitted papers. In particular, we would like to thank
the program committee members and the additional referees for the difficult
task of reviewing and commenting on the submitted papers. We are also very
grateful to our colleagues who provided invaluable organizational support and
to Richard van de Stadt, the author of the Cyberchair system, a free software
under GNU General Public License, that supported all the review process and
the preparation of the proceedings.
November 2002
Guilherme Bittencourt
Geber Ramalho
Organization
SBIA 2002 was held in conjunction with the VII Brazilian Symposium on Neural
Networks (SBRN 2002). Both conferences were organized by AI research groups
that belong to the Federal University of Pernambuco.
Chair
Geber Ramalho (UFPE, Brazil)
Steering Committee
Ana Teresa Martins (UFC, Brazil)
Guilherme Bittencourt (UFSC, Brazil)
Jaime Sichman (USP, Brazil)
Solange Rezende (USP, Brazil)
Organizing Committee
Jacques Robin (UFPE, Brazil)
Flávia Barros (UFPE, Brazil)
Francisco Carvalho (UFPE, Brazil)
Guilherme Bitencourt (UFSC, Brazil)
Patrı́cia Tedesco (UFPE, Brazil)
Solange Rezende (USP, Brazil)
Supporting Scientific Society
SBC
Sociedade Brasileira de Computação
Organization
VII
Program Committee
Guilherme Bittencourt (Chair) Universidade Federal de Santa Catarina
(Brazil)
Agnar Aamodt
Norwegian University of Science and Technology (Norway)
Alexis Drogoul
Université Paris VI (France)
Ana Lúcia Bazzan
Universidade Federal do Rio Grande do Sul
(Brazil)
Ana Teresa Martins
Universidade Federal do Ceará (Brazil)
Andre Valente
Knowledge Systems Ventures (USA)
Carles Sierra
Institut d’Investigació en Intelligència Artificial
(Spain)
Christian Lemaitre
Laboratorio Nacional de Informatica Avanzada
(Mexico)
Cristiano Castelfranchi
Institute of Psychology of CNR (Italy)
Dı́bio Leandro Borges
PUC-PR (Brazil)
Donia Scott
University of Brighton (United Kingdom)
Eugênio Costa Oliveira
Universidade do Porto (Portugal)
Evandro de Barros Costa
Universidade Federal de Alagoas (Brazil)
Fábio Cozman
Universidade de São Paulo (Brazil)
Flávia Barros
Universidade Federal de Pernambuco (Brazil)
Francisco Carvalho
Universidade Federal de Pernambuco (Brazil)
Gabriel Pereira Lopes
Universidade Nova de Lisboa (Portugal)
Gabriela Henning
Universidad Nacional del Litoral (Argentina)
Geber Ramalho
Universidade Federal de Pernambuco (Brazil)
Gerhard Widmer
Austrian Research Institute for Artificial Intelligence (Austria)
Gerson Zaverucha
Universidade Federal do Rio de Janeiro (Brazil)
Helder Coelho
Universidade de Lisboa (Portugal)
Jacques Wainer
Universidade de Campinas (Brazil)
Jacques Robin
Universidade Federal de Pernambuco (Brazil)
Jacques Calmet
Universität Karlsruhe (Germany)
Jaime Sichman
Universidade de São Paulo (Brazil)
Kathy McKeown
Columbia University (USA)
Lluis Godo Lacasa
Artificial Intelligence Research Institute
(Spain)
Luis Otávio Alvares
Universidade Federal do Rio Grande do Sul
(Brazil)
Marcelo Ladeira
Universidade de Brası́lia (Brazil)
Maria Carolina Monard
Universidade de São Paulo (Brazil)
Michael Huhns
University of South Carolina (USA)
Nitin Indurkhya
University of New South Wales (Australia)
Olivier Boissier
Ecole Nationale Superieure des Mines de SaintEtienne (France)
Pavel Brazdil
Universidade do Porto (Portugual)
VIII
Organization
Pedro Paulo B. de Oliveira
Ramon Lopes de Mantaras
Rosaria Conte
Sandra Sandri
Solange Rezende
Stefano Cerri
Tarcı́sio Pequeno
Uma Garimella
Vincent Corruble
Vera Lúcia Strube de Lima
Universidade Presbiteriana Mackenzie (Brazil)
Institut d’Investigació en Intelligència Artificial
(Spain)
National Research Council (Italy)
Instituto Nacional de Pesquisas Espaciais
(Brazil)
Universidade de São Paulo (Brazil)
LIRMM (France)
Universidade Federal do Ceará (Brazil)
AP State Council for Higher Education (India)
LIP6, Université Paris VI (France)
PUC-RS (Brazil)
Sponsoring Organizations
The SBIA 2002 conference received financial support from the following
institutions:
CNPq
CAPES
CESAR
Conselho Nacional de Desenvolvimento Cientı́fico e
Tecnológico
Fundação Coordenação de Aperfeiçoamento de Pessoal de Nı́vel Superior
Centro de Estudos e Sistemas Avançados do Recife
Referees
Adam Kilgarriff
Alipio Jorge
Alneu de Andrade Lopes
Ana Maria Monteiro
Ana Paula Rocha
Anna H.R. Costa
Augusto Cesar Pinto Loureiro da Costa
Basilis Gidas
Carlos Soares
Caroline Varaschin Gasperin
Dante Augusto Couto Barone
Diogo Lucas
Edson Augusto Melanda
Edward Hermann Haeusler
Fernando Carvalho
Fernando Gomide
Fernando de Carvalho Gomes
Francisco Tavares
Frederico Luiz Gonçalves de Freitas
Germano C. Vasconcelos
Gina M.B. Oliveira
Gustavo Alberto Giménez Lugo
Gustavo Enrique de A.P. Alves Batista
Jaqueline Brigladori Pugliesi
Joao Carlos Pereira da Silva
Joaquim Costa
Jomi Fred Hübner
José Augusto Baranauskas
João Luis Pinto
Kees van Deemter
Kelly Christine C.S. Fernandes
Lucia Helena Machado Rino
Luis Antunes
Luis Moniz
Luis Torgo
Mara Abel
Marcelino Pequeno
Marco Aurelio C. Pacheco
Organization
Marcos Ferreira de Paula
Maria Benedita Malheiro
Mario Benevides
Marta Mattoso
Maurı́cio Marengoni
Maxime Morge
Nicandro Cruz
Nizam Omar
Nuno Correia
Nuno Marques
Patricia Tedesco
Paulo Cortez
Paulo Quaresma
Pavel Petrovic
Rafael H. Bordini
Renata Vieira
Rita A. Ribeiro
Riverson Rios
Rosa M. Vicari
Sheila Veloso
Teresa Bernarda Ludermir
Tore Amble
IX
Table of Contents
Theoretical and Logical Methods
On Special Functions and Theorem Proving in Logics for ’Generally’ . . . . . . . . 1
Sheila R. M. Veloso and Paulo A. S. Veloso
First-Order Contextual Reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Laurent Perrussel
Logics for Approximate Reasoning:
Approximating Classical Logic “From Above” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Marcelo Finger and Renata Wassermann
Attacking the Complexity of Prioritized Inference Preliminary Report . . . . . . 31
Renata Wassermann and Samir Chopra
A New Approach to the Identification Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Carlos Brito
Towards Default Reasoning through MAX-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Berilhes Borges Garcia and Samuel M. Brasil, Jr.
Autonomous Agents and Multi-agent Systems
Multiple Society Organisations and Social Opacity:
When Agents Play the Role of Observers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Nuno David, Jaime Simão Sichman, and Helder Coelho
Altruistic Agents in Dynamic Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .74
Eduardo Camponogara
Towards a Methodology for Experiments with Autonomous Agents . . . . . . . . . 85
Luis Antunes and Helder Coelho
How Planning Becomes Improvisation? – A Constraint Based Approach
for Director Agents in Improvisational Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Márcia Cristina Moraes and Antônio Carlos da Rocha Costa
Extending the Computational Study of Social Norms
with a Systematic Model of Emotions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
Ana L. C. Bazzan, Diana F. Adamatti, and Rafael H. Bordini
A Model for the Structural, Functional, and Deontic Specification
of Organizations in Multiagent Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Jomi Fred Hübner, Jaime Simão Sichman, and Olivier Boissier
The Queen Robots: Behaviour-Based Situated Robots
Solving the N-Queens Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
Paulo Urbano, Luı́s Moniz, and Helder Coelho
XII
Table of Contents
The Conception of Agents as Part of a Social Model
of Distance Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .140
João Luiz Jung, Patrı́cia Augustin Jaques, Adja Ferreira de Andrade,
and Rosa Maria Vicari
Emotional Valence-Based Mechanisms and Agent Personality . . . . . . . . . . . . . 152
Eugénio Oliveira and Luı́s Sarmento
Simplifying Mobile Agent Development
through Reactive Mobility by Failure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
Alejandro Zunino, Marcelo Campo, and Cristian Mateos
Dynamic Social Knowledge: The Timing Evidence . . . . . . . . . . . . . . . . . . . . . . . . 175
Augusto Loureiro da Costa and Guilherme Bittencourt
Machine Learning
Empirical Studies of Neighborhood Shapes
in the Massively Parallel Diffusion Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
Sven E. Eklund
Ant-ViBRA: A Swarm Intelligence Approach
to Learn Task Coordination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Reinaldo A. C. Bianchi and Anna H. R. Costa
Automatic Text Summarization Using a Machine Learning Approach . . . . . 205
Joel Larocca Neto, Alex A. Freitas, and Celso A. A. Kaestner
Towards a Theory Revision Approach for the Vertical Fragmentation
of Object Oriented Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .216
Flavia Cruz, Fernanda Baião, Marta Mattoso, and Gerson Zaverucha
Speeding up Recommender Systems with Meta-prototypes . . . . . . . . . . . . . . . . 227
Byron Bezerra, Francisco de A.T. de Carvalho, Geber L. Ramalho,
and Jean-Daniel Zucker
ActiveCP: A Method for Speeding up User Preferences Acquisition
in Collaborative Filtering Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
Ivan R. Teixeira, Francisco de A.T. de Carvalho, Geber L. Ramalho,
and Vincent Corruble
Making Recommendations for Groups Using Collaborative Filtering
and Fuzzy Majority . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .248
Sérgio R. de M. Queiroz, Francisco de A.T. de Carvalho,
Geber L. Ramalho, and Vincent Corruble
Knowledge Discovery and Data Mining
Mining Comprehensible Rules from Data with an Ant Colony Algorithm . . 259
Rafael S. Parpinelli, Heitor S. Lopes, and Alex A. Freitas
Table of Contents
XIII
Learning in Fuzzy Boolean Networks – Rule Distinguishing Power . . . . . . . . .270
José A.B. Tomé
Attribute Selection with a Multi-objective Genetic Algorithm . . . . . . . . . . . . . 280
Gisele L. Pappa, Alex A. Freitas, and Celso A.A. Kaestner
Applying the Process of Knowledge Discovery in Databases
to Identify Analysis Patterns for Reuse in Geographic Database Design . . . 291
Carolina Silva, Cirano Iochpe, and Paulo Engel
Lithology Recognition by Neural Network Ensembles . . . . . . . . . . . . . . . . . . . . . .302
Rafael Valle dos Santos, Fredy Artola, Sérgio da Fontoura,
and Marley Vellasco
Evolutionary Computation and Artificial Life
2-Opt Population Training for Minimization of Open Stack Problem . . . . . . 313
Alexandre César Muniz de Oliveira and Luiz Antonio Nogueira Lorena
Grammar-Guided Genetic Programming and
Automatically Defined Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
Ernesto Rodrigues and Aurora Pozo
An Evolutionary Behavior Tool for Reactive Multi-agent Systems . . . . . . . . . 334
Andre Zanki Cordenonsi and Luis Otavio Alvares
Controlling the Population Size in Genetic Programming . . . . . . . . . . . . . . . . . .345
Eduardo Spinosa and Aurora Pozo
Uncertainty
The Correspondence Problem under
an Uncertainty Reasoning Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
José Demisio Simões da Silva and Paulo Ouvera Simoni
Random Generation of Bayesian Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
Jaime S. Ide and Fabio G. Cozman
Evidence Propagation in Credal Networks:
An Exact Algorithm Based on Separately Specified Sets of Probability . . . . 376
José Carlos F. da Rocha and Fabio G. Cozman
Restoring Consistency in Systems of Fuzzy Gradual Rules
Using Similarity Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
Isabela Drummond, Lluis Godo, and Sandra Sandri
Natural Language Processing
Syntactic Analysis for Ellipsis Handling in Coordinated Clauses . . . . . . . . . . . 397
Ralph Moreira Maduro and Ariadne M. B. R. Carvalho
Assessment of Selection Restrictions Acquisition . . . . . . . . . . . . . . . . . . . . . . . . . . 407
Alexandre Agustini, Pablo Gamallo, and Gabriel P. Lopes
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .417
Author Index
Adamatti, Diana F. . . . . . . . . . . . . 108
Agustini, Alexandre . . . . . . . . . . . 407
Alvares, Luis Otavio . . . . . . . . . . . 334
Andrade, Adja Ferreira de . . . . . 140
Antunes, Luis . . . . . . . . . . . . . . . . . . . 85
Artola, Fredy . . . . . . . . . . . . . . . . . . 302
Hübner, Jomi Fred . . . . . . . . . . . . .118
Baião, Fernanda . . . . . . . . . . . . . . . 216
Bazzan, Ana L. C. . . . . . . . . . . . . . 108
Bezerra, Byron . . . . . . . . . . . . . . . . 227
Bianchi, Reinaldo A. C. . . . . . . . . 195
Bittencourt, Guilherme . . . . . . . . 175
Boissier, Olivier . . . . . . . . . . . . . . . .118
Bordini, Rafael H. . . . . . . . . . . . . . 108
Brasil, Samuel M., Jr. . . . . . . . . . . . 52
Brito, Carlos . . . . . . . . . . . . . . . . . . . . 41
Kaestner, Celso A.A. . . . . . .205, 280
Campo, Marcelo . . . . . . . . . . . . . . . 163
Camponogara, Eduardo . . . . . . . . . 74
Carvalho, Ariadne M. B. R. . . . . 397
Carvalho, Francisco de A. T. de . . .
. . . . . . . . . . . . . . . . . . . . . . 227, 237, 248
Chopra, Samir . . . . . . . . . . . . . . . . . . 31
Coelho, Helder . . . . . . . . . 63, 85, 129
Cordenonsi, Andre Zanki . . . . . . 334
Corruble, Vincent . . . . . . . . . 237, 248
Costa, Anna H. R. . . . . . . . . . . . . . 195
Costa, Augusto Loureiro da . . . . 175
Cozman, Fabio G. . . . . . . . . 366, 376
Cruz, Flavia . . . . . . . . . . . . . . . . . . . 216
David, Nuno . . . . . . . . . . . . . . . . . . . . 63
Drummond, Isabela . . . . . . . . . . . . 386
Eklund, Sven E. . . . . . . . . . . . . . . . 185
Engel, Paulo . . . . . . . . . . . . . . . . . . . 291
Finger, Marcelo . . . . . . . . . . . . . . . . . 21
Fontoura, Sérgio da . . . . . . . . . . . . 302
Freitas, Alex A. . . . . . . 205, 259, 280
Gamallo, Pablo . . . . . . . . . . . . . . . . 407
Garcia, Berilhes Borges . . . . . . . . . 52
Godo, Lluis . . . . . . . . . . . . . . . . . . . . 386
Ide, Jaime S. . . . . . . . . . . . . . . . . . . 366
Iochpe, Cirano . . . . . . . . . . . . . . . . . 291
Jaques, Patrı́cia Augustin . . . . . . 140
Jung, João Luiz . . . . . . . . . . . . . . . 140
Lopes, Gabriel P. . . . . . . . . . . . . . . 407
Lopes, Heitor S. . . . . . . . . . . . . . . . 259
Lorena, Luiz Antonio Nogueira 313
Maduro, Ralph Moreira . . . . . . . . 397
Mateos, Cristian . . . . . . . . . . . . . . . 163
Mattoso, Marta . . . . . . . . . . . . . . . . 216
Moniz, Luı́s . . . . . . . . . . . . . . . . . . . . 129
Moraes, Márcia Cristina . . . . . . . . 97
Neto, Joel Larocca . . . . . . . . . . . . . 205
Oliveira, Alexandre César Muniz de
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
Oliveira, Eugénio . . . . . . . . . . . . . . 152
Pappa, Gisele L. . . . . . . . . . . . . . . . 280
Parpinelli, Rafael S. . . . . . . . . . . . 259
Perrussel, Laurent . . . . . . . . . . . . . . 11
Rocha Costa, Antônio Carlos da 97
Pozo, Aurora . . . . . . . . . . . . . 324, 345
Queiroz, Sérgio R. de M. . . . . . . . 248
Ramalho, Geber L. . . . 227, 237, 248
Rocha, José Carlos F. da . . . . . . 376
Rodrigues, Ernesto . . . . . . . . . . . . 324
Sandri, Sandra . . . . . . . . . . . . . . . . .386
Santos, Rafael Valle dos . . . . . . . 302
Sarmento, Luı́s . . . . . . . . . . . . . . . . 152
Sichman, Jaime Simão . . . . . 63, 118
Silva, Carolina . . . . . . . . . . . . . . . . . 291
Silva, José Demisio Simões da . .355
Simoni, Paulo Ouvera . . . . . . . . . .355
Spinosa, Eduardo . . . . . . . . . . . . . . 345
418
Author Index
Teixeira, Ivan R. . . . . . . . . . . . . . . . 237
Tomé, José A.B. . . . . . . . . . . . . . . . 270
Urbano, Paulo . . . . . . . . . . . . . . . . . 129
Vellasco, Marley . . . . . . . . . . . . . . . 302
Veloso, Paulo A. S. . . . . . . . . . . . . . . .1
Veloso, Sheila R. M. . . . . . . . . . . . . . 1
Vicari, Rosa Maria . . . . . . . . . . . . .140
Wassermann, Renata . . . . . . . . 21, 31
Zaverucha, Gerson . . . . . . . . . . . . . 216
Zucker, Jean-Daniel . . . . . . . . . . . .227
Zunino, Alejandro . . . . . . . . . . . . . 163