Mathematical theorem proving has undergone an impressive development during the last two decades, resulting in a variety of powerful systems for applications in mathematical deduction and knowledge processing. Natural language processing has become a topic of outstanding relevance in information technology, mainly due to the explosive growth of the Web, where by far the largest part of information is encoded in natural language documents.

This monograph focuses on the development of inference tools tailored to applications in natural language processing by demonstrating how the model generation paradigm can be used as a framework for the support of specific tasks in natural language interpretation and natural language based inference in a natural way.

The book appears at a pivotal moment, when much attention is being paid to the task of adding a semantic layer to the Web, and representation and processing of natural language based semantic information pops up as a primary requirement for further technological progress.

The 16th Annual Symposium on Combinatorial Pattern Matching was held on Jeju Island, Korea on June 19-22, 2005. Previous meetings were held in Paris, London, Tucson, Padova, Asilomar, Helsinki, Laguna Beach, Aarhus, Piscataway, Warwick, Montreal, Jerusalem, Fukuoka, Morelia, and Istanbul over the years 1990-2004. In response to the call for papers, CPM 2005 received a record number of 129papers.Eachsubmissionwasreviewedbyatleast threeProgramCommittee members with the assistance of external referees. Since there were many hi- quality papers, the Program Committee's task was extremely di?cult. Through an extensive discussion the Program Committee accepted 37 of the submissions tobepresentedattheconference.Theyconstituteoriginalresearchcontributions in combinatorial pattern matching and its applications. Inadditiontotheselectedpapers, CPM2005hadthreeinvitedpresentations, by Esko Ukkonen from the University of Helsinki, Ming Li from the University of Waterloo, and Naftali Tishby from The Hebrew University of Jerusalem. We would like to thank all Program Committee members and external r- erees for their excellent work, especially given the demanding time constraints; they gave the conference its distinctive character. We also thank all who s- mitted papers for consideration; they all contributed to the high quality of the conference. Finally, we thank the Organizing Committee members and the graduates- dents who worked hard to put in place the logistical arrangements of the c- ference. It is their dedicated contribution that made the conference possible and enjoyable

This volume contains the Proceedings of the 7th International Conference on Text, Speech and Dialogue, held in Brno, Czech Republic, in September 2004, under the auspices of the Masaryk University. This series of international conferences on text, speech and dialogue has come to c- stitute a major forum for presentation and discussion, not only of the latest developments in academic research in these ?elds, but also of practical and industrial applications. Uniquely, these conferences bring together researchers from a very wide area, both intellectually and geographically, including scientists working in speech technology, dialogue systems, text processing, lexicography, and other related ?elds. In recent years the conference has dev- oped into aprimary meetingplacefor speech and languagetechnologistsfrom manydifferent parts of the world and in particular it has enabled important and fruitful exchanges of ideas between Western and Eastern Europe. TSD 2004 offered a rich program of invited talks, tutorials, technical papers and poster sessions, aswellasworkshops andsystemdemonstrations. Atotalof78paperswereaccepted out of 127 submitted, contributed altogether by 190 authors from 26 countries. Our thanks as usual go to the Program Committee members and to the external reviewers for their conscientious and diligent assessment of submissions, and to the authors themselves for their high-quality contributions. We would also like to take this opportunity to express our appreciation to all the members of the Organizing Committee for their tireless efforts in organizing the conference and ensuring its smooth running.

Deep learning on graphs has become one of the hottest topics in machine learning. The book consists of four parts to best accommodate our readers with diverse backgrounds and purposes of reading. Part 1 introduces basic concepts of graphs and deep learning; Part 2 discusses the most established methods from the basic to advanced settings; Part 3 presents the most typical applications including natural language processing, computer vision, data mining, biochemistry and healthcare; and Part 4 describes advances of methods and applications that tend to be important and promising for future research. The book is self-contained, making it accessible to a broader range of readers including (1) senior undergraduate and graduate students; (2) practitioners and project managers who want to adopt graph neural networks into their products and platforms; and (3) researchers without a computer science background who want to use graph neural networks to advance their disciplines.

This book constitutes the refereed proceedings of the 10th International Conference on Computer Analysis of Images and Patterns, CAIP 2003, held in Groningen, The Netherlands in August 2003. The 94 revised papers presented were carefully reviewed and selected from 160 submissions. The papers are organized in topical sections on analysis and understanding, video analysis, segmentation, shape, classification, face recognition, interpolation and spatial transformations, and filtering.

Spoken Dialogue Technology provides extensive coverage of spoken dialogue systems, ranging from the theoretical underpinnings of the study of dialogue through to a detailed look at a number of well-established methods and tools for developing spoken dialogue systems. The book enables students and practitioners to design and test dialogue systems using several available development environments and languages, including the CSLU toolkit, VoiceXML, SALT, and XHTML+ voice. This practical orientation is usually available otherwise only in reference manuals supplied with software development kits. The latest research in spoken dialogue systems is presented along with extensive coverage of the most relevant theoretical issues and a critical evaluation of current research prototypes. A dedicated web site containing supplementary materials, code, links to resources will enable readers to develop and test their own systems (). Previously such materials have been difficult to track down, available only on a range of disparate web sites and this web site provides a unique and useful reference source which will prove invaluable.

The International Conference TSD 2003, the sixth event in the series on Text, Speech, and Dialogue, which originated in 1998, presents state-of-the-art technology and - cent achievements in the ?eld of natural language processing. This year's conference includes invited talks given by top-class researchers (Frederick Jelinek from Johns H- kinsUniversityofBaltimore, SadaokiFuruifromtheUniversityofTechnologyinTokyo, President of ISCA, and Steven Krauwer from the Institute of Linguistics of Utrecht U- versity), plenary and problem-oriented sessions, as well as poster sessions and dem- strations involving 28 functional applications. The conference declares its intent to be an interdisciplinary forum, which intertwines researchinspeechandlanguageprocessingaswellasresearchintheEasternandWestern hemispheres. We feel that the mixture of different approaches and applications gives agreatopportunitytogetacquaintedwiththecurrentactivitiesinallaspectsoflanguage communication and to witness the amazing vitality of research from the former East Block countries. The ?nancial support of ISCA (International Speech Communication Association) enables the wide attendance of researchers from all active regions of the world. This volume contains a collection of all the papers presented at the international conf- ence organized by the Faculty of Applied Sciences of the University of West Bohemia in Pilsen in collaboration with the Faculty of Informatics, Masaryk University in Brno, ? and held in the beautiful city of Ceske Budejo ? vice (South Bohemia, Czech Republic), September 8-12, 2003. Each of the submitted papers was thoroughly reviewed by three membersoftheconferencereviewingteamconsistingofmorethan40world-famouss- cialists in the conference topic areas."

This book constitutes the refereed proceedings of the Third International Symposium on Smart Graphics, SG 2003, held in Heidelberg, Germany in July 2003. The 19 revised full papers and 7 poster papers presented were carefully reviewed and selected for presentation. The papers address smart graphics issues from the points of view of computer science, artificial intelligence, cognitive psychology, and fine art. The papers are organized in topical sections on graphical interaction, visualization techniques, virtual characters, and camera planning.

This book constitutes the refereed proceedings of the 5th International Conference on Text, Speech and Dialogue, TSD 2002, held in Brno, Czech Republic, in September 2002.The 65 revised full papers presented were carefully reviewed and selected from 134 submissions. The papers present a wealth of state-of-the-art research and development results in the field of natural language processing with emphasis on text, speech, and spoken language, ranging from theoretical and methodological issues to applications in various fields, such as web information retrieval, the semantic Web, algorithmic learning, dialogue systems, etc.

This third volume documents the results achieved within a priority program on spatial cognition funded by the German Science Foundation (DFG). The 23 revised full papers presented went through two rounds of reviewing and improvement and reflect the increased interdisciplinary cooperation in the area. The papers are organized in topical sections on routes and navigation, human memory and learning, spatial representation, and spatial reasoning.

This book constitutes the refereed proceedings of the Third International Conference PorTAL 2002 - Portugal for Natural Language Processing, held in Faro, Portugal, in June 2002.The 23 reviewed regular papers and 11 short papers presented were carefully reviewed and selected from 48 submissions. The papers are organized in topical sections on pragmatics, discourse, semantics, and the lexicon; interpreting and generating spoken and written language; language-oriented information retrieval, question answering, summarization, and information extraction; language-oriented machine learning; multi-lingual processing, machine translation, and translation aids; natural language interfaces and dialogue systems; tools and resources; and evaluation of systems.

This book constitutes the thoroughly refereed post-proceedings of the 6th International Conference on Applications of Natural Language to Information Systems, NLDB 2002, held in Stockholm, Sweden in June 2002.The 17 revised full papers and 7 revised short papers presented were carefully selected from 42 submissions during two rounds of reviewing and revision. The papers are organized in topical sections on linguistic aspects of modeling, information retrieval, natural language text understanding, knowledge bases, recognition of information in natural language descriptions, and natural language conversational systems.

Recent Advances in Example-Based Machine Translation is of relevance to researchers and program developers in the field of Machine Translation and especially Example-Based Machine Translation, bilingual text processing and cross-linguistic information retrieval. It is also of interest to translation technologists and localisation professionals.

Recent Advances in Example-Based Machine Translation fills a void, because it is the first book to tackle the issue of EBMT in depth. It gives a state-of-the-art overview of EBMT techniques and provides a coherent structure in which all aspects of EBMT are embedded. Its contributions are written by long-standing researchers in the field of MT in general, and EBMT in particular. This book can be used in graduate-level courses in machine translation and statistical NLP.

CICLing2002wasthethirdannualConferenceonIntelligenttextprocessingand Computational Linguistics (hence the name CICLing); see www.CICLing.org. It was intended to provide a balanced view of the cutting edge developments in both theoretical foundations of computational linguistics and practice of natural language text processing with its numerous applications. A feature of CICLing conferences is their wide scope that covers nearly all areas of computational linguistics and all aspects of natural language processing applications. The c- ference is a forum for dialogue between the specialists working in these two areas. This year we were honored by the presence of our invited speakers Ni- lettaCalzolari (Inst. for Computational Linguistics, Italy), Ruslan Mitkov (U.of Wolverhampton, UK), Ivan Sag (Stanford U., USA), Yorick Wilks (U. of She?eld), and Antonio Zampolli (Inst. for Computational Linguistics, Italy). They delivered excellent extended lectures and organized vivid discussions. Of 67 submissions received, after careful reviewing 48 were selected for p- sentation; of them, 35 as full papers and 13 as short papers; by 98 authors from 19countries: Spain (18 authors), Mexico (13), Japan, UK (8each), Israel (7), Germany, Italy, USA (6each), Switzerland (5), Taiwan(4), Ireland (3), A- tralia, China, CzechRep., France, Russia (2each), Bulgaria, Poland, Romania (1 each).

This book constitutes the refereed proceedings of the 6th International Colloquium on Grammatical Inference, ICGI 2002, held in Amsterdam, The Netherlands in September 2002.The 28 revised full papers presented together with 7 software descriptions were carefully reviewed and selected from 48 submissions. The papers address issues in machine learning, automata, theoretical computer science, computational linguistics, and grammar systems as well as applications in fields like natural language processing, pattern recognition, computational biology, information retrieval, text processing, and data compression.

This book constitutes the refereed proceedings of the 5th Conference of the Association for Machine Translation in the Americas, AMTA 2002, held in Tiburon, CA, USA, in October 2002.The 18 revised full technical papers, 3 user studies, and 9 system descriptions presented were carefully reviewed and selected for inclusion in the book. Among the issues addressed are hybrid translation environments, resource-limited MT, statistical word-level alignment, word formation rules, rule learning, web-based MT, translation divergences, example-based MT, data-driven MT, classification, contextual translation, the lexicon building process, commercial MT systems, speeck-to-speech translation, and language checking systems.

The conference series Logical Aspects of Computational Linguistics (LACL) aims at providing a forum for the presentation and discussion of current research in all the formal and logical aspects of computational linguistics. The LACL initiative started with a workshop held in Nancy (France) in 1995. Selected papers from this event have appeared as a special issue of the Journal of Logic Language and Information, Volume 7(4), 1998. In 1996, LACL shifted to the format of an international conference. LACL'96 and '97 were both held in Nancy (France). The proceedings appeared as volumes 1328 and 1582 of the Springer Lecture Notes in Arti cial Intelligence. This volume contains selected papers of the third international conference on Logical Aspects of Computational Linguistics (LACL'98), held in Grenoble, France, from December 14 to 16, 1998. The conference was organized by the U- versity Pierre Mend es-France (Grenoble 2) together with LORIA (Laboratoire Lorrain d'Informatique et Applications, Nancy). On the basis of 33 submitted 4-page abstracts, the Program Committee selected 19 contributions for pres- tation. In addition to the selected papers, the program featured three invited talks, by Maarten de Rijke (ILLC, Amsterdam), Makoto Kanazawa (Chiba U- versity, Japan), and Fernando Pereira (AT&T Labs). After the conference, the contributors were invited to submit a full paper for the conference proceedings.

Parsing technologies are concerned with the automatic decomposition of complex structures into their constituent parts, with structures in formal or natural languages as their main, but certainly not their only, domain of application. The focus of Recent Advances in Parsing Technology is on parsing technologies for linguistic structures, but it also contains chapters concerned with parsing two or more dimensional languages. New and improved parsing technologies are important not only for achieving better performance in terms of efficiency, robustness, coverage, etc., but also because the developments in areas related to natural language processing give rise to new requirements on parsing technologies. Ongoing research in the areas of formal and computational linguistics and artificial intelligence lead to new formalisms for the representation of linguistic knowledge, and these formalisms and their application in such areas as machine translation and language-based interfaces call for new, effective approaches to parsing. Moreover, advances in speech technology and multimedia applications cause an increasing demand for parsing technologies where language, speech, and other modalities are fully integrated. Recent Advances in Parsing Technology presents an overview of recent developments in this area with an emphasis on new approaches for parsing modern, constraint-based formalisms on stochastic approaches to parsing, and on aspects of integrating syntactic parsing in further processing.

This book constitutes the thoroughly refereed post-proceedings of the 5th International Conference on Application of Natural Language to Information Systems, NLDB 2000, held in Versailles, France, in June 2000.The 29 revised full papers presented together with two invited papers and seven posters and demonstrations have passed through two rounds of reviewing and selection. The book offers topical sections on linguistics in information design, temporal databases, word-sense disambiguation, semantic relationships in databases, semantic and contextual document retrieval, natural language generation for answering email and OLAP, NLP techniques for information retrieval, Web information retrieval, technical databases, users and interactions in Web querying, and conceptual patterns.

This book presents recent advances by leading researchers in computational modelling of language acquisition. The contributors, from departments of linguistics, cognitive science, psychology, and computer science, combine powerful computational techniques with real data and in doing so throw new light on the operations of the brain and the mind. They explore the extent to which linguistic structure is innate and/or available in a child's environment, and the degree to which language learning is inductive or deductive. They assess the explanatory power of different models. The book will appeal to all those working in language acquisition.

CICLing 2001 is the second annual Conference on Intelligent text processing and Computational Linguistics (hence the name CICLing), see www.CICLing.org. It is intended to provide a balanced view of the cutting edge developments in both theoretical foundations of computational linguistics and practice of natural language text processing with its numerous applications. A feature of the CICLing conferences is their wide scope that covers nearly all areas of computational linguistics and all aspects of natural language processing applications. The conference is a forum for dialogue between the specialists working in these two areas. This year our invited speakers were Graeme Hirst (U. Toronto, Canada), Sylvain Kahane (U. Paris 7, France), and Ruslan Mitkov (U. Wolverhampton, UK). They delivered excellent extended lectures and organized vivid discussions. A total of 72 submissions were received, all but very few of surprisingly high quality. After careful reviewing, the Program Committee selected for presentation 53 of them, 41 as full papers and 12 as short papers, by 98 authors from 19 countries: Spain (19 authors), Japan (15), USA (12), France, Mexico (9 each), Sweden (6), Canada, China, Germany, Italy, Malaysia, Russia, United Arab Emirates (3 each), Argentina (2), Bulgaria, The Netherlands, Ukraine, UK, and Uruguay (1 each).

A feature is a small modification or extension of a system which can be seen as having a self-contained functional role, such as Call Forwarding, Automatic Call back and Voice Mail in telephone services, to which users can subscribe. Feature interaction happens when one feature modifies or subverts the operation of another, and this problem has received a great deal of attention from industry and academics, especially in the field of telecommunications, where new services are constantly being developed and deployed. This volume contains refereed papers resulting from the ESPRIT FIREworks working group. The papers focus on the language constructs which have been developed describing features, and advocate a feature-oriented approach to software design including requirements specification languages and verifications logics.

This book constitutes the refereed proceedings of the 4th International Conference on Text, Speech and Dialogue, TSD 2001, held in Zelezna Ruda, Czech Republic in September 2001.
The 59 revised papers presented were carefully reviewed and selected from 117 submissions. The book presents a wealth of state-of-the-art research and development results from the field of natural language processing with emphasis on text, speech, and spoken language.

This book is based on the workshop "Information Retrieval Techniques for Speech Applications", held as part of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval in New Orleans, USA, in September 2001.The book presents 10 papers based on workshop presentations. The topics range from traditional information retrieval techniques over adaptations of these techniques to spoken documents and multimedia collections finally to new applications.

Thisvolumecontainstheproceedingsofthe4thInternationalConferenceonL- icalAspectsofComputationalLinguistics, heldJune27 29,2001inLeCroisic, France. TheLACLconferencesaimtoprovideaforumforthepresentationand discussionofcurrentresearchinalltheformalandlogicalaspectsofcompu- tionallinguistics. Theprogramcommitteeselected16papersfromsubmissionsofoverallhigh quality. Thepaperscoverawiderangeoftopics, includingcategorialgrammars, dependency grammars, formal languagetheory, grammaticalinference, hyp- intensionalsemantics, minimalism, andtype-logicalsemantics, byauthorsfrom Australia, Canada, Denmark, France, Germany, Italy, TheNetherlands, Poland, Spain, Sweden, UnitedKingdom, andUSA. M. Moortgat (Universiteit Utrecht), G. K. Pullum (University of Calif- nia, Santa Cruz), and M. Steedman (University of Edinburgh) presented - vitedtalks, on StructuralEquationsinLanguageLearning, OntheDisti- tion between Model-Theoretic and Generative-Enumerative Syntactic Fra- works, and ReconcilingType-LogicalandCombinatoryExtensionsofCate- rialGrammar respectively. Wewouldliketothankallthepeoplewhomadethis4thLACLpossible: the programcommittee, theexternalreviewers, theorganizationcommittee, andthe LACLsponsors. April2001 PhilippedeGroote &GlynMorrill Organization ProgramCommittee W. Buszkowski(Poznan) M. Kanazawa(Tokyo) R. Crouch, (PaloAlto) G. Morrill, co-chair(Barcelona) A. Dikovsky(Nantes) R. Muskens(Tilburg) M. Dymetman(Grenoble) F. Pfenning(Pittsburgh) C. Gardent(Nancy) B. Rounds, (AnnArbor) Ph. deGroote, co-chair(Nancy) E. Stabler(LosAngeles) OrganizingCommittee B. Daille(Nantes) C. Piliere, publicitychair(Nancy) A. Dikovsky(Nantes) C. Retore, chair(Rennes) A. Foret(Rennes) P. Sebillot(Rennes) E. Lebret(Rennes) AdditionalReferees J. -M. Andreoli T. HollowayKing J. Marciniec P. Blackburn M. Kandulski J. -Y. Marion C. Brun F. Lamarche G. Perrier TableofContents InvitedTalks StructuralEquationsinLanguageLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 MichaelMoortgat OntheDistinctionbetweenModel-TheoreticandGenerative-Enumerative SyntacticFrameworks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Geo?reyK. Pullum, BarbaraC. Scholz ContributedPapers AFormalDe?nitionofBottom-UpEmbeddedPush-DownAutomataand TheirTabulationTechnique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 MiguelA. Alonso, EricdelaClergerie, ManuelVilares AnAlgebraicApproachtoFrenchSentenceStructure. . . . . . . . . . . . . . . . . . . 62 DanieleBargelli, JoachimLambek DeductiveParsingofVisualLanguages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 PaoloBottoni, BerndMeyer, KimMarriott, FrancescoParisiPresicce LambekGrammarsBasedonPregroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 WojciechBuszkowski AnAlgebraicAnalysisofCliticPronounsinItalian. . . . . . . . . . . . . . . . . . . . . 110 ClaudiaCasadio, JoachimLambek Consistent Identi?cation in the Limit of Any of the Classes k-Valued Is NP-hard. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 ChristopheCostaFlor encio PolarizedNon-projectiveDependencyGrammars. . . . . . . . . . . . . . . . . . . . . . . 139 AlexanderDikovsky OnMixingDeductionandSubstitutioninLambekCategorialGrammars. . 158 AnnieForet A Framework for the Hyperintensional Semantics of Natural Language withTwoImplementations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 ChrisFox, ShalomLappin ACharacterizationofMinimalistLanguages. . . . . . . . . . . . . . . . . . . . . . . . . . . 193 HenkHarkema VIII TableofContents PartofSpeechTaggingfromaLogicalPointofView. . . . . . . . . . . . . . . . . . . 212 Torbjorn ] Lager, JoakimNivre TransformingLinearContext FreeRewritingSystemsintoMinimalist Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 JensMichaelis RecognizingHeadMovement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 EdwardP. Stabler CombinatorsforParaconsistentAttitudes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 JorgenVilladsen Combining Syntax and Pragmatic Knowledge for the Understanding of SpontaneousSpokenSentences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 JeanneVillaneau, Jean-YvesAntoine, OlivierRidoux AtomicityofSomeCategoriallyPolyvalentModi?ers . . . . . . . . . . . . . . . . . . . 296 R. Zuber AuthorIndex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 Structural Equations in Language Learning Michael Moortgat UtrechtInstituteofLinguistics OTS Trans10,3512JKUtrecht, TheNetherlands Michael. Moortgat@let. uu. nl Abstract. Incategorialsystemswitha?xedstructuralcomponent, the learningproblemcomesdownto?ndingthesolutionforasetofty- assignmentequations. Ahard-wiredstructuralcomponentisproblematic ifonewanttoaddressissuesofstructuralvariation. Ourstartingpointis atype-logicalarchitecturewithseparatemodulesforthelogicalandthe structural components of the computati