Developments in Language Theory: 25th International Conference, DLT 2021, Porto, Portugal, August 16–20, 2021, Proceedings (Theoretical Computer Science and General Issues)

This book constitutes the proceedings of the 25th International Conference on Developments in Language Theory, DLT 2021, which was held in Porto, Portugal, during August 16-20, 2021. The conference took place in an hybrid format with both in-person and online participation. The 27 full papers included in these proceedings were carefully reviewed and selected from 48 submissions. The DLT conference series provides a forum for presenting current developments in formal 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; algebraic theories of automata; algorithmic, combinatorial, and algebraic properties of words and languages; variable length codes; symbolic dynamics; cellular 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; quantum computing. The book also includes 3 invited talks in full paper length. Preface Organization Abstracts of Invited Talks Computing Edit Distance Guarded Kleene Algebra with Tests Contents Invited Talks Morphic Sequences Versus Automatic Sequences 1 Introduction 2 Words, Morphisms, Sequences 3 (Purely) Morphic Sequences. Automatic Sequences 4 Comparing the Classes of Morphic and of Automatic Sequences 5 Hidden Automatic Sequences 6 How to Prove that a Sequence Is Not Automatic 7 Towards a (Partially) Automated Approach? References Parsimonious Computational Completeness 1 Introduction: A Historical Perspective 2 Nonterminal Complexity 3 Indian Connections 4 Some Weird Grammars to Conclude References Pointlike Sets and Separation: A Personal Perspective 1 Pointlike Sets: Definitions and Reformulations 2 Aperiodic Pointlikes 3 Group Pointlikes 4 Join Results and Tameness 5 Undecidability of Pointlikes 6 Transference Results 7 A New Result: Separation for Modular Quantifiers 8 Two More of My Favorite Results About Pointlike Sets 9 Some Open Problems References Regular Papers A Strong Non-overlapping Dyck Code 1 Introduction 2 Preliminary Notations 3 The Construction 4 Expansion of the Set 5 Enumeration 6 Conclusions and Further Developments References Active Learning of Sequential Transducers with Side Information About the Domain 1 Introduction 2 Preliminaries 3 Learning Transducers with Side Information 4 Merging Maps to Guess a Minimal Transducer 5 Encoding into String Equations 6 Conclusion References Compositions of Constant Weighted Extended Tree Transducers 1 Introduction 2 Preliminaries 3 Weighted Extended Tree Transducers 4 Composition 5 Decidability of Constant Property References Extremal Binary PFAs in a Černý Family 1 Introduction and Preliminaries 2 Extending the Černý Sequence to a Family 3 Reduction to a Pawn Race Problem 4 Recursive and Asymptotic Results 5 Explicit Solution of the Pawn Race Problem for Small c References Variations on the Post Correspondence Problem for Free Groups 1 Introduction 2 Free Group Preliminaries 3 Non-injective Maps: PCP(inj, inj) and GPCP(inj, inj) 4 The PCP Under Rational Constraints: PCPR 5 The GPCP and Extreme-Letter Restrictions 6 Main Results: Part 1 7 Conjugacy Inequivalent Maps: PCPCI and PCPinj+CI 7.1 Random Maps and Genericity 7.2 The GPCP for Conjugacy Inequivalent Maps 8 The Basis Problem and Stallings' Rank Problem 9 Main Results: Part 2 References Reducing Local Alphabet Size in Recognizable Picture Languages 1 Introduction 2 Preliminaries 3 Strictly Locally Testable Picture Languages 3.1 Comma-Free Picture Codes 4 Main Result 5 Conclusion A Appendix: Example1 Continued to Illustrate the Main Theorem References Properties of Graphs Specified by a Regular Language 1 Introduction 2 Notation and Preliminaries 3 Graphs 4 Graph Properties 5 Conclusion and Open Problems References Balanced-By-Construction Regularand ω-Regular Languages 1 Introduction 2 Balanced Regular Languages 3 Balanced-By-Construction Regular Languages 4 Balanced-By-Construction ω-regular Languages 4.1 Balanced !-Regular Expressions 4.2 Balanced-By-Construction ω-Regular Languages References Weighted Prefix Normal Words: Mind the Gap 1 Introduction 2 Preliminaries 3 Weighted Prefix Normal Words and Weighted Prefix Normal Form 4 Gapfree Weight Measures 5 Conclusions References Two-Way Non-uniform Finite Automata 1 Non-uniformity in Finite Automata 2 Model 3 Previous Work 4 The Power of Two-Way Advice 5 Relation to Non-uniform Space Complexity 6 Determinism Vs Non-determinism 7 Conclusion and Further Research References Integer Weighted Automata on Infinite Words 1 Introduction 2 Notation and Definitions 3 Universality Problem for Zero Acceptance 4 Different Acceptance Conditions 5 A Universal Weighted Automaton References Deciding FO2 Alternation for Automata over Finite and Infinite Words 1 Introduction 2 Preliminaries 3 Subword-Patterns 4 Hierarchies of Subword-Patterns 5 Patterns for Carton-Michel Automata References State Complexity of Projection on Languages Recognized by Permutation Automata and Commuting Letters 1 Introduction 2 General Notions 3 Orbit Sets, Projected Languages and Permutation Automata 4 Projection on Permutation Automata 5 State-Partition Automata and Normal Subgroups 6 Commuting Letters 7 Conclusion References Constrained Synchronization and Subset Synchronization Problems for Weakly Acyclic Automata 1 Introduction 2 Preliminaries 3 Constrained Synchronization of Weakly Acyclic Automata 4 Subset Synchronization Problems 5 Constraint Automata with Two States and at Most Three Letters 6 Relation to Automata with TTSPL Automaton Graphs 7 Conclusion References Lyndon Words Formalized in Isabelle/HOL 1 Introduction 2 Combinatorics on Words in Isabelle/HOL 3 Lyndon Words Formalized 3.1 Specifying the Order and Lyndon Word Definition 3.2 Formal Proofs Concerning Lyndon Words 3.3 Using the Minimal Relation 4 Final Remark References The Range of State Complexities of Languages Resulting from the Cascade Product—The General Case (Extended Abstract) 1 Introduction 2 Preliminaries 3 Results 3.1 Cascade Products Where Reset Automata are Involved 3.2 Cascade Products of Two Permutation Automata 3.3 Cascade Products with Permutation and Permutation-Reset Automata and Beyond 4 Conclusions References Second-Order Finite Automata: Expressive Power and Simple Proofs Using Automatic Structures 1 Introduction 2 Second-Order Finite Automata and Regular Classes of Languages 3 Closure Properties and Special Representations of Regular Classes of Languages 3.1 Automatic Structures 3.2 Special Representations of Regular Classes 3.3 Decidable Properties of Regular Classes 3.4 Closure Properties of the Collection of Regular Classes 4 Expressiveness of Second-Order Finite Automata 4.1 Regular and Automatic Classes of Languages 4.2 Regular and Automatic Classes of Single-Length Languages 4.3 -regular and Automatic Classes of Languages 5 Regular Classes of Languages, Ordered by Inclusion References Reversible Top-Down Syntax Analysis 1 Introduction 2 Preliminaries and Definitions 3 Computational Capacity 3.1 Lookahead Versus States 3.2 Reversibility Versus Irreversibility 4 Impact of the Lookahead Size References Symmetry Groups of Infinite Words 1 Introduction 2 Preliminaries 3 Sequences of Symmetry Groups 4 The Symmetry Groups of Arnoux-Rauzy Words 5 Symmetry Group of the Period-Doubling Word 6 Symmetry Groups of the Thue-Morse Word and the Paperfolding Word 7 Symmetry Groups of Toeplitz Words 8 Conclusions and Open Problems References Bounded Languages Described by GF(2)-grammars 1 Introduction 2 Basics 3 Subsets of a* b* 4 The Main Result for Subsets of a* b* 5 Subsets of a* b* c* 6 The Main Result 7 The Language an bn cn and Its Relatives 8 Concluding Remarks References Definability Results for Top-Down Tree Transducers 1 Introduction 2 Preliminaries 2.1 Transducers 3 From Transducers to Linear Transducers 3.1 Constructing a Linear Transducer 4 When is a Transducer Equivalent to a Homomorphism? 5 Conclusions References The Hardest LL(k) Language 1 Introduction 2 LL Grammars 3 The Hardest LL(0) Language 4 Non-existence Under Standard Definitions 5 Hardest Language for LL(k) Grammars 6 Conclusions References Upper Bounds on Distinct Maximal (Sub-)Repetitions in Compressed Strings 1 Introduction 2 Preliminaries 3 Upper Bound for Maximal -Repetitions 4 Upper Bound for Maximal -Subrepetitions 5 Tightness 6 Conclusion References Branching Frequency and Markov Entropy of Repetition-Free Languages 1 Introduction 2 Preliminaries 3 Entropy Characteristics of Prefix Trees 4 Computing Entropy 4.1 General and Markov Entropy for Regular Languages 4.2 Order-n Markov Entropy via Random Walks 5 Experimental Results 5.1 Random Walks in Power-Free Languages 5.2 Random Walks in Abelian Power-Free Languages 6 Conclusion and Future Work References A Linear-Time Simulation of Deterministic d-Limited Automata 1 Introduction 1.1 d-Limited Automata and d-DCFLs 1.2 Our Contribution 1.3 Related Results 2 Definitions 2.1 Deterministic d-Limited Automaton 2.2 Deleting DLBA 3 Linear-Time Simulation Algorithm 3.1 Simulation Algorithm References Carathéodory Extensions of Subclasses of Regular Languages 1 Introduction 2 Density and Measurability 2.1 Density of Formal Languages 2.2 C-measurability of Formal Languages 2.3 Examples of REG-measurable/immeasurable Languages 3 Closure Properties and Carathéodory's Condition 4 Carathéodory Extensions of Local Varieties 4.1 Local Varieties and an Eilenberg-Type Theorem 4.2 Extension as a Closure Operator 5 Future Work and Open Problems References Parikh Word Representable Graphs and Morphisms 1 Introduction 2 Preliminaries 3 Parikh Word Representable Graphs over a Ternary Alphabet 4 Morphisms on Words and Graphs 5 Conclusion References Author Index