Given that context-free grammars (CFG) cannot adequately describe natural languages, grammar formalisms beyond CFG that are still computationally tractable are of central interest for computational linguists. This book provides an extensive overview of the formal language landscape between CFG and PTIME, moving from Tree Adjoining Grammars to Multiple Context-Free Grammars and then to Range Concatenation Grammars while explaining available parsing techniques for these formalisms. Although familiarity with the basic notions of parsing and formal languages is helpful when reading this book, it is not a strict requirement. The presentation is supported with many illustrations and examples relating to the different formalisms and algorithms, and chapter summaries, problems and solutions. The book will be useful for students and researchers in computational linguistics and in formal language theory.

The need for a comprehensive survey-type exposition on formal languages and related mainstream areas of computer science has been evident for some years. In the early 1970s, when the book Formal Languages by the second mentioned editor appeared, it was still quite feasible to write a comprehensive book with that title and include also topics of current research interest. This would not be possible anymore. A standard-sized book on formal languages would either have to stay on a fairly low level or else be specialized and restricted to some narrow sector of the field. The setup becomes drastically different in a collection of contributions, where the best authorities in the world join forces, each of them concentrat ing on their own areas of specialization. The present three-volume Handbook constitutes such a unique collection. In these three volumes we present the current state of the art in formallanguage theory. We were most satisfied with the enthusiastic response given to our request for contributions by specialists representing various subfields. The need for a Handbook of Formal Languages was in many answers expressed in different ways: as an easily accessible his torical reference, a general source of information, an overall course-aid, and a compact collection of material for self-study. We are convinced that the final result will satisfy such various needs.

This book constitutes the refereed proceedings of the 12th International Conference on Language and Automata Theory and Applications, LATA 2018, held in Ramat Gan, Israel, in April 2018.The 20 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 58 submissions. The papers cover fields like algebraic language theory, algorithms for semi-structured data mining, algorithms on automata and words, automata and logic, automata for system analysis and programme verification, automata networks, automatic structures, codes, combinatorics on words, computational complexity, concurrency and Petri nets, data and image compression, descriptional complexity, foundations of finite state technology, foundations of XML, grammars (Chomsky hierarchy, contextual, unification, categorial, etc.), grammatical inference and algorithmic learning, graphs and graph transformation, language varieties and semigroups, language-based cryptography, mathematical and logical foundations of programming methodologies, parallel and regulated rewriting, parsing, patterns, power series, string processing algorithms, symbolic dynamics, term rewriting, transducers, trees, tree languages and tree automata, and weighted automata.

This reference discusses how automata and language theory can be used to understand solutions to solving equations in groups and word problems in groups. Examples presented include, how Fine scale complexity theory has entered group theory via these connections and how cellular automata, has been generalized into a group theoretic setting. Chapters written by experts in group theory and computer science explain these connections.

This book constitutes the refereed proceedings of the 21st International Symposium on Fundamentals of Computation Theory, FCT 2017, held in Bordeaux, France, in September 2017. The 29 revised full papers and 5 invited papers presented were carefully reviewed and selected from 99 submissions. The papers cover topics of all aspects of theoretical computer science, in particular algorithms, complexity, formal and logical methods.

This unique compendium presents the major methods of recognition and learning used in syntactic pattern recognition from the 1960s till 2018. Each method is introduced firstly in a formal way. Then, it is explained with the help of examples and its algorithms are described in a pseudocode. The survey of the applications contains more than 1,000 sources published since the 1960s. The open problems in the field, the challenges and the determinants of the future development of syntactic pattern recognition are discussed.This must-have volume provides a good read and serves as an excellent source of reference materials for researchers, academics, and postgraduate students in the fields of pattern recognition, machine perception, computer vision and artificial intelligence.

This book constitutes the refereed proceedings of the 7th International Conference on Language and Automata Theory and Applications, LATA 2013, held in Bilbao, Spain in April 2013. The 45 revised full papers presented together with 5 invited talks were carefully reviewed and selected from 97 initial submissions. The volume features contributions from both classical theory fields and application areas (bioinformatics, systems biology, language technology, artificial intelligence, etc.). Among the topics covered are algebraic language theory; algorithms for semi-structured data mining; algorithms on automata and words; automata and logic; automata for system analysis and program verification; automata, concurrency and Petri nets; automatic structures; cellular automata; combinatorics on words; computability; computational complexity; computational linguistics; data and image compression; decidability questions on words and languages; descriptional complexity; DNA and other models of bio-inspired computing; document engineering; foundations of finite state technology; foundations of XML; fuzzy and rough languages; grammars (Chomsky hierarchy, contextual, multidimensional, unification, categorial, etc.); grammars and automata architectures; grammatical inference and algorithmic learning; graphs and graph transformation; language varieties and semigroups; language-based cryptography; language-theoretic foundations of artificial intelligence and artificial life; parallel and regulated rewriting; parsing; pattern recognition; patterns and codes; power series; quantum, chemical and optical computing; semantics; string and combinatorial issues in computational biology and bioinformatics; string processing algorithms; symbolic dynamics; symbolic neural networks; term rewriting; transducers; trees, tree languages and tree automata; weighted automata.

This volume showcases the contributions that formal experimental methods can make to syntactic research in the 21st century. Syntactic theory is both a domain of study in its own right, and one component of an integrated theory of the cognitive neuroscience of language. It provides a theory of the mediation between sound and meaning, a theory of the representations constructed during sentence processing, and a theory of the end-state for language acquisition. Given the highly interactive nature of the theory of syntax, this volume defines "experimental syntax" in the broadest possible terms, exploring both formal experimental methods that have been part of the domain of syntax since its inception (i.e., acceptability judgment methods) and formal experimental methods that have arisen through the interaction of syntactic theory with the domains of acquisition, psycholinguistics, and neurolinguistics. The Oxford Handbook of Experimental Syntax brings these methods together into a single experimental syntax volume for the first time, providing high-level reviews of major experimental work, offering guidance for researchers looking to incorporate these diverse methods into their own work, and inspiring new research that will push the boundaries of the theory of syntax. It will appeal to students and scholars from the advanced undergraduate level upwards in a range of fields including syntax, acquisition, psycholinguistics, neurolinguistics, and computational linguistics.

The two-volume set LNAI 11288 and 11289 constitutes the proceedings of the 17th Mexican International Conference on Artificial Intelligence, MICAI 2018, held in Guadalajara, Mexico, in October 2018. The total of 62 papers presented in these two volumes was carefully reviewed and selected from 149 submissions. The contributions are organized in topical as follows: Part I: evolutionary and nature-inspired intelligence; machine learning; fuzzy logic and uncertainty management. Part II: knowledge representation, reasoning, and optimization; natural language processing; and robotics and computer vision.

A COMPANION TO CHOMSKY Widely considered to be one of the most important public intellectuals of our time, Noam Chomsky has revolutionized modern linguistics. His thought has had a profound impact upon the philosophy of language, mind, and science, as well as the interdisciplinary field of cognitive science which his work helped to establish. Now, in this new Companion dedicated to his substantial body of work and the range of its influence, an international assembly of prominent linguists, philosophers, and cognitive scientists reflect upon the interdisciplinary reach of Chomsky's intellectual contributions. Balancing theoretical rigor with accessibility to the non-specialist, the Companion is organized into eight sections—including the historical development of Chomsky's theories and the current state of the art, comparison with rival usage-based approaches, and the relation of his generative approach to work on linguistic processing, acquisition, semantics, pragmatics, and philosophy of language. Later chapters address Chomsky's rationalist critique of behaviorism and related empiricist approaches to psychology, as well as his insistence upon a "Galilean" methodology in cognitive science. Following a brief discussion of the relation of his work in linguistics to his work on political issues, the book concludes with an essay written by Chomsky himself, reflecting on the history and character of his work in his own words. A significant contribution to the study of Chomsky's thought, A Companion to Chomsky is an indispensable resource for philosophers, linguists, psychologists, advanced undergraduate and graduate students, and general readers with interest in Noam Chomsky's intellectual legacy as one of the great thinkers of the twentieth century.