Developments in language theory

Viac o knihe

This collection features a range of invited and contributed papers that explore various topics in graph theory, automata, and computational models. It includes surveys on recognizable sets of graphs and hypergraphs, as well as discussions on parameterized complexity. Key concepts such as reaction systems and a Kleene theorem for communicating automata are addressed, alongside algebraic and topological models related to DNA recombinant processes. Contributions delve into regular expressions for two-dimensional languages, competence in CD grammar systems, and the correspondence between dot-depth and the polynomial hierarchy. New characterizations of languages through input reversals and iterated pushdown automata are presented, along with studies on maximum coefficients of rational formal series. The collection also examines codes defined by bio-operations, avoidable sets, and well quasi-orders, alongside a focus on ciliate bio-operations and language families. Additionally, topics such as semantic shuffles, Sturmian graphs, and firing squad synchronization problems are discussed. The power of maximal parallelism in P systems is highlighted, along with efficient algorithms for pattern matching in context-free grammars. The complexity of various automata, including left-monotone deterministic restarting automata and finite automata in two-dimensional environments, is analyzed. Other significant discussions include the role of