Developments in Language Theory : 27th International Conference, DLT 2023, Umeå, Sweden, June 12–16, 2023, Proceedings

This book constitutes the refereed proceedings of the 27th International Conference on Developments in Language Theory, DLT 2023, held in Umeå, 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. Preface Organization Invited Papers Transducers and the Power of Delay When the Map is More Exact than the Terrain On Structural Tractability Parameters for Hard String Problems Contents Formal Languages and the NLP Black Box 1 Introduction 2 RNNs 2.1 LSTMs Can Count, Other RNNs Cannot 2.2 Saturated RNNs as a Model of Practical RNNs 2.3 Summary and Open Questions 3 Transformers 3.1 Transformers with Hard Attention 3.2 Transformers with Soft Attention 3.3 Logics and Programming Languages for Expressing Transformer Computation 3.4 Summary and Open Questions 4 Conclusion 5 Resources References Jumping Automata over Infinite Words 1 Introduction 2 Preliminaries and Definitions 3 Jumping Languages 3.1 Jumping Languages and Masked Semilinear Sets 3.2 Jumping Languages – Closure Properties 3.3 Jumping Languages - Algorithmic Properties 4 Fixed-Window Jumping Languages 5 Existential-Window Jumping Languages 6 Future Research References Isometric Words Based on Swap and Mismatch Distance 1 Introduction 2 Preliminaries 3 Tilde-Distance and Tilde-Isometric Words 4 Tilde-Isometric Words and Tilde-Error Overlaps 5 Construction of Tilde-Witnesses References Set Augmented Finite Automata over Infinite Alphabets 1 Introduction 2 Preliminaries 3 Set Augmented Finite Automata 4 Decision Problems and Closure Properties 4.1 Nonemptiness and Membership 4.2 Closure Properties 5 Expressiveness 6 Conclusion References Fast Detection of Specific Fragments Against a Set of Sequences 1 Introduction 2 Background: Directed Acyclic Word Graph 3 Computing the Set of T-specific Words 4 Computing Occurrences of Target-Specific Factors: The T-specific table References Weak Inverse Neighborhoods of Languages 1 Introduction 2 Preliminaries 3 Edit-Distance Neighborhoods and Edit-Distance Interiors 4 Closure Properties on Edit-Distance Interiors 5 Edit-Distance Interiors of Regular or Context-Free Languages 6 Conclusions References The Exact State Complexity for the Composition of Root and Reversal 1 Introduction 2 Preliminaries 3 An Automaton Accepting the Root-Reversal of a Regular Language 4 State Complexity of Root-Reversal References Bit Catastrophes for the Burrows-Wheeler Transform 1 Introduction 2 Preliminaries 3 Increasing r by a (logn)-Factor 3.1 Inserting a Character 3.2 Deleting a Character 3.3 Substituting a Character 4 Additive (n) Factor 5 Bit Catastrophes for r$ 6 Conclusion References The Domino Problem Is Undecidable on Every Rhombus Subshift 1 Introduction 2 Definitions 2.1 Geometrical Tiling Spaces 2.2 Symbolic-geometrical Tiling Spaces 2.3 Computability and Decidability 2.4 Domino Problems 3 Complexity of the Domino Problem on Rhombus Subshifts 3.1 The Domino Problem on Effective Rhombus Subshifts Is 10 3.2 The Domino Problem on Shape Uniformly Recurrent Subshifts Is 10-hard 3.3 The Domino Problem on Any Rhombus Subshift Is 10-hard References Synchronization of Parikh Automata 1 Introduction 2 Preliminaries 3 Notions of Synchronization 4 Decidability 5 Deterministic Complete Parikh Automata on Letters 5.1 Simplifying the Semilinear Set 5.2 Ternary Alphabet 5.3 Binary Alphabet 5.4 Unary Alphabet 6 Conclusion References Completely Distinguishable Automata and the Set of Synchronizing Words 1 Preliminaries 2 Completely Distinguishable Automata 2.1 Complete Distinguishability 2.2 Sync-Maximal Automata 3 SI-Automata 3.1 The Rystsov Graph and Related Constructions 3.2 Application to SI-Automata 4 Decision Problems 5 Conclusion References Zielonka DAG Acceptance and Regular Languages over Infinite Words 1 Introduction 1.1 Zielonka-DAG Acceptance and Extension Acceptance 1.2 Other Acceptance Types 2 Preliminaries 2.1 Automaton Structures 2.2 Acceptance Conditions 3 Extension Acceptance 4 Comparison to Other Acceptance Types 4.1 Zielonka DAG Acceptance 4.2 Relative Succinctness 4.3 Color-Muller Acceptance 5 Zielonka DAG and Extension Automata 5.1 Boolean Closure 5.2 Decision Problems 5.3 Non-deterministic Extension Automata References On Word-Representable and Multi-word-Representable Graphs 1 Introduction 2 Mathematical Preliminaries 2.1 Word-Representable Graphs 2.2 Semi-transitive Orientation 3 A Novel Decidability Proof of Word-Representable Graphs 4 Multi-Word-Representability 4.1 Colourability and Multi-word-Representability 4.2 Graphs Representable by 2 Words 5 Conclusion and Open Problems References On the Simon's Congruence Neighborhood of Languages 1 Introduction 2 Preliminaries 3 Simon's Congruences and Their Neighborhoods 3.1 Finding Maximal k-Congruence of Two Languages 3.2 Determining the Equivalence and Containment of Two Simon's Congruence Neighborhoods 4 Conclusions References Tree-Walking-Storage Automata 1 Introduction 2 Definitions and Preliminaries 3 Computational Capacity of General Deterministic Tree-Walking-Storage Automata 4 Non-Erasing Tree-Walking-Storage Versus Non-Erasing Stack 5 A Non-Erasing Polynomial-Time Tree is Better Than Any Stack References Rewriting Rules for Arithmetics in Alternate Base Systems 1 Introduction 2 Preliminaries 2.1 Finiteness in Cantor Real Bases 2.2 Admissibility 2.3 Alternate Bases 3 Main Results 4 Sufficient Condition References Synchronizing Automata with Coinciding Cycles 1 Introduction 2 Preliminaries 3 Upper Bound 4 Worst-Case Lower Bound 5 Conclusions and Further Work References Approaching Repetition Thresholds via Local Resampling and Entropy Compression 1 Introduction 2 Definitions and Notation 3 Logs Compression and Repetition Thresholds 4 Constructing Threshold Words: Experimental Results References Languages Generated by Conjunctive Query Fragments of FC[REG] 1 Introduction 2 Preliminaries 2.1 Patterns 2.2 FC Conjunctive Queries 3 Expressive Power and Closure Properties 3.1 Connection to Related Models 4 Decision Problems 5 Descriptional Complexity 6 Conclusions References Groups Whose Word Problems Are Accepted by Abelian G-Automata 1 Introduction 2 Preliminaries 2.1 Words, Subwords, and Scattered Subwords 2.2 Word Problem for Groups 2.3 Graphs and Paths 2.4 G-Automata 3 Equivalence of Theorem 3 and Theorem 2 4 Proof of Theorem 3 4.1 Minimal Accepting Paths 4.2 Pumpable Paths and the Monoids M(mu,p) 4.3 Group Homomorphisms f_{mu,p} from G(mu,p) onto H(mu,p) 4.4 One of the H(mu,p)'s has Finite Index in H 5 Conclusion References Author Index