This volume contains the papers prepared for the 2nd International Conference on Natural Language Processing, held 2-4 June in Patras, Greece. The conference program features invited talks and submitted papers, c- ering a wide range of NLP areas: text segmentation, morphological analysis, lexical knowledge acquisition and representation, grammar formalism and s- tacticparsing, discourse analysis, languagegeneration, man-machineinteraction, machine translation, word sense disambiguation, and information extraction. The program committee received 71 abstracts, of which unfortunately no more than 50% could be accepted. Every paper was reviewed by at least two reviewers. The fairness of the reviewing process is demonstrated by the broad spread of institutions and countries represented in the accepted papers. So many have contributed to the success of the conference. The primary credit, ofcourse, goes to theauthors andto the invitedspeakers. By theirpapers and their inspired talks they established the quality of the conference. Secondly, thanks should go to the referees and to the program committee members who did a thorough and conscientious job. It was not easy to select the papers to be presented. Last, but not least, my special thanks to the organizing committee for making this conference happ

Intelligent agents are one of the most important developments in computer science in the 1990s. Agents are of interest in many important application areas, ranging from human-computer interaction to industrial process control. The ATAL workshop series aims to bring together researchers interested in the core aspects of agent technology. Speci?cally, ATAL addresses issues such as th- ries of agency, software architectures for intelligent agents, methodologies and programming languages for realizing agents, and software tools for developing and evaluating agent systems. One of the strengths of the ATAL workshop series is its emphasis on the synergies between theories, infrastructures, architectures, methodologies, formal methods, and languages. This year's workshop continued the ATAL trend of attracting a large n- ber of high-quality submissions. In more detail, 75 papers were submitted to the ATAL-99 workshop, from 19 countries. After stringent reviewing, 22 papers wereacceptedforpresentationattheworkshop.Aftertheworkshop, thesepapers were revised on the basis of comments received both from the original reviewers and from discussions at the workshop itself. This volume contains these revised papers.

The need to improve communication between humans and computers has been instrumental in de ning new modalities of communication, and new ways of interacting with machines. Gestures can convey information for which other modalities are not e cient or suitable. In natural and user-friendly interaction, gesturescanbeused, asasinglemodality, orcombinedinmultimodalinteraction schemes which involvespeech, or textual media. Speci cation methodologiescan be developed to design advanced interaction processes in order to de ne what kind of gestures are used, which meaning they convey, and what the paradigms of interaction are. Research centred on gesture interaction has recently provided signi cant technologicalimprovements, in particular: gesture capture and tra- ing (from video streams or other input devices), motion recognition, motion generation, and animation. In addition, active research in the elds of signal processing, pattern recognition, arti cial intelligence, and linguistics is relevant to the areas covered by the multidisciplinary research on gesture as a means of communication. Resulting fromathree-dayinternationalworkshopin Gif-sur-Yvette, France, with 80 participants from ten countries all over the world, this book presents contributions on gesture under the focus of human-computer communication. The workshop was run by Universit e Paris Sud, Orsay, on the lines of GW'96 at York University, UK, and GW'97 at Bielefeld University, Germany. Its purpose was to bring together scientists from researchand industrial organisationswo- ing on all aspects of gesture modelling and interaction. The book is organised in sixsections, coveringhumanperceptionandproductionofgesture, gestureloc- isation and movement segmentation, vision-based recognition and sign language recognition, gesture synthesis and animation, and multimodality.

Most of the books about computational (lexical) semantic lexicons deal with the depth (or content) aspect of lexicons, ignoring the breadth (or coverage) aspect. This book presents a first attempt in the community to address both issues: content and coverage of computational semantic lexicons, in a thorough manner. Moreover, it addresses issues which have not yet been tackled in implemented systems such as the application time of lexical rules. Lexical rules and lexical underspecification are also contrasted in implemented systems. The main approaches in the field of computational (lexical) semantics are represented in the present book (including Wordnet, CyC, Mikrokosmos, Generative Lexicon). This book embraces several fields (and subfields) as different as: linguistics (theoretical, computational, semantics, pragmatics), psycholinguistics, cognitive science, computer science, artificial intelligence, knowledge representation, statistics and natural language processing. The book also constitutes a very good introduction to the state of the art in computational semantic lexicons of the late 1990s.

ABOUT THIS BOOK This book is intended for researchers who want to keep abreast of cur rent developments in corpus-based natural language processing. It is not meant as an introduction to this field; for readers who need one, several entry-level texts are available, including those of (Church and Mercer, 1993; Charniak, 1993; Jelinek, 1997). This book captures the essence of a series of highly successful work shops held in the last few years. The response in 1993 to the initial Workshop on Very Large Corpora (Columbus, Ohio) was so enthusias tic that we were encouraged to make it an annual event. The following year, we staged the Second Workshop on Very Large Corpora in Ky oto. As a way of managing these annual workshops, we then decided to register a special interest group called SIGDAT with the Association for Computational Linguistics. The demand for international forums on corpus-based NLP has been expanding so rapidly that in 1995 SIGDAT was led to organize not only the Third Workshop on Very Large Corpora (Cambridge, Mass. ) but also a complementary workshop entitled From Texts to Tags (Dublin). Obviously, the success of these workshops was in some measure a re flection of the growing popularity of corpus-based methods in the NLP community. But first and foremost, it was due to the fact that the work shops attracted so many high-quality papers."

Computational semantics is concerned with computing the meanings of linguistic objects such as sentences, text fragments, and dialogue contributions. As such it is the interdisciplinary child of semantics, the study of meaning and its linguistic encoding, and computational linguistics, the discipline that is concerned with computations on linguistic objects.
From one parent computational semantics inherits concepts and techniques that have been developed under the banner of formal (or model-theoretic) semantics. This blend of logic and linguistics applies the methods of logic to the description of meaning. From the other parent the young discipline inherits methods and techniques for parsing sentences, for effective and efficient representation of syntactic structure and logical form, and for reasoning with semantic information. Computational semantics integrates and further develops these methods, concepts and techniques.
This book is a collection of papers written by outstanding researchers in the newly emerging field of computational semantics. It is aimed at those linguists, computer scientists, and logicians who want to know more about the algorithmic realisation of meaning in natural language and about what is happening in this field of research. There is a general introduction by the editors.

Human language capabilities are based on mental proceduresthat are closely linked to the time domain. Listening, understanding, and reacting, on the one hand, as well as planning, formulating, and speaking, onthe other, are performedin a highlyover lapping manner, thus allowing inter human communication to proceed in a smooth and ?uent way. Although it happens to be the natural mode of human language interaction, in cremental processing is still far from becoming a common feature of today's lan guage technology. Instead, it will certainly remain one of the big challenges for research activities in the years to come. Usually considered dif?cult to a degree that rendersit almost intractableforpracticalpurposes, incrementallanguageprocessing has recently been attracting a steadily growing interest in the spoken language pro cessing community. Its notorious dif?culty can be attributed mainly to two reasons: Due to the inaccessibility of the right context, global optimization criteria are no longer available. This loss must be compensated for by communicating larger search spaces between system components or by introducing appropriate repair mechanisms. In any case, the complexity of the task can easily grow by an order of magnitude or even more. Incrementality is an almost useless feature as long as it remains a local property of individual system components. The advantages of incremental processing can be effectiveonly if all the componentsof a producer consumerchain consistently adhere to the same pattern of temporal behavior.

Information extraction (IE) is a new technology enabling relevant content to be extracted from textual information available electronically. IE essentially builds on natural language processing and computational linguistics, but it is also closely related to the well established area of information retrieval and involves learning. In concert with other promising intelligent information processing technologies like data mining, intelligent data analysis, text summarization, and information agents, IE plays a crucial role in dealing with the vast amounts of information accessible electronically, for example from the Internet. The book is based on the Second International School on Information Extraction, SCIE-99, held in Frascati near Rome, Italy in June/July 1999.

Machine translation (MT) is the area of computer science and applied linguistics dealing with the translation of human languages such as English and German. MT on the Internet has become an important tool by providing fast, economical and useful translations. With globalisation and expanding trade, demand for translation is set to grow.Translation Engines covers theoretical and practical aspects of MT, both classic and new, including: - Character sets and formatting languages - Translation memory - Linguistic and computational foundations - Basic computational linguistic techniques - Transfer and interlingua MT - Evaluation Software accompanies the text, providing readers with hands on experience of the main algorithms.

This book contains the collection of papers presented at the Second Workshop on Text, Speech and Dialogue - TSD'99 held in Plzen and Mari ansk eLazn e (Czech Republic) on 13{17 September 1999. The general objective of the workshop was to present state{of{the{art technology and recent achievements in the eld of natural language processing. A total of 57 papers and 19 posters contributed by 128 authors (63 from Central Europe, 11 from Eastern Europe, 33 from Western Europe, 2 from Africa, 13 from America, and 6 from Asia) were included in the workshop proceedings. The workshop is an interdisciplinary forum, which brings together research in speech and language processing as well as research in the Eastern and Western hemisphere. We feel that the mixture of di erent approaches and applications gives all of us a great opportunity to bene t and learn from each other. We would like to gratefully thank the invited speakers and the authors of the papers for their valuable contributions, the Medav GmbH (Uttenreuth, GER) and the SpeechWorks (Boston, USA) for their nancial support, and Prof. V- tracky for greeting the workshop on behalf of the University of West Bohemia.

Machine Conversationsis a collection of some of the best research available in the practical arts of machine conversation. The book describes various attempts to create practical and flexible machine conversation - ways of talking to computers in an unrestricted version of English or some other language. While this book employs and advances the theory of dialogue and its linguistic underpinnings, the emphasis is on practice, both in university research laboratories and in company research and development. Since the focus is on the task and on the performance, this book provides some of the first-rate work taking place in industry, quite apart from the academic tradition. It also reveals striking and relevant facts about the tone of machine conversations and closely evaluates what users require. Machine Conversations is an excellent reference for researchers interested in computational linguistics, cognitive science, natural language processing, artificial intelligence, human computer interfaces and machine learning.

Stochastically-Based Semantic Analysis investigates the problem of automatic natural language understanding in a spoken language dialog system. The focus is on the design of a stochastic parser and its evaluation with respect to a conventional rule-based method. Stochastically-Based Semantic Analysis will be of most interest to researchers in artificial intelligence, especially those in natural language processing, computational linguistics, and speech recognition. It will also appeal to practicing engineers who work in the area of interactive speech systems.

ThisvolumecontainsaselectionofpaperspresentedattheInternationalConf- ence on Analytic Tableaux and Related Methods (TABLEAUX'99) held on June 7-11, 1999 at the Inn at Saratoga, Saratoga Springs, NY, USA. This conference was the continuation of international meetings on Theorem Proving with A- lytic Tableaux and Related Methods held in Lautenbach near Karlsruhe (1992), Marseille (1993), Abingdon near Oxford (1994), St. Goar near Koblenz (1995), Terrasini near Palermo (1996), Pont-' a-Mousson near Nancy (1997), and Oist- wijk near Tilburg (1998). TABLEAUX'99 marks the ?rst time the conference has been held in North America. Tableau and related methods have been found to be convenient and e?ective for automating deduction in various non-standard logics as well as in classical logic. Examples taken from this meeting alone include temporal, description, tense, quantum, modal, projective, hybrid, intuitionistic, and linear logics. - eas of application include veri?cation of software and computer systems, ded- tive databases, knowledge representation and its required inference engines, and system diagnosis. The conference brought together researchers interested in all aspects - theoretical foundations, implementation techniques, systems devel- ment and applications - of the mechanization of reasoning with tableaux and related methods.

Natural Semantics has become a popular tool among programming language researchers for specifying many aspects of programming languages. However, due to the lack of practical tools for implementation, the natural semantics formalism has so far largely been limited to theoretical applications.
This book introduces the rational meta-language RML as a practical language for natural semantics specifications. The main part of the work is devoted to the problem of compiling natural semantics, actually RML, into highly efficient code. For this purpose, an effective compilation strategy for RML is developed and implemented in the rml2c compiler. This compiler ultimately produces low-level C code. Benchmarking results show that rml2c-produced code is much faster than code resulting from compilers based on alternative implementation approaches.

The last decade has been one of dramatic progress in the field of Natural Language Processing (NLP). This hitherto largely academic discipline has found itself at the center of an information revolution ushered in by the Internet age, as demand for human-computer communication and informa tion access has exploded. Emerging applications in computer-assisted infor mation production and dissemination, automated understanding of news, understanding of spoken language, and processing of foreign languages have given impetus to research that resulted in a new generation of robust tools, systems, and commercial products. Well-positioned government research funding, particularly in the U. S., has helped to advance the state-of-the art at an unprecedented pace, in no small measure thanks to the rigorous 1 evaluations. This volume focuses on the use of Natural Language Processing in In formation Retrieval (IR), an area of science and technology that deals with cataloging, categorization, classification, and search of large amounts of information, particularly in textual form. An outcome of an information retrieval process is usually a set of documents containing information on a given topic, and may consist of newspaper-like articles, memos, reports of any kind, entire books, as well as annotated image and sound files. Since we assume that the information is primarily encoded as text, IR is also a natural language processing problem: in order to decide if a document is relevant to a given information need, one needs to be able to understand its content."

This book constitutes the thoroughly refereed post-proceedings of the Second International Conference on Logical Aspects of Computational Linguistics, LACL '97, held in Nancy, France in September 1997.
The 10 revised full papers presented were carefully selected during two rounds of reviewing. Also included are two comprehensive invited papers. Among the topics covered are type theory, various types of grammars, linear logic, parsing, type-directed natural language processing, proof-theoretic aspects, concatenation logics, and mathematical languages.

In knowledge-based natural language generation, issues of formal knowledge representation meet with the linguistic problems of choosing the most appropriate verbalization in a particular situation of utterance. Lexical Semantics and Knowledge Representation in Multilingual Text Generation presents a new approach to systematically linking the realms of lexical semantics and knowledge represented in a description logic. For language generation from such abstract representations, lexicalization is taken as the central step: when choosing words that cover the various parts of the content representation, the principal decisions on conveying the intended meaning are made. A preference mechanism is used to construct the utterance that is best tailored to parameters representing the context. Lexical Semantics and Knowledge Representation in Multilingual Text Generation develops the means for systematically deriving a set of paraphrases from the same underlying representation with the emphasis on events and verb meaning. Furthermore, the same mapping mechanism is used to achieve multilingual generation: English and German output are produced in parallel, on the basis of an adequate division between language-neutral and language-specific (lexical and grammatical) knowledge. Lexical Semantics and Knowledge Representation in Multilingual Text Generation provides detailed insights into designing the representations and organizing the generation process. Readers with a background in artificial intelligence, cognitive science, knowledge representation, linguistics, or natural language processing will find a model of language production that can be adapted to a variety of purposes.

This volume is a selection of papers presented at a workshop entitled Predicative Forms in Natural Language and in Lexical Knowledge Bases organized in Toulouse in August 1996. A predicate is a named relation that exists among one or more arguments. In natural language, predicates are realized as verbs, prepositions, nouns and adjectives, to cite the most frequent ones. Research on the identification, organization, and semantic representa tion of predicates in artificial intelligence and in language processing is a very active research field. The emergence of new paradigms in theoretical language processing, the definition of new problems and the important evol ution of applications have, in fact, stimulated much interest and debate on the role and nature of predicates in naturallangage. From a broad theoret ical perspective, the notion of predicate is central to research on the syntax semantics interface, the generative lexicon, the definition of ontology-based semantic representations, and the formation of verb semantic classes. From a computational perspective, the notion of predicate plays a cent ral role in a number of applications including the design of lexical knowledge bases, the development of automatic indexing systems for the extraction of structured semantic representations, and the creation of interlingual forms in machine translation."

Machine Translation and the Information Soup! Over the past fty years, machine translation has grown from a tantalizing dream to a respectable and stable scienti c-linguistic enterprise, with users, c- mercial systems, university research, and government participation. But until very recently, MT has been performed as a relatively distinct operation, so- what isolated from other text processing. Today, this situation is changing rapidly. The explosive growth of the Web has brought multilingual text into the reach of nearly everyone with a computer. We live in a soup of information, an increasingly multilingual bouillabaisse. And to partake of this soup, we can use MT systems together with more and more tools and language processing technologies|information retrieval engines, - tomated text summarizers, and multimodal and multilingual displays. Though some of them may still be rather experimental, and though they may not quite t together well yet, it is clear that the future will o er text manipulation systems that contain all these functions, seamlessly interconnected in various ways.

This book constitutes the refereed proceedings of the Fourth International Colloquium on Grammatical Inference, ICGI-98, held in Ames, Iowa, in July 1998.
The 23 revised full papers were carefully reviewed and selected for inclusion in the book from a total of 35 submissions. The book addresses a wide range of grammatical inference theory such as automata induction, grammar induction, automatic language acquisition, etc. as well as a variety of applications in areas like syntactic pattern recognition, adaptive intelligent agents, diagnosis, computational biology, data mining, and knowledge discovery.

A broad-ranging survey of our current understanding of visual languages and their theoretical foundations. Its main focus is the definition, specification, and structural analysis of visual languages by grammars, logic, and algebraic methods and the use of these techniques in visual language implementation. Researchers in formal language theory, HCI, artificial intelligence, and computational linguistics will all find this an invaluable guide to the current state of research in the field.

Marcus Contextual Grammars is the first monograph to present a class of grammars introduced about three decades ago, based on the fundamental linguistic phenomenon of strings-contexts interplay (selection). Most of the theoretical results obtained so far about the many variants of contextual grammars are presented with emphasis on classes of questions with relevance for applications in the study of natural language syntax: generative powers, descriptive and computational complexity, automata recognition, semilinearity, structure of the generated strings, ambiguity, regulated rewriting, etc. Constant comparison with families of languages in the Chomsky hierarchy is made. Connections with non-linguistic areas are established, such as molecular computing. Audience: Researchers and students in theoretical computer science (formal language theory and automata theory), computational linguistics, mathematical methods in linguistics, and linguists interested in formal models of syntax.

This book constitutes the strictly refereed post-conference proceedings of the First International Conference on Logical Aspects of Computational Linguistics, LACL '96, held in Nancy, France in April 1996.
The volume presents 18 revised full papers carefully selected and reviewed for inclusion in the book together with four invited contributions by leading authorities and an introductory survey with a detailed bibliography. The papers cover all relevant logical aspects of computational linguistics like logical inference, grammars, logical semantics, natural language processing, formal proofs, logic programming, type theory, etc.

The series serves to propagate investigations into language usage, especially with respect to computational support. This includes all forms of text handling activity, not only interlingual translations, but also conversions carried out in response to different communicative tasks. Among the major topics are problems of text transfer and the interplay between human and machine activities.

Nachdem die letztjiihrige DAGM-Tagung an der iiltesten Universitat Deutsch- lands stattfand, freut es uns, daJ3 wir das diesjahrige Mustererkennungs-Sym- posium jetzt an Deutschlands altester Technischer Universitat nun schon zum zweitenmal veranstalten durfen. An der Carolo-Wilhelmina zu Braunschweig (gegrundet im Jahre 1745) ist Forschung auf den Gebieten der Mustererken- nung, der Sprachverarbeitung und der Bildverarbeitung schon seit Jahrzehnten im Institut fiir Nachrichtentechnik (INT) beheimatet. Seit 1986 wird am Institut fiir Robotik und Prozefiinformatik (IRP) auf den Gebieten der aktiven optischen 3D Oberflachenerfassung und der Analyse von Tiefendaten fiir vision-gestutzte Robotikanwendungen geforscht. Daneben gibt es an der Technischen Universitat sowie an den Forschungseinrichtungen der Region eine Vielzahl von Bereichen, in denen Methoden der Mustererkennung in unterschiedlichsten Anwendungsgebie- ten fur den praktischen Einsatz vorbereitet werden; diese reichen von melkenden Robotern bis hin zur sichtgestutzten automatischen Navigation von Helikoptern und zu Anwendungen in der virtuellen Medizin. Von insgesamt 90 eingereichten Beitragen wurden yom Programmkomitee 34 als Vortrag und 30 zur Posterprasentation angenommen. Die Beitrage uberdecken - wie in fruheren Jahren auch - das gesamte Spektrum des von der DAGM be- treuten Themengebietes: Von den theoretischen Grundlagen, Musterinvarianten, neuronalen Netzen uber die Bildsegmentierung bis hin zur Erkennung in und Interpretation von statischen und dynamischen 3D Szenen. Auch Beitrage zur Schrift- und Spracherkennung sind wiederum wesentlicher Bestandteil des Pro- gramms. Bei den Anwendungen ist dieses Jahr insbesondere der medizinische Bereich stark vertreten.