Implementation and Application of Automata: 25th International Conference, CIAA 2021, Virtual Event, July 19-22, 2021, Proceedings (Theoretical Computer Science and General Issues)

This book constitutes the proceedings of the 25th International Conference on Implementation and Application of Automata, CIAA 2021, held in July 2021. Due to Covid-19 pandemic the conference was held virtually. The 13 regular papers presented in this book were carefully reviewed and selected from 20 submissions. The topics of the papers cover various fields in the application, implementation, and theory of automata and related structures. Preface Organization Abstract of Invited Lecture Polyregular Functions Contents Invited Lectures Back to the Future: A Fresh Look at Linear Temporal Logic 1 Manna and Pnueli's Safety-Progress Hierarchy 2 The Automata-Theoretic Approach to LTL Verification 3 A New Challenge 4 Closing the Circle 5 Conclusions: Back to the Future References Say No to Case Analysis: Automating the Drudgery of Case-Based Proofs 1 Introduction 2 Why We Need Cases: Some Things Are True for No Good Reason 3 Let a Computer Do the Work 4 Algorithmic Case Analysis Prevents Errors 5 Replacing a Large Number of Cases with a General Argument 6 Heuristics Plus Algorithms Can Create Proofs 7 Decision Procedures 7.1 SAT Solvers 7.2 The W-Z Method 8 Heuristics Plus Decision Procedures Provide Proofs 9 Objections References Technical Contributions Regularity Conditions for Iterated Shuffle on Commutative Regular Languages 1 Introduction 2 Preliminaries and Definitions 2.1 General Notions 2.2 Commutative Languages and the Shuffle Operation 2.3 Aperiodic and Group Languages 2.4 Commutative Aperiodic and Group Languages 3 Commutative Aperiodic and Group Languages Under Projection 4 A Class of Regular Languages Closed Under Iterated Shuffle 5 Characterizing Regularity of the Iterated Shuffle 5.1 Finite Commutative Languages 5.2 Aperiodic Commutative Languages 5.3 Decision Procedures 6 Conclusion References Memoized Regular Expressions 1 Introduction 2 Notation and Definitions 2.1 Memoized NFA 2.2 Memoized Regular Expressions 3 Generalization of Mohri's Ambiguity Results to mNFA 4 Hardness Results 5 Memoization Schemes 6 Future Work References The Commutative Closure of Shuffle Languages over Group Languages is Regular 1 Introduction 2 Preliminaries and Definitions 3 Shuffle Languages over Arbitrary Language Classes 4 The Commutative Closure on SE(G) 5 Commutative Group Languages 6 The n-times Shuffle 7 Conclusion References Efficient Enumeration of Regular Expressions for Faster Regular Expression Synthesis 1 Introduction 2 Preliminaries 3 Concise Normal Form for REs 4 RE Synthesis Algorithm 4.1 Best-First Search Algorithm 4.2 Finding Redundancy Using Positive Examples 4.3 Our Synthesis Algorithm 5 Experimental Results 5.1 Exact Enumeration of REs in Normal Form 5.2 Performance of RE Synthesis References Degrees of Restriction for Two-Dimensional Automata 1 Introduction 2 Preliminaries 3 Recognition Properties 3.1 Three-Way Recognition 3.2 Deterministic vs Nondeterministic Three-Way Recognition 3.3 Two-Way Recognition 4 Closure Properties 5 Conclusion References The Range of State Complexities of Languages Resulting from the Cascade Product—The Unary Case (Extended Abstract) 1 Introduction 2 Preliminaries 3 Results on the Cascade Product 3.1 At Least One Automaton is a Reset Automaton 3.2 Two Permutation Automata 3.3 Permutation Automata with Permutation-Reset Automata 3.4 Deterministic Finite Automata Without Restrictions 4 Conclusions References Guessing the Buffer Bound for k-Synchronizability 1 Introduction 2 Preliminaries 3 Largest Prime Reachable Exchange 4 Regularity of Reachable Exchanges 4.1 Automata of the Control States 4.2 Automata of Causal Delivery Exchanges 4.3 Language of Reachable Exchanges 5 Prime Exchanges 6 Computation of k 7 Conclusion References State Complexity of Permutation and Related Decision Problems on Alphabetical Pattern Constraints 1 Introduction 2 Preliminaries and Definitions 3 State Complexity Bound of Permutation on APCs 4 When perm(Lsimple(A)) Is a Strict Shuffle Language 5 State Complexity on General Chain Automata 6 Complexity Results 7 Conclusion References Algorithms for Probabilistic and Stochastic Subsequential Failure Transducers 1 Introduction 2 Preliminaries 3 Probabilistic Transducers 4 Conditional Probabilistic Transducers 5 Composition of Conditional Probabilistic Transducers with Probabilistic Failure Transducers 5.1 Generic Composition 5.2 Special Case Composition 6 Canonization 7 Experimental Results and Conclusion References Ambiguity Hierarchies for Weighted Tree Automata 1 Introduction 2 Preliminaries 3 Matrix Representation and Ambiguity 4 Unambiguous vs. Finitely Ambiguous 5 Finitely Vs. Polynomially Ambiguous 6 Polynomially Ambiguous Vs. Recognizable 7 Conclusion References Boolean Kernels of Context-Free Languages 1 Introduction 2 Preliminaries 3 Expressive Capability 4 (Non-)Closure Properties 5 Descriptional Complexity 6 Untouched and Open Questions References Efficient String Matching Based on a Two-Step Simulation of the Suffix Automaton 1 Introduction 2 Basic Notions and Definitions 3 The BTSM Generic Algorithm 4 The UFM Algorithm 4.1 The Algorithm 4.2 Extension to Condensed Alphabets 5 Experimental Results 6 Conclusions References Approximate Hashing for Bioinformatics 1 Introduction 2 Design of an Approximate Hash Function 2.1 Definition of the Signature 2.2 Clustering 2.3 Searching for a String Including Some Read References Author Index