Developments in Language Theory : 26th International Conference, DLT 2022, Tampa, FL, USA, May 9–13, 2022, Proceedings

This book constitutes the proceedings of the 26th International Conference on Developments in Language Theory, DLT 2022, which was held in Tampa, FL, USA, during May, 2022. The conference took place in an hybrid format with both in-person and online participation. The 21 full papers included in these proceedings were carefully reviewed and selected from 32 submissions. The DLT conference series provides a forum for presenting current developments in formal languages and automata. Preface Organization Abstracts of Invited Talks Algebraic Methods for Periodicity in Multidimensional Symbolic Dynamics Non-deterministic Transducers Origin-Equivalence for Macro Tree Transducers Contents Invited Talks Can Formal Languages Help Pangenomics to Represent and Analyze Multiple Genomes? 1 Introduction 2 Preliminaries 3 Lyndon Words and Lyndon-Based Factorization 3.1 Some Applications: Representing and Querying Read Sequences 4 Sample Specific Strings and Structural Variations in Human Genome 5 Open Problems References Word Equations in the Context of String Solving 1 Introduction 2 String Solving 3 A Closer Look at Solution-Sets 3.1 Parametric Solutions 3.2 Graph Representations of Solution-Sets 3.3 Nielsen Transformations 3.4 Restricted Word Equations 4 Conclusions References A Survey on Delegated Computation 1 Introduction 2 Model and Definitions 3 Delegated Computation of Ring Multiplication 3.1 Algebraic Setting 3.2 An Example Protocol 3.3 Related Work 4 Delegated Computation of Group Exponentiation 4.1 Algebraic Setting and Preliminaries 4.2 An Example Protocol 4.3 Related Work 5 Delegation of Pairings 5.1 Algebraic Setting 5.2 An Example Protocol 5.3 Related Work 6 Conclusions and Directions for Future Research References Regular Papers Checking Regular Invariance Under Tightly-Controlled String Modifications 1 Introduction 2 Preliminaries 3 Model 4 Complexity of the Invariance-Checking Problem 5 Invariance-Checking : Special Case 6 Conclusions and Future Work References Deciding Atomicity of Subword-Closed Languages 1 Introduction 2 Main Result 3 Concluding Remarks and Open Problems References Prefix Palindromic Length of the Sierpinski Word 1 Introduction 2 Definitions, Notation, Known Results 3 Auxiliary Functions qj(n) 4 Function q and Its First Differences 5 Difference Between p(n) and q(n) 6 First Differences of p(n) References Preservation of Normality by Unambiguous Transducers 1 Introduction 2 Basic Definitions 2.1 Normality 2.2 Automata and Transducers 2.3 Weighted Automata 3 Results 4 Markov Chain of an Unambiguous Automaton 5 Sketches of Proofs 6 Conclusion References A Full Characterization of Bertrand Numeration Systems 1 Introduction 2 Basic Notation 3 Characterization of Bertrand Numeration Systems 4 Linear Bertrand Numeration Systems 5 Lexicographically Greastest Words of Each Length 6 The Non-canonical -shift References On the Decidability of Infix Inclusion Problem 1 Introduction 2 Preliminaries 3 IIP on Finite Languages 4 IIP on Infinite Languages 5 Conclusions References Column Representation of Sturmian Words in Cellular Automata 1 Introduction 2 Preliminaries 2.1 Words 2.2 Continued Fraction Expansion 2.3 Standard Sequences and Directed Sequences 3 Cellular Automata 4 Construction of Numbers 5 Construction of Prefixes 6 Conclusions References Logarithmic Equal-Letter Runs for BWT of Purely Morphic Words 1 Introduction 2 Preliminaries 3 BWT-Highly Compressible Morphisms 4 Upper and Lower Bounds for rbwt 4.1 Combinatorial Structure of Binary Morphisms 4.2 Logarithmic Bounds for rbwt in Case of Binary Morphisms 5 Conclusions and Further Work References On Perfect Coverings of Two-Dimensional Grids 1 Introduction and Preliminaries 2 Line Polynomial Factors 3 Perfect Coverings 3.1 Infinite Grids 3.2 General Convex Neighborhoods 4 Algorithmic Aspects References Automata-Theoretical Regularity Characterizations for the Iterated Shuffle on Commutative Regular Languages 1 Introduction 2 Preliminaries 3 Type I Languages 4 Type II Languages 5 Automata-Theoretical Characterizations 6 Decision Problems 7 Conclusion References On the Complexity of Decision Problems for Counter Machines with Applications to Coding Theory 1 Introduction 2 Preliminaries 3 Complexity of Decision Problems for Restrictions of 2NCM 3.1 The Non-emptiness Problem 3.2 Other Decision Problems 4 Complexity of k-Infix-Freeness of Languages 5 Generalizations of k-Infix-Freeness References Visit-Bounded Stack Automata 1 Introduction 2 Preliminaries 2.1 Stack Automata 3 Visit-Bounded Automata 4 Semilinearity 5 Other Expensive Instruction Sets References Well Quasi-Orders Arising from Finite Ordered Semigroups 1 Introduction 2 Preliminaries 3 What Makes an Ordered Semigroup Congenial 4 Effective Characterization of the Class C 5 Other Necessary and Sufficient Conditions 6 Conclusion References The Billaud Conjecture for 69640972 86418188 = 4, and Beyond 1 Introduction 2 Preliminaries 3 Languages of Fixed Points and Their Parents 4 A `Blueprint' for a Billaud Conjecture Proof for Fixed 5 A Proof for the Billaud Conjecture for 69640972 86418188 = 4 References Weighted Tree Automata with Constraints 1 Introduction 2 Preliminaries 3 Weighted Tree Grammars with Constraints 4 Closure Properties 5 Towards HOM Problem References Performing Regular Operations with 1-Limited Automata 1 Introduction 2 Preliminaries 3 Product and Kleene Star 3.1 Simulations of Operations on 3.2 Simulations of Operations on 4 Union, Intersection, and Complementation 4.1 Simulations of Operations on 4.2 Simulations of Operations on 5 Reversal References Binomial Complexities and Parikh-Collinear Morphisms 1 Introduction 1.1 Binomial Coefficients and Complexity Functions 1.2 Questions Addressed in This Paper 2 Several Answers to Question A 3 An Interlude: Parikh-Collinear Morphisms 3.1 A Characterization of Parikh-Collinear Morphisms 3.2 Proof of Theorem 10 4 Binomial Properties of the Thue–Morse Morphism 4.1 The First k Binomial Complexities 4.2 The (k+1)-Binomial Complexity 5 Answer to Question B and Beyond References Rational Index of Languages with Bounded Dimension of Parse Trees 1 Introduction 2 Definitions 3 Upper Bound on the Rational Index 4 Lower Bound on the Rational Index 5 Rational Indices for Some Language Families 6 Conclusion and Open Problems References Measuring Power of Locally Testable Languages 1 Introduction 2 Preliminaries 2.1 Density of Formal Languages 2.2 Measurability of Formal Languages 2.3 Fragments of Star-Free Languages 3 Measuring Power of Locally Testable Languages 4 Measuring Power of Alphabet and Piecewise Testable Languages 5 Summary and Future Work References The Power Word Problem in Graph Products 1 Introduction 2 Preliminaries 3 Cyclic Normal Forms and Conjugacy 4 The Power Word Problem in Graph Products References On One-Counter Positive Cones of Free Groups 1 Introduction 2 One-Counter Languages and Bi-infinite Words 3 Free Groups and Bi-infinite Words 4 The Space of Orders Defined by Spaced Words References Kolmogorov Complexity Descriptions of the Exquisite Behaviors of Advised Deterministic Pushdown Automata 1 Background and Our Challenges 1.1 Kolmogorov Complexity Approaches to Formal Languages 1.2 Advice-Aided Languages and Pumping Lemmas 1.3 Overview of Main Contributions 2 Preparation: Notions and Notation 2.1 Numbers, Alphabets, Languages, etc. 2.2 One-Way Deterministic Pushdown Automata 2.3 Kolmogorov Complexity Primer 3 Advised Computation 4 Kolmogorov Complexity Approach 4.1 Key Lemma – KC-DCFL/n Lemma 4.2 Applications of the KC-DCFL/n Lemma References Author Index