Algebraic Informatics. 9th International Conference, CAI 2022 Virtual Event, October 27–29, 2022 Proceedings

Description

Preface Organization Abstracts of Invited Talks Weighted Automata Over Monotonic Strong Bimonoids: Decidability and Undecidability of Finite Image Constraints, Graphs, Algebra, Logic, and Complexity Contents Invited Papers Chaining Multiplications in Finite Fields with Chudnovsky-Type Algorithms and Tensor Rank of the k-Multiplication 1 Introduction 1.1 Context, Notation and Basic Results 1.2 New Results and Organisation 2 Theoretical Construction of a Multiplying Algorithm 2.1 Notations 2.2 Algorithm 3 On the Existence of These Algorithms 3.1 Strategy of Construction 3.2 Towers of Algebraic Function Fields 4 Uniform Upper Bounds References On Some Algebraic Ways to Calculate Zeros of the Riemann Zeta Function 1 The Riemann Hypothesis 2 The Riemann Hypothesis in the Arithmetical Hierarchy 3 Calculation of the Zeta Zeros by Solving Algebraic Equations 4 Calculation of Summands from Dirichlet Series for the Zeta Function at Its Zeros References Shuffle Product of Regular Languages: Results and Open Problems 1 Introduction 2 Shuffle and Recognition 2.1 Shuffle Product 2.2 Monoids and Ordered Monoids 2.3 Power Monoids and Lower Set Monoids 3 Classes of Languages Closed Under Shuffle 3.1 Varieties of Languages Closed Under Shuffle 3.2 Positive Varieties of Languages Closed Under Shuffle 3.3 Intermixed Languages 4 Sequential and Parallel Decompositions 4.1 Definitions and Examples 4.2 Closure Properties 4.3 Schnoebelen's Problem 5 Conclusion References Contributed Papers Ordering the Boolean Cube Vectors by Their Weights and with Minimal Change 1 Introduction 2 Basic Notions and Preliminary Results 3 Ordering the Vectors of the Boolean Cube by Their Weights and with Minimal Change 4 Algorithm for Generating the Vectors of the Boolean Cube Ordered by Weights and with Minimal Change 5 Conclusions References Designated-Verifier Linkable Ring Signatures with Unconditional Anonymity 1 Introduction 2 Preliminaries 2.1 Notation 2.2 Security Assumptions 3 UDVLRS Definition and Security Model 3.1 UDVLRS Definition 3.2 Correctness 3.3 Adversarial Capabilities 3.4 Unforgeability 3.5 Anonymity 3.6 Non-transferability 3.7 Linkability 3.8 Non-slanderability 4 Our Construction 5 Security Analysis 6 Conclusion and Future Work References Finding Points on Elliptic Curves with Coppersmith's Method 1 Introduction 2 Preliminaries 2.1 Some ECC Cryptosystems 2.2 Lattice Basis Reduction and Coppersmith's Method 3 Small Solutions of the Elliptic Curve Equation 4 A Numerical Example 5 Conclusion References Weighted Propositional Configuration Logic over De Morgan Algebras 1 Introduction 2 Related Work 3 Preliminaries 4 Unweighted PCL 5 Weighted PCL over De Morgan Algebras 6 Examples 7 Discussion 8 Conclusion References Weighted Two-Way Transducers 1 Introduction 2 Preliminaries 3 Weighted Two-Way Transducers 4 Relation to Unweighted Case 5 Closure Properties References A Formal Algebraic Approach for the Quantitative Modeling of Connectors in Architectures 1 Introduction 2 Related Work 3 Preliminaries 4 The Weighted Algebra of Interactions 5 The Weighted Algebra of Connectors 6 On Congruence Relation for Fusion-wAC(P) Connectors 7 Discussion 8 Conclusion References Watson-Crick Powers of a Word 1 Introduction 2 Preliminaries 3 A Binary Operation Generating Watson-Crick Powers 4 Watson-Crick Conjugate Equations 5 Conjugacy and Commutativity with Respect to 6 -Primitive Words, and a Word's -Primitive Root Pair 7 Conclusions References A Normal Form for Matrix Multiplication Schemes 1 Introduction 2 Matrix Multiplication Schemes 3 The Symmetry Group 4 Minimal Orbit Elements 5 Minimizing the First Row 6 Timings and Analysis References Bideterministic Weighted Automata 1 Introduction 2 Preliminaries 3 Bideterministic Weighted Automata over a Semiring 4 The Minimality Property of Bideterministic Automata 4.1 Fields and Integral Domains 4.2 Other Commutative Rings 4.3 Positive Semirings 5 Decidability of Bideterminisability 5.1 Fields 5.2 Tropical Semirings References How to Decide Functionality of Compositions of Top-Down Tree Transducers 1 Introduction 2 Top-Down Tree Transducers 3 Functionality of Two-Fold Compositions 3.1 Construction of the LA-Transducer M 3.2 Correctness of the LA-Transducer M 3.3 Functionality of Arbitrary Compositions 4 Conclusion References Computation of Solutions to Certain Nonlinear Systems of Fuzzy Relation Inequations 1 Introduction 2 Preliminaries 3 Certain Types of Fuzzy Relation Inequations and Their Solutions References When Variable-Length Codes Meet the Field of Error Detection 1 Introduction 2 Preliminaries 3 Error Detection and the Prefix Metric 4 Error Detection and the Factor Metric 5 Error Detection in the Topologies Associated to (anti-)automorphisms 6 Concluding Remark References Author Index