This book constitutes the refereed proceedings of the 6th International Conference on Natural Language Processing, GoTAL 2008, Gothenburg, Sweden, August 2008.

The 44 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 107 submissions. The papers address all current issues in computational linguistics and monolingual and multilingual intelligent language processing - theory, methods and applications.

This Lecture Notes in Computer Science (LNCS) volume contains the papers presented at the Second International Workshop on Computational Forensics (IWCF 2008), held August 7-8, 2008. It was a great honor for the organizers to host this scienti?c event at the renowned National Academy of Sciences: Keck Center in Washington, DC, USA. Computational Forensics is an emerging research domain focusing on the investigation of forensic problems using computational methods. Its primary goalis the discoveryand advancement of forensicknowledgeinvolving modeling, computer simulation, and computer-based analysis and recognition in studying and solving forensic problems. The Computational Forensics workshop series is intended as a forum for researchers and practitioners in all areas of computational and forensic sciences. This forum discusses current challenges in computer-assisted forensic investi- tions and presents recent progress and advances. IWCF addresses a broad spectrum of forensic disciplines that use computer tools for criminal investigation. This year's edition covers presentations on c- putational methods for individuality studies, computer-based3D processing and analysis of skulls and human bodies, shoe print preprocessing and analysis, n- ural language analysis and information retrieval to support law enforcement, analysis and group visualization of speech recordings, scanner and print device forensics, and computer-based questioned document and signature analysis.

The annual Text, Speech and Dialogue Conference (TSD), which originated in 1998, is now starting its second decade. So far almost 900 authors from 45 countries have contributed to the proceedings. TSD constitutes a recognizedplatform for the presen- tion and discussion of state-of-the-art technology and recent achievements in the ?eld of natural language processing. It has become an interdisciplinary forum, interweaving the themes of speech technology and language processing. The conference attracts - searchers not only from Central and Eastern Europe, but also from other parts of the world. Indeed, one of its goals has always been to bring together NLP researchers with different interests from different parts of the world and to promote their mutual co- eration. One of the ambitions of the conference is, as its title says, not only to deal with dialogue systems as such, but also to contribute to improving dialogue between researchers in the two areas of NLP, i. e., between text and speech people. In our view, the TSD conference was successful in this respect in 2008 as well. This volume contains the proceedings of the 11th TSD conference, held in Brno, Czech Republic in September 2008. Following the review process, 79 papers were - ceptedoutof173submitted, anacceptancerateof45. 7%.

TheseriesofworkshopsonMachineLearningforMultimodalInteraction(MLMI) celebratesthisyearits?fthanniversary.Onthisoccasion, anumberofinnovations havebeenintroducedin the reviewingandpublicationprocedures, while keeping the focus onthe samescienti?c topics. For the ?rst time, the reviewing process has been adapted in order to p- parethe proceedings in time for the workshop, held on September 8-10,2008, in Utrecht, The Netherlands. The 47 submissions received by the Program C- mittee were ?rst reviewed by three PC members each, and then advocated by an Area Chair. Overall, 12 oral presentations (ca. 25% of all submissions) and 15 poster presentations were selected. Authors were given one month to revise their papers according to the reviews, and the ?nal versions were brie?y checked by the two Program Co-chairs. Both types of presentation have been give equal space in the present proceedings. The 32 papers gathered in this volume cover a wide range of topics - lated to human-human communication modeling and processing, as well as to human-computer interaction, using several communication modalities. A sign- icant number of papers focus on the analysis of non-verbal communication cues, such as the expression of emotions, laughter, face turning, or gestures, which demonstrates a growing interest for social signal processing. Yet, another large set of papers targets the analysis of communicative content, with a focus on the abstractionofinformationfrommeetingsintheformofsummaries, actionitems, ordialogueacts.OthertopicspresentedatMLMI2008includeaudio-visualscene analysis, speech processing, interactive systems and applica

This book constitutes the refereed proceedings of the 22nd Conference on Artificial Intelligence, Canadian AI 2009, held in Kelowna, Canada, in May 2009.

The 15 revised full papers presented together with 19 revised short papers, 8 papers from the graduate student symposium and the abstracts of 3 keynote presentations were carefully reviewed and selected from 63 submissions. The papers present original high-quality research in all areas of Artificial Intelligence and apply historical AI techniques to modern problem domains as well as recent techniques to historical problem settings.

This volume contains the papers presented at NLDB 2008, the 13th Inter- tional Conference on Natural Language and Information Systems, held June 25-27,2008.It also containssome of the best researchproposalsas submitted to theNLDB2008doctoralsymposiumheldonJune24,2008.Theprogrammealso includes three invited talks covering the main perspectives of the application of naturallanguageto informationsystems: the wayhumansprocess, communicate and understand natural language, what are the implications and challenges - wardssemanticsearchforthenewWebgeneration, hownaturallanguageapplies to the well-established database way of querying as a means to unlock data and information for end users. We received 68 papers as regular papers for the main conference and 14 short papers for the doctoral symposium. Each paper for the main conference was assigned four reviewers based on the preferences expressed by the Program Committee members. We ensured that every paper had at least two reviewers that expressedinterest in reviewing it or indicated that they could reviewit. We ensured that each paper got at least three reviews. As a result, only 10% of the papers were reviewed by three reviewers. The Conference Chair and the two Program Committee Co-chairs acted as Meta-Reviewers.Eachofthemtookroughly1/3ofthepapers(obviouslyrespe- ing con?icts of interest), for which s/he was responsible. This included studying the reviews, launching discussions and asking for clari?cations whenever nec- sary, as well as studying the papers whenever a need for an informed additional opinion arose or when the reviewers' notes did not allow for a decision.

The IEEE Tutorialand ResearchWorkshopon Perceptionand InteractiveTe- nologies for Multimodal Dialogue Systems (PIT 2008) is the continuation of a successful series of workshops that started with an ISCA Tutorial and Research WorkshoponMultimodalDialogueSystemsin1999.Thisworkshopwasfollowed by a second one focusing on mobile dialogue systems (IDS 2002), a third one exploring the role of a?ect in dialogue (ADS 2004), and a fourth one focusing on perceptive interfaces (PIT 2006). Like its predecessors, PIT 2008 took place at Kloster Irsee in Bavaria. Due to the increasing interest in perceptive interfaces, we decided to hold a follow-up workshop on the themes discussed at PIT 2006, but encouraged aboveallpaperswithafocusonperceptioninmultimodaldialoguesystems.PIT 2008received37 paperscoveringthe following topics (1) multimodal and spoken dialogue systems, (2) classi?cation of dialogue acts and sound, (3) recognitionof eye gaze, head poses, mimics and speech aswellascombinationsofmodalities, (4) vocal emotion recognition, (5) human-like and social dialogue systems and (6) evaluation methods for multimodal dialogue systems. Noteworthy was the strong participation from industry at PIT 2008. Indeed, 17 of the accepted 37 papers come from industrial organizations or were written in collaboration with them. Wewouldliketothankallauthorsforthe e?ortthey madewiththeirsubm- sions, and the Program Committee - nearly 50 distinguished researchers from industry and academia - who worked very hard to meet tight deadlines and selected the best contributions for the ?nal program. Special thanks goes to our invited speaker, Anton Batliner from Friedrich-Alexander-Universit] atErlangen- N] urnberg."

A practical introduction to essential topics at the core of computer science

Automata, formal language, and complexity theory are central to the understanding of computer science. This book provides, in an accessible, practically oriented style, a thorough grounding in these topics for practitioners and students on all levels.

Based on the authors’ belief that the problem-solving approach is the most effective, Problem Solving in Automata, Languages, and Complexity collects a rich variety of worked examples, questions, and exercises designed to ensure understanding and mastery of the subject matter. Building from the fundamentals for beginning engineers to more advanced concepts, the book examines the most common topics in the field, including:

• Finite-state automata
• Context-free grammars
• Turing machines
• Recursive and recursively enumerable languages
• Computability theory
• Complexity classes
• NP-completeness

Focused, practical, and versatile, Problem Solving in Automata, Languages, and Complexity gives students and engineers a solid grounding in essential areas in computer science.

The papers contained in this volume were presented at the 19th Annual S- posium on Combinatorial Pattern Matching (CPM 2008) held at the University of Pisa, Italy, June 18-20, 2008. All the papers presented at the conference are originalresearchcontributions on computational pattern matching and analysis. They were selected from 78 submissions. Each submission was reviewed by at least three reviewers. The committee decided to accept 25 papers. The programme also includes three invited talks by Daniel M. Gus?eld from the University of California, Davis, USA, J. Ian Munro from the University of Waterloo, Canada, and Prabhakar Raghavan from Yahoo! Research, USA. The objective of the annual CPM meetings is to provide an international forum for research in combinatorial pattern matching and related applications. It addresses issues of searching and matching strings and more complicated p- terns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivialcombinatorialproperties of suchstructures and to exploit these properties in order to either achieve superior performance for the cor- sponding computational problems or pinpoint conditions under which searches cannotbeperformede?ciently. Themeeting also dealswith problems incom- tational biology, data compression, data mining, coding, information retrieval, natural language processing and pattern recognition.

This book constitutes the refereed proceedings of the 10th International Conference on Text, Speech and Dialogue, TSD 2007, held in Pilsen, Czech Republic, in September 2007. The 80 revised full papers presented in this volume cover a wealth of state-of-the-art research results in the field of natural language processing with an emphasis on text, speech, and spoken dialogue ranging from theoretical and methodological issues to applications in various fields.

This book constitutes the refereed proceedings of the 8th International Conference on Computational Linguistics and Intelligent Text Processing, CICLing 2007, held in Mexico City, Mexico in February 2007.

The 53 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 179 submissions. The papers cover all current issues in computational linguistics research and present intelligent text processing applications. The papers are organized in topical sections on: lexical resources, corpus-based knowledge acquisition, morphology and part-of-speech tagging, named entity recognition, temporal expression treatment, word segmentation, sentence splitting, chunking, grammar formalisms and syntax, word sense disambiguation and discrimination, semantics, humor and emotion analysis; machine translation, natural language generation, intelligent tutoring systems, information retrieval, question answering, text summarization and information extraction, text categorization and clustering, and spell-checking.

This book constitutes the thoroughly refereed post-proceedings of the 5th International Workshop on Finite-State Methods in Natural Language Processing, FSMNLP 2005, held in Helsinki, Finland in September 2005.

The 24 revised full papers and 7 revised poster papers presented together with 2 invited contributions and the abstracts of 6 software demos were selected from 50 submissions and have gone through two rounds of reviewing and improvement. The papers address various topics in morphology, optimality theory, some special FSM families, weighted FSM algorithms, FSM representations, exploration, ordered structures, and surface parsing.

This book constitutes the thoroughly refereed proceedings of the 5th International Symposium on Chinese Spoken Language Processing, ISCSLP 2006, held in Singapore in December 2006, co-located with ICCPOL 2006, the 21st International Conference on Computer Processing of Oriental Languages. Coverage includes speech science, acoustic modeling for automatic speech recognition, speech data mining, and machine translation of speech.

This book constitutes the thoroughly refereed proceedings of the 21st International Conference on Computer Processing of Oriental Languages, ICCPOL 2006, held in Singapore in December 2006, colocated with ISCSLP 2006, the 5th International Symposium on Chinese Spoken Language Processing.

The 36 revised full papers and 20 revised short papers presented were carefully reviewed and selected from 169 submissions. The papers are organized in topical sections on information retrieval, document classification, questions and answers, summarization, machine translation, word segmentation, chunking, abbreviation expansion, writing-system issues, parsing, semantics, and lexical resources.

As well as conveying a message in words and sounds, the speech signal carries information about the speaker's own anatomy, physiology, linguistic experience and mental state. These speaker characteristics are found in speech at all levels of description: from the spectral information in the sounds to the choice of words and utterances themselves.

This two volume set, LNAI 4343 and LNAI 4441, constitutes a state-of-the-art survey for the field of speaker classification. It approaches the following questions: What characteristics of the speaker become manifest in his or her voice and speaking behavior? Which of them can be inferred from analyzing the acoustic realizations? What can this information be used for? Which methods are the most suitable for diversified problems in this area of research? How should the quality of the results be evaluated?

The 22 articles of the second volume comprise a number of selected self-contained papers on research projects in the field of speaker classification. These include among other things a report on a gender recognition system; a study on emotion recognition; a presentation of a text-dependent speaker verification system; an account of the analysis of both speaker and verbal content information - as well as studies on accent identification.

This book constitutes the refereed proceedings of the 11th International Conference on Applications of Natural Language to Information Systems, NLDB 2006, held in Klagenfurt, Austria in May/June 2006 as part of UNISCON 2006. The book presents 17 revised full papers and 5 revised short papers, organized in topical sections on concepts extraction and ontology, ontologies and task repository utilization, query processing, information retrieval and dialog processing, and NLP techniques.

This book constitutes the thoroughly refereed post-proceedings of the Second International Workshop on Machine Learning for Multimodal Interaction held in July 2005. The 38 revised full papers presented together with two invited papers were carefully selected during two rounds of reviewing and revision. The papers are organized in topical sections on multimodal processing, HCI and applications, discourse and dialogue, emotion, visual processing, speech and audio processing, and NIST meeting recognition evaluation.

This book constitutes the refereed proceedings of the 5th International Conference on Natural Language Processing, FinTAL 2006, held in Turku, Finland in August 2006. The book presents 72 revised full papers together with 1 invited talk and the extended abstracts of 2 invited keynote addresses. The papers address all current issues in computational linguistics and monolingual and multilingual intelligent language processing - theory, methods and applications.

Refereed postproceedings of the International Conference on Non-Linear Speech Processing, NOLISP 2005. The 30 revised full papers presented together with one keynote speech and 2 invited talks were carefully reviewed and selected from numerous submissions for inclusion in the book. The papers are organized in topical sections on speaker recognition, speech analysis, voice pathologies, speech recognition, speech enhancement, and applications.

Here are the refereed proceedings of the 9th International Conference on Text, Speech and Dialogue, TSD 2006. The book presents 87 revised full papers together with 2 invited papers reviewing state-of-the-art research in the field of natural language processing. Coverage ranges from theoretical and methodological issues to applications with special focus on corpora, texts and transcription, speech analysis, recognition and synthesis, as well as their intertwining within NL dialogue systems.

The Theme of IJCNLP 2005: "NLP with Kimchee," a Conference with a Unique Flavor Welcometo IJCNLP 2005, thesecondannualconferenceof theAsian Federation ofNaturalLanguageProcessing(AFNLP). Followingthesuccessofthe?rstc- ference held in the beautiful cityof Sanya, Hainan Island, China, in March2004, IJCNLP 2005 is held in yet another attractive Asian resort, namely Jeju Island in Korea, on October 11-13, 2005 - the ideal place and season for appreciating mugunghwa, the rose of Sharon, and the national ?ower of Korea. On behalf of the Program Committee, we are excited to present these p- ceedings, which collect together the papers accepted for oral presentation at the conference. We received 289 submissions in total, from 32 economies all over the world: 77% from Asia, 11% from Europe, 0.3% from Africa, 1.7% from Australasia and 10% from North America. We are delighted to report that the popularity of IJCNLP has signi?cantly increased this year, with an increase of 37% from the 211 submissions from 16 economies and 3 continents received for IJCNLP 2004. With such a large number of submissions, the paper selection process was not easy. With the very considerable assistance of our 12 area chairs - Claire Gardent, Jamie Henderson, Chu-Ren Huang, Kentaro Inui, GaryLee, Kim-Teng Lua, Helen Meng, Diego Moll a, Jian-Yun Nie, Dragomir Radev, Manfred Stede, andMing Zhou- andthe 133internationalreviewers,90papers(31%)were- cepted for oral presentation and 62 papers (21%) were recommended as posters."

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, appr

The ?fth campaign of the Cross-Language Evaluation Forum (CLEF) for Eu- pean languages was held from January to September 2004. Participation in the CLEF campaigns has increased each year and CLEF 2004 was no exception: 55 groups submitted results for one or more of the di?erent tracks compared with 42 groups in the previous year. CLEF 2004 also marked a breaking point with respect to previous campaigns. The focus was no longer mainly concentrated on multilingual document retrieval as in previous years but was diversi?ed to include di?erent kinds of text retrieval across languages (e. g. , exact answers in the question-answering track) and retrieval on di?erent kinds of media (i. e. , not just plain text but collections containing image and speech as well). In ad- tion, increasing attention was given to issues that regard system usability and user satisfaction with tasks to measure the e?ectiveness of interactive systems or system components being included in both the cross-language question - swering and image retrieval tasks with the collaboration of the coordinators of the interactive track. The campaign culminated in a two-and-a-half-day workshop held in Bath, UK, 15-17 September, immediately following the 8th European Conference on Digital Libraries. The workshop was attended by nearly 100 researchers and s- tem developers.

This volume contains invited and contributed papers presented at the 9th International Summer School "Neural Nets E.R. Caianiello" on Nonlinear Speech Processing: Al- rithms and Analysis, held in Vietri sul Mare, Salerno, Italy, during September 13-18, 2004. The aim of this book is to provide primarily high-level tutorial coverage of the ?elds related to nonlinear methods for speech processing and analysis, including new approaches aimed at improving speech applications. Fourteen surveys are offered by specialists in the ?eld. Consequently, the volume may be used as a reference book on nonlinear methods for speech processing and an- ysis. Also included are ?fteen papers that present original contributions in the ?eld and complete the tutorials. The volume is divided into ?ve sections: Dealing with Nonlinearities in Speech S- nal, Acoustic-to-Articulatory Modeling of Speech Phenomena, Data Driven and Speech Processing Algorithms, Algorithms and Models Based on Speech Perception Mec- nisms, and Task-Oriented Speech Applications. Dealing with Nonlinearities in Speech Signals is an introductory section where n- linear aspects of the speech signal are introduced from three different points of view. The section includes three papers. The ?rst paper, authored by Anna Esposito and Maria Marinaro, is an attempt to introduce the concept of nonlinearity revising several nonl- ear phenomena observed in the acoustics, the production and the perception of speech. Also discussed is the engineering endeavor to model these phenomena.

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