Bücher der Reihe Lecture Notes in Artificial Intelligence

SBIA, the Brazilian Symposium on Arti?cial Intelligence, is a biennial event intended to be the main forum of the AI community in Brazil. The SBIA 2004 was the 17th issue of the series initiated in 1984. Since 1995 SBIA has been accepting papers written and presented only in English, attracting researchers from all over the world. At that time it also started to have an international program committee, keynote invited speakers, and proceedings published in the Lecture Notes in Arti?cial Intelligence (LNAI) series of Springer (SBIA 1995, Vol. 991, SBIA 1996, Vol. 1159, SBIA 1998, Vol. 1515, SBIA 2000, Vol. 1952, SBIA 2002, Vol. 2507). SBIA 2004 was sponsored by the Brazilian Computer Society (SBC). It was held from September 29 to October 1 in the city of SE ao Luis, in the northeast of Brazil, together with the Brazilian Symposium on Neural Networks (SBRN). This followed a trend of joining the AI and ANN communities to make the joint event a very exciting one. In particular, in 2004 these two events were also held togetherwiththeIEEEInternationalWorkshoponMachineLearningandSignal Processing (MMLP), formerly NNLP. The organizationalstructure of SBIA 2004was similar to other international scienti?cconferences.Thebackboneofthe conferencewasthe technicalprogram whichwascomplementedbyinvitedtalks,workshops,etc.onthemainAItopics.

The central themes of the 14th International Conference on Knowledge Engineering and Knowledge Management (EKAW 2004) were ontological engineering and the Semantic Web. These provide the key foundational and delivery mechanisms for building open, Web-based knowledge services. However, consistent with the tradition of EKAW conferences, EKAW 2004 was concerned with all aspects of eliciting, acquiring, modelling and managing knowledge, and its role in the construction of knowledge-intensive systems. Indeed a key aspect of the Knowledge Acquisition Workshops (KAWs) held in the US, Europe and Asia over the past 20 years has been the emphasis on 'holistic' knowledge engineering, addressing problem solving, usability, socio-technological factors and knowledge modelling, rather than simply analyzing and designing symbol-level inferential mechanisms. The papers included in this volume are thus drawn from a variety of research areas both at the cutting edge of research in ontologies and the Semantic Web and in the more traditionally grounded areas of knowledge engineering. A Semantic Web service can be seen as the addition of semantic technologies to Web services to produce Web-accessible services that can be described using appropriate ontologies, reasoned about and combined automatically. Since Web services can be seen as Web-accessible computational objects, much of the work in this area is also concerned with problem-solving methods (PSMs).

The modern ?eld of multiagent systems has developed from two main lines of earlier research. Its practitioners generally regard it as a form of arti?cial intelligence (AI). Some of its earliest work was reported in a series of workshops in the US dating from1980,revealinglyentitled,"e;DistributedArti?cialIntelligence,"e;andpioneers often quoted a statement attributed to Nils Nilsson that "e;all AI is distributed. "e; The locus of classical AI was what happens in the head of a single agent, and much MAS research re?ects this heritage with its emphasis on detailed modeling of the mental state and processes of individual agents. From this perspective, intelligenceisultimatelythepurviewofasinglemind,thoughitcanbeampli?ed by appropriate interactions with other minds. These interactions are typically mediated by structured protocols of various sorts, modeled on human conver- tional behavior. But the modern ?eld of MAS was not born of a single parent. A few - searchershavepersistentlyadvocatedideasfromthe?eldofarti?ciallife(ALife). These scientists were impressed by the complex adaptive behaviors of commu- ties of animals (often extremely simple animals, such as insects or even micro- ganisms). The computational models on which they drew were often created by biologists who used them not to solve practical engineering problems but to test their hypotheses about the mechanisms used by natural systems. In the ar- ?cial life model, intelligence need not reside in a single agent, but emerges at the level of the community from the nonlinear interactions among agents. - cause the individual agents are often subcognitive, their interactions cannot be modeled by protocols that presume linguistic competence.

By presenting state-of-the-art results in logical reasoning and formal methods in the context of artificial intelligence and AI applications, this book commemorates the 60th birthday of Jorg H. Siekmann.The 30 revised reviewed papers are written by former and current students and colleagues of Jrg Siekmann; also included is an appraisal of the scientific career of Jrg Siekmann entitled "e;A Portrait of a Scientist: Logics, AI, and Politics."e; The papers are organized in four parts on logic and deduction, applications of logic, formal methods and security, and agents and planning.

This is the fourth volume in a series of books dedicated to basic research in spatial cognition. Spatial cognition is a field that investigates the connection between the physical spatial world and the mental world. Philosophers and researchers have p- posed various views concerning the relation between the physical and the mental worlds: Plato considered pure concepts of thought as separate from their physical manifestations while Aristotle considered the physical and the mental realms as two aspects of the same substance. Descartes, a dualist, discussed the interaction between body and soul through an interface organ and thus introduced a functional view that presented a challenge for the natural sciences and the humanities. In modern psych- ogy, the relation between the physical and the cognitive space has been investigated using thorough experiments, and in artificial intelligence we have seen views as diverse as 'problems can be solved on a representation of the world' and 'a representation of the world is not necessary. ' Today's spatial cognition work establishes a correspondence between the mental and the physical worlds by studying and exploiting their interaction; it investigates how mental space and spatial "e;reality"e; join together in understanding the world and in interacting with it. The physical and representational aspects are equally important in this work. Almost all topics of cognitive science manifest themselves in spatial cognition.

This volume presents revised and extended versions of selected papers presented at the Joint Workshop on Multi-Agent and Multi-Agent-Based Simulation, a workshop federated with the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2004), which was held in New York City, USA, July 19-23, 2004. The workshop was in part a continuation of the International Workshop on Multi-Agent-Based Simulation (MABS) series. - vised versions of papers presented at the four previous MABS workshops have been published as volumes 1534, 1979, 2581, and 2927 in the Lecture Notes in Arti?cial Intelligence series. The aim of the workshop was to provide a forum for work in both appli- tions of multi-agent-based simulation and the technical challenges of simulating large multi-agent systems (MAS). There has been considerable recent progress in modelling and analyzing multi-agent systems, and in techniques that apply MAS models to complex real-world systems such as social systems and organi- tions. Simulation is an increasingly important strand that weaves together this work. In high-risk, high-cost situations, simulations provide critical cost/bene?t leverage, and make possible explorations that cannot be carried out in situ: - Multi-agentapproachestosimulatingcomplexsystemsarekeytoolsinint- disciplinary studies of social systems. Agent-based social simulation (ABSS) researchsimulatesandsynthesizessocialbehaviorinordertounderstandreal social systems with properties of self-organization, scalability, robustness, and openness. - IntheMAScommunity,simulationhasbeenappliedtoawiderangeofMAS research and design problems, from models of complex individual agents - ploying sophisticated internal mechanisms to models of large-scale societies of relatively simple agents which focus more on the interactions between agents.

Edited in collaboration with FoLLI, the Association of Logic, Language and Information, this book inaugurates the new FoLLI LNAI subline. It constitutes the refereed proceedings of the 5th International Conference on Logical Aspects of Computational Linguistics, LACL 2005, held in Bordeaux, France in April 2005.The 25 revised full papers presented were carefully reviewed and selected from over 40 submissions. The papers address a wide range of logical and formal methods in computational linguistics with studies of particular grammar formalisms and their computational properties, language engineering, and traditional topics about the syntax/semantics interface.

The 18th conference of the Canadian Society for the Computational Study of Intelligence (CSCSI) continued the success of its predecessors. This set of - pers re?ects the diversity of the Canadian AI community and its international partners. AI 2005 attracted 135 high-quality submissions: 64 from Canada and 71 from around the world. Of these, eight were written in French. All submitted papers were thoroughly reviewed by at least three members of the Program Committee. A total of 30 contributions, accepted as long papers, and 19 as short papers are included in this volume. We invited three distinguished researchers to give talks about their current research interests: Eric Brill from Microsoft Research, Craig Boutilier from the University of Toronto, and Henry Krautz from the University of Washington. The organization of such a successful conference bene?ted from the coll- oration of many individuals. Foremost, we would like to express our apprec- tion to the Program Committee members and external referees, who provided timely and signi?cant reviews. To manage the submission and reviewing process we used the Paperdyne system, which was developed by Dirk Peters. We owe special thanks to Kellogg Booth and Tricia d'Entremont for handling the local arrangementsandregistration.WealsothankBruceSpencerandmembersofthe CSCSI executive for all their e?orts in making AI 2005 a successful conference.

In recent years the Internet has become a source of data and information of indisputable importance and has immensely gained in acceptance and popularity. The World Wide Web (WWW or Web, for short), frequently named "e;the nervous system of the infor- tion society,"e; offers numerous valuable services leaving no doubt about the signi?cance of the Web in our daily activities at work and at home. Consequently, we have a clear aspiration to meet the obvious need for effective use of its potential by making - provements in both the methods and the technology applied. Among the new research directions observable in Web-related applications, intelligent methods from within the broadly perceived topic of soft computing occupy an important place. AWIC, the "e;Atlantic Web Intelligence Conferences"e; are intended to be a forum for exchange of new ideas and novel practical solutions in this new and exciting ?eld. The conference was born as an initiative of the WIC-Poland and the WIC-Spain Research Centres, both belonging to the Web Intelligence Consortium - WIC (http://wi-consortium.org/). So far, three AWIC conferences have been held: in Madrid, Spain (2003), in Cancun, Mexico (2004), and in ?odz, ' Poland (2005).

Conditionals are fascinating and versatile objects of knowledge representation. On the one hand, they may express rules in a very general sense, representing, for example, plausible relationships, physical laws, and social norms. On the other hand, as default rules or general implications, they constitute a basic tool for reasoning, even in the presence of uncertainty. In this sense, conditionals are intimately connected both to information and inference. Due to their non-Boolean nature, however, conditionals are not easily dealt with. They are not simply true or false - rather, a conditional "e;if A then B"e; provides a context, A, for B to be plausible (or true) and must not be confused with "e;A entails B"e; or with the material implication "e;not A or B."e; This ill- trates how conditionals represent information, understood in its strict sense as reduction of uncertainty. To learn that, in the context A, the proposition B is plausible, may reduce uncertainty about B and hence is information. The ab- ity to predict such conditioned propositions is knowledge and as such (earlier) acquired information. The ?rst work on conditional objects dates back to Boole in the 19th c- tury, and the interest in conditionals was revived in the second half of the 20th century, when the emerging Arti?cial Intelligence made claims for appropriate formaltoolstohandle"e;generalizedrules."e;Sincethen,conditionalshavebeenthe topic of countless publications, each emphasizing their relevance for knowledge representation, plausible reasoning, nonmonotonic inference, and belief revision.

This volume contains selected and thoroughly revised papers plus contributions from invited speakers presented at the First International Workshop on C- straint Solving and Language Processing, held in Roskilde, Denmark, September 1-3, 2004. Constraint Programming and Constraint Solving, in particular Constraint Logic Programming, appear to be a very promising platform, perhaps the most promising present platform, for bringing forward the state of the art in natural language processing, this due to the naturalness in speci?cation and the direct relation to e?cient implementation. Language, in the present context, may - fer to written and spoken language, formal and semiformal language, and even general input data to multimodal and pervasive systems, which can be handled in very much the same ways using constraint programming. The notion of constraints, with slightly di?ering meanings, apply in the ch- acterization of linguistic and cognitive phenomena, in formalized linguistic m- els as well as in implementation-oriented frameworks. Programming techniques for constraint solving have been, and still are, in a period with rapid devel- ment of new e?cient methods and paradigms from which language processing can pro?t. A common metaphor for human language processing is one big c- straintsolvingprocessinwhichthedi?erent(-lyspeci?ed)linguisticandcognitive phases take place in parallel and with mutual cooperation, which ?ts quite well with current constraint programming paradigms.

This volume contains papers presented at the Eighteenth Annual Conference on Learning Theory (previously known as the Conference on Computational Learning Theory) held in Bertinoro, Italy from June 27 to 30, 2005. The technical program contained 45 papers selected from 120 submissions, 3 open problems selected from among 5 contributed, and 2 invited lectures. The invited lectures were given by Sergiu Hart on "e;Uncoupled Dynamics and Nash Equilibrium"e;, and by Satinder Singh on "e;Rethinking State, Action, and Reward in Reinforcement Learning"e;. These papers were not included in this volume. The Mark Fulk Award is presented annually for the best paper co-authored by a student. The student selected this year was Hadi Salmasian for the paper titled "e;The Spectral Method for General Mixture Models"e; co-authored with Ravindran Kannan and Santosh Vempala. The number of papers submitted to COLT this year was exceptionally high. In addition to the classical COLT topics, we found an increase in the number of submissions related to novel classi?cation scenarios such as ranking. This - crease re?ects a healthy shift towards more structured classi?cation problems, which are becoming increasingly relevant to practitioners.

1 "e;Change is inevitable."e; Embracing this quote we have tried to carefully exp- iment with the format of this conference, the 15th International Conference on Inductive Logic Programming, hopefully making it even better than it already was. But it will be up to you, the inquisitive reader of this book, to judge our success. The major changes comprised broadening the scope of the conference to include more diverse forms of non-propositional learning, to once again have tutorials on exciting new areas, and, for the ?rst time, to also have a discovery challenge as a platform for collaborative work. This year the conference was co-located with ICML 2005, the 22nd Inter- tional Conference on Machine Learning, and also in close proximity to IJCAI 2005, the 19th International Joint Conference on Arti?cial Intelligence. - location can be tricky, but we greatly bene?ted from the local support provided by Codrina Lauth, Michael May, and others. We were also able to invite all ILP and ICML participants to shared events including a poster session, an invited talk, and a tutorial about the exciting new area of "e;statistical relational lea- ing"e;. Two more invited talks were exclusively given to ILP participants and were presented as a kind of stock-taking-?ttingly so for the 15th event in a series-but also tried to provide a recipe for future endeavours.

The ?rst workshop "e;Engineering Societies in the Agents World"e; (ESAW) was held in August 2000, in conjunction with the 14th European Conference on Arti?cial Intelligence (ECAI 2000) in Berlin. It was launched by a group of - searchers who thought that the design and development of MASs (multi-agent systems) not only needed adequate theoretical foundations but also a call for new techniques, methodologies and infrastructures to develop MASs as arti?cial societies. The second ESAW was co-located with the European Agent Summer School (ACAI 2001) in Prague, and mostly focused on logics and languages, middleware, infrastructures and applications. In Madrid, the third ESAW c- centrated on models and methodologies and took place with the "e;Cooperative Information Agents"e; workshop (CIA 2002). The fourth ESAW in London was the ?rst one that ran as a stand-alone event: apart from the usual works on methodologies and models, it also stressed the issues of applications and m- tidisciplinary models. Based on the success of previous ESAWs, and also given that the di?cult challenges in the construction of arti?cial societies are not yet fully addressed, the ?fth ESAW workshop was organized in the same spirit as its predecessors. Inparticular,ESAW2004tookplaceattheIRITlaboratoryoftheUniversit' e "e;Paul Sabatier"e; (Toulouse, France), at the end of October 2004. It was not - located with any other scienti?c event, in the same way as ESAW 2003. ESAW 2004 remained committed to the use of the notion of MASs as the seeds for animated, constructive and highly interdisciplinary discussions about techno- gies,methodologiesandtoolsfortheengineeringofcomplexdistributedsystems.

Introduction The dramatic increase in available computer storage capacity over the last 10 years has led to the creation of very large databases of scienti?c and commercial information. The need to analyze these masses of data has led to the evolution of the new ?eld knowledge discovery in databases (KDD) at the intersection of machine learning, statistics and database technology. Being interdisciplinary by nature, the ?eld o?ers the opportunity to combine the expertise of di?erent ?elds intoacommonobjective.Moreover,withineach?elddiversemethodshave been developed and justi?ed with respect to di?erent quality criteria. We have toinvestigatehowthesemethods cancontributeto solvingthe problemofKDD. Traditionally, KDD was seeking to ?nd global models for the data that - plain most of the instances of the database and describe the general structure of the data. Examples are statistical time series models, cluster models, logic programs with high coverageor classi?cation models like decision trees or linear decision functions. In practice, though, the use of these models often is very l- ited, because global models tend to ?nd only the obvious patterns in the data, 1 which domain experts already are aware of . What is really of interest to the users are the local patterns that deviate from the already-known background knowledge. David Hand, who organized a workshop in 2002, proposed the new ?eld of local patterns.

TheInternationalConferenceTSD 2005,the8theventin theseriesonText,Speech,and Dialogue, which originated in 1998, presented state-of-the-art technology and recent achievements in the ?eld of natural language processing. It declared its intent to be an interdisciplinary forum, intertwining research in speech and language processing with its applications in everyday practice. We feel that the mixture of different approaches and applications offered a great opportunity to get acquainted with the current act- ities in all aspects of language communication and to witness the amazing vitality of researchers from developing countries too. The ?nancial support of the ISCA (Inter- tional Speech Communication Association) enabled the wide attendance of researchers from all active regions of the world. Thisyear'sconferencewaspartiallyorientedtowardsmulti-modalhuman-computer interaction (HCI), which can be seen as the most attractive topic of HCI at the present time. In this way, we are involved in a rich complex of communicative activity, facial expressions, hand gestures, direction of gaze, to name but the most obvious ones. The interpretationof each user utterancedependson the context,prosody,facial expressions (e. g. brows raised, brows and gaze both raised) and gestures. Hearers have to adapt to the speaker (e. g. maintainingthe theme of the conversation,smiling etc. ). Research into the interaction of these channels is however limited, often focusing on the interaction between a pair of channels. Six signi?cant scienti?c results achieved in this area in the USA, Japan, Switzerland, Germany, The Netherlands, and the Czech Republic were presented by keynote speakers in special plenary sessions. Further, approx.

Dear delegates,friendsand membersofthe growingKES professionalcommunity,w- come to the proceedings of the 9th International Conference on Knowledge-Based and IntelligentInformationandEngineeringSystemshostedbyLa TrobeUniversityin M- bourne Australia. The KES conference series has been established for almost a decade, and it cont- ues each year to attract participants from all geographical areas of the world, including Europe, the Americas, Australasia and the Paci?c Rim. The KES conferences cover a wide range of intelligent systems topics. The broad focus of the conference series is the theory and applications of intelligent systems. From a pure research ?eld, intel- gent systems have advanced to the point where their abilities have been incorporated into many business and engineering application areas. KES 2005 provided a valuable mechanism for delegates to obtain an extensive view of the latest research into a range of intelligent-systems algorithms, tools and techniques. The conference also gave de- gates the chance to come into contact with those applying intelligent systems in diverse commercial areas. The combination of theory and practice represented a unique opp- tunity to gain an appreciation of the full spectrum of leading-edge intelligent-systems activity. The papers for KES 2005 were either submitted to invited sessions, chaired and organized by respected experts in their ?elds, or to a general session, managed by an extensive International Program Committee, or to the Intelligent Information Hiding and Multimedia Signal Processing (IIHMSP) Workshop, managed by an International Workshop Technical Committee.