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.

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.

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.

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.

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.

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.

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 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.

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."

The journey towards the autonomous enterprise has begun; there are already companies operating in a highly automated way. Every corporate decision-maker will need to understand the opportunities and risks that the autonomous enterprise presents, to learn how best to navigate the shifting competitive landscape on their journey of change. This book is your guide to this innovation, presenting the concepts in real world contexts by covering the art of the possible today and providing glimpses into the future of business.

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.

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.

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.

This book constitutes the strictly refereed post-workshop documentation of the ECAI'96 Workshop on Dialogue Processing in Spoken Language Systems, held in Budapest, Hungary, in August 1996, during ECAI'96.
The volume presents 16 revised full papers including a detailed introduction and survey paper by the volume editors. The papers are organized in sections on foundations of spoken language dialogue systems, dialogue systems and prosodic aspects of spoken dialogue processing, spoken dialogue systems-design and implementation, and evaluation of systems. The book reports on work being pursued both in academia and in industry as a crucial issue in speech processing.

This is an exciting time for Artificial Intelligence, and for Natural Language Processing in particular. Over the last five years or so, a newly revived spirit has gained prominence that promises to revitalize the whole field: the spirit of empiricism.
This book introduces a new approach to the important NLP issue of automatic ambiguity resolution, based on statistical models of text. This approach is compared with previous work and proved to yield higher accuracy for natural language analysis. An effective implementation strategy is also described, which is directly useful for natural language analysis. The book is noteworthy for demonstrating a new empirical approach to NLP; it is essential reading for researchers in natural language processing or computational linguistics.

This book constitutes the refereed proceedings of the Third International Colloquium on Grammatical Inference, ICGI-96, held in Montpellier, France, in September 1996.
The 25 revised full papers contained in the book together with two invited key papers by Magerman and Knuutila were carefully selected for presentation at the conference. The papers are organized in sections on algebraic methods and algorithms, natural language and pattern recognition, inference and stochastic models, incremental methods and inductive logic programming, and operational issues.

Crypto '96, the Sixteenth Annual Crypto Conference, is sponsored by the International Association for Cryptologic Research (IACR), in cooperation with the IEEE Computer Society Technical Committee on Security and P- vacy and the Computer Science Department of the University of California at Santa Barbara (UCSB). It takes place at UCSB from August 18 to 22, 1996. The General Chair, Richard Graveman, is responsible for local organization and registration. The scientific program was organized by the 16-member Program C- mittee. We considered 115 papers. (An additional 15 submissions had to be summarily rejected because of lateness or major noncompliance with the c- ditions in the Call for Papers.) Of these, 30 were accepted for presentation. In addition, there will be five invited talks by Ernest Brickell. Andrew Clark, Whitfield Diffie, Ronald Rivest, and Cliff Stoll. A Rump Session will be chaired by Stuart Haber. These proceedings contain the revised versions of the 30 contributed talks. least three com- The submitted version of each paper was examined by at mittee members and/or outside experts, and their comments were taken into account in the revisions. However, the authors (and not the committee) bear full responsibility for the content of their papers.

This comprehensive state-of-the-art book is the first devoted to the important and timely issue of evaluating NLP systems. It addresses the whole area of NLP system evaluation, including aims and scope, problems and methodology.
The authors provide a wide-ranging and careful analysis of evaluation concepts, reinforced with extensive illustrations; they relate systems to their environments and develop a framework for proper evaluation. The discussion of principles is completed by a detailed review of practice and strategies in the field, covering both systems for specific tasks, like translation, and core language processors. The methodology lessons drawn from the analysis and review are applied in a series of example cases. A comprehensive bibliography, a subject index, and term glossary are included.