Developments in language theory

Viac o knihe

The book features a diverse range of topics, including invited talks and regular papers. It covers various aspects of formal languages and automata theory, such as factorization forests, weighted versus probabilistic logics, and the post correspondence problem. Key discussions include the size complexity of two-way finite automata, matrix mortality, and the ? erný-Pin conjecture. The text delves into synchronizing words in one-cluster automata, majority quantifiers in regular languages, and the inclusion problem of context-free languages. It also addresses the complexity of avoiding sets of partial words and explores closures in formal languages. Additional topics include rich and periodic-like words, traces of control-flow graphs, and synchronous relations. The book extends the Lyndon-Schützenberger result to pseudoperiodic words and examines strongly regular grammars. It discusses powers of regular languages, descriptive patterns, and stateless multihead finite automata. The work also touches on crucial words for abelian powers, descriptional complexity of regular expressions, and the pumping lemma for well-nested multiple context-free languages. Further insights include game-theoretic characterizations of Boolean grammars, word equations, and limitations of equations over sets of numbers. The text also presents a weighted ?-calculus, branching-time temporal logics, and simulations by time-bounded counter machines, alongs