Developments in Language Theory: 27th International Conference, DLT 2023, Umea, Sweden, June 12-16, 2023, Proceedings

ISBN-13: 9783031332630 / Angielski

Frank Drewes;Mikhail Volkov

Opis

This book constitutes the refereed proceedings of the 27th International Conference on Developments in Language Theory, DLT 2023, held in Umea, Sweden, during June 12-16, 2023. The 20 full papers included in this book were carefully reviewed and selected from 32 submissions (31 regular ones and one invited).The DLT conference series provides a forum for presenting current developments informal languages and automata. Its scope is very general and includes, among others, the following topics and areas: grammars, acceptors and transducers for words; trees and graphs; relations between formal languages and artificial neural networks; algebraic theories of automata; algorithmic, combinatorial, and algebraic properties of words and languages; variable length codes; symbolic dynamics; cellular automata; groups and semigroups generated by automata; polyominoes and multidimensional patterns; decidability questions; image manipulation and compression; efficient text algorithms; relationships to cryptography, concurrency, complexity theory, and logic; bio-inspired computing; and quantum computing.

Spis treści

Transducers and the Power of Delay.- When the Map is More Exact than the Terrain.- Formal Languages and the NLP Black Box.- On Structural Tractability Parameters for Hard String Problems.- Jumping Automata over Infinite Words.- Isometric Words based on Swap and Mismatch Distance.- Set Augmented Finite Automata over Infinite Alphabets.- Fast detection of specific fragments against a set of sequences.- Weak Inverse Neighborhoods of Languages.- The exact state complexity for the composition of Root and reversal.- Bit catastrophes for the Burrows-Wheeler Transform.- The Domino problem is undecidable on every rhombus subshift.- Synchronization of Parikh Automata.- Completely Distinguishable Automata and the Set of Synchronizing Words.- Zielonka DAG Acceptance and Regular Languages over Infinite Words.- On Word Representable and Multi-Word Representable Graphs.- On the Simon's Congruence Neighborhood of Languages.- Tree-Walking-Storage Automata.- Rewriting rules for arithmetics in alternate base systems.- Synchronizing Automata with Coinciding Cycles.- Approaching Repetition Thresholds Via Local Resampling and Entropy Compression.- Languages Generated by Conjunctive Query Fragments of FC[REG].- Groups whose word problems are accepted by abelian G-automata.