Language and Automata Theory and Applications: 15th International Conference, LATA 2021, Milan, Italy, March 1–5, 2021, Proceedings (Theoretical Computer Science and General Issues)

This book constitutes the proceedings of the 15th International Conference on Language and Automata Theory and Applications, LATA 2021, held in Milan, Italy, in March 2021. The 26 full papers presented in this volume were carefully reviewed and selected from 52 submissions. They were organized in topical sections named: algebraic structures; automata; complexity; learning; logics and languages; trees and graphs; and words and strings. Preface Organization Contents Algebraic Structures On Language Varieties Without Boolean Operations 1 Introduction 2 Lattice Bimodules 3 Pseudovarieties of Reduced Lattice Bimodules 4 Basic Varieties of Regular Languages 5 Duality and the Basic Variety Theorem 6 Quantum Finite Automata 7 Conclusion and Future Work References Partially Directed Animals with a Bounded Number of Holes 1 Introduction 2 Notation and Preliminaries 3 A Dynamical System for HPDAk 4 Exhaustive Generation 4.1 Data Structure 4.2 Complexity 5 Conclusion and Future Works References On the Computational Power of Programs over BA2 Monoid 1 Introduction 2 Preliminaries 3 PLP for (Restricted) Programs over BA2 3.1 PLP for Non-nullable Programs 3.2 PLP for (Restricted) Nullable Programs 4 Limitations of Programs over BA2 Monoid References Automata Location Based Automata for Expressions with Shuffle 1 Introduction 2 Preliminaries 3 A Location Based Position Automaton 4 APD() as a Quotient of APOS() 5 APOS() Vs. Apos() 6 Relation with Other Constructions References Succinct Representations for (Non)Deterministic Finite Automata 1 Introduction 1.1 Our Main Results and Paper Organization 2 Succinct Representations for DFA and NFA 2.1 Succinct Encoding of DFA 2.2 Reducing the Space Further 2.3 Succinct Data Structure for DFA 3 Concluding Remarks References Optimising Attractor Computation in Boolean Automata Networks 1 Introduction 2 Definitions 2.1 Boolean Functions 2.2 Boolean Automata Networks and Acyclic Modules 2.3 Promise Problems and Classes of Function Problems 3 From BANs to AMs 4 Output Functions 5 Optimal Acyclic Module Synthesis 6 Final Wiring and Analysis 7 Conclusion References On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous Finite Automata 1 Introduction 2 Definitions 3 Upper Bound 4 Lower Bound 5 Estimating the Rank of the Matrix for Permutations 6 Conclusion References Complexity Deciding Non-emptiness of Hypergraph Languages Generated by Connection-preserving Fusion Grammars is NP-complete 1 Introduction 2 Preliminaries 3 Fusion Grammars 4 A Linear-Time Reduction of the Non-emptiness Problem of Connection-preserving Fusion Grammars to the Non-emptiness Problem of Vector Fusion Grammars 5 A Polynomial-Time Equivalence of the Non-emptiness Problem for Vector Fusion Grammars and Solvability of a Variant of Integer Linear Programming 6 Complexity-Theoretic Implications of the Reductions 7 Conclusion References On the Power of Nondeterministic Circuits and Co-Nondeterministic Circuits 1 Introduction 2 Preliminaries 2.1 Circuits 2.2 The Gate Elimination Method 3 Proof of Theorem 2 4 Nondeterministic Selecting 5 Proof of Theorem 1 5.1 The Nondeterministic Circuit Complexity 5.2 The Deterministic Circuit Complexity 5.3 The Co-Nondeterministic Circuit Complexity 6 Concluding Remarks References On Hardest Languages for One-Dimensional Cellular Automata 1 Introduction 2 Definitions 3 No Hardest Language for Trellis Automata 4 The Hardest Language for Linear-Time Cellular Automata 5 On Real-Time vs Linear-Time Cellular Automata References Usefulness of Information and Unary Languages 1 Introduction 2 Preliminaries, Notations and Definition of Problem 2.1 Number Theory 2.2 Usefulness of Information 3 Unary Deterministic Finite Automata 3.1 Rolling Cycle of UDFA 4 Deterministic Decomposability of -cyclic Languages References Learning Learnability and Positive Equivalence Relations 1 Introduction 2 Preliminaries 3 Learnability 4 Results for All Positive Equivalence Relations: Fin, Conf, Ex, Vac and BC Learning 5 Learnability of Families Closed Under Special Positive Equivalence Relations 6 Conclusion References Learning Mealy Machines with One Timer 1 Introduction 2 Mealy Machines with a Single Timer 3 Learning MM1Ts 3.1 From MM1Ts to Mealy Machines and Back 3.2 Membership Queries 4 From MM1T to DOTA Learning 5 Case Studies 5.1 Learning Setup 5.2 Android Authentication and Key Management 5.3 Performance Comparison 6 Conclusion and Future Work References Logics and Languages Finite-Word Hyperlanguages 1 Introduction 2 Preliminaries 3 Hyperregular Expressions 4 Nondeterminsitic Finite-Word Hyperautomata 5 Properties of Regular Hyperlanguages 5.1 Closure Properties 5.2 Decision Procedures 6 Discussion and Future Work References Temporal Logics with Language Parameters 1 Introduction 2 Preliminaries 3 Logics 3.1 Extended LTL 3.2 Extended CTL* and CTL+ 4 Automata for LTL[U] 5 Expressivity 6 Satisfiability 7 Model Checking References Commutative Rational Term Rewriting 1 Introduction 2 Preliminaries 2.1 Finite Automata 2.2 Rational Terms 2.3 Rational Term Rewriting 2.4 Products of Canonical Regular Systems 3 Automata for Inverse Rewrite Steps 4 Automata for Join of Branching Steps 5 Automata for Difference of Branching Steps 6 Closure Under Equivalence 7 Conclusion References Context-Free Grammars with Lookahead 1 Introduction 2 Languages with Lookahead 3 Context-Free Grammars with Lookahead 3.1 Definition of CFGLa 3.2 Closure Properties 3.3 Operational Semantics and Parsing Expression Grammars 4 Related Work and Discussion References Tree-Like Unit Refutations in Horn Constraint Systems 1 Introduction 2 Statement of Problems 3 Motivation and Related Work 4 Length-Bounded Tree-Like Unit Refutations 5 Optimal Length Tree-Like Unit Refutations 6 Lower Bounds on Kernel Size for TLURD 7 Conclusion References Trees and Graphs Homomorphic Characterization of Tree Languages Based on Comma-Free Encoding 1 Introduction 2 Basic Definitions 3 Main Results 4 Conclusion References Approximated Determinisation of Weighted Tree Automata 1 Introduction 2 Preliminaries 3 Approximated Determinisation 4 Approximated Twinning Property 5 Decidability of the Twinning Property 6 Outlook References Sequentiality of Group-Weighted Tree Automata 1 Introduction 2 Preliminaries 2.1 Weighted Tree Automata 3 Lipschitz and Twinning Property 3.1 The Lipschitz Property 3.2 The Twinning Property 4 Sequentiality of the Twinning Property 5 Outlook References An Algorithm for Single-Source Shortest Paths Enumeration in Parameterized Weighted Graphs 1 Introduction 2 Definitions 2.1 Parametric Graphs 2.2 Trees over Parametric Graphs 2.3 Constraints and Zones Associated to Trees 3 Presentation of Our Algorithm for Minimal Distances 4 Formal Presentation of Our Algorithm 4.1 The Algorithm 4.2 Proof of the Algorithm 4.3 Complexity 5 Conclusion References Words and Strings On Balanced Sequences and Their Asymptotic Critical Exponent 1 Introduction 2 Preliminaries 3 Languages of Balanced Sequences 4 Critical Exponent and Its Relation to Return Words 5 Asymptotic Critical Exponent of Balanced Sequences References Completely Reachable Automata, Primitive Groups and the State Complexity of the Set of Synchronizing Words 1 Introduction 2 Preliminaries and Definitions 3 General Results on the State Complexity of Syn(A) 4 Permutation Groups and State Complexity of Syn(A) 4.1 Primitive and k-Homogeneous Permutation Groups 4.2 Sync-Maximal Permutation Groups 5 k-Reachable Permutation Groups 6 Conclusion References State Complexity of the Set of Synchronizing Words for Circular Automata and Automata over Binary Alphabets 1 Introduction 2 Preliminaries and Definitions 3 General Results on the State Complexity of Syn(A) 4 Generalized Circular Automata 5 Automata over Binary Alphabets 6 Conclusion References Cadences in Grammar-Compressed Strings 1 Introduction 2 Preliminaries 3 NP-Complete Cadence Problems 4 L-R-Cadences 5 3-Cadences in Binary Strings 6 Conclusion References Author Index