Algebraic Informatics: 3rd International Conference on Algebraic Informatics, CAI 2009, Thessaloniki, Greece, Mai 19-22, 2009 (Lecture Notes in Computer Science, 5725)

CAI 2009 was the Third International Conference on Algebraic Informatics. It was intended to cover the topics of algebraic semantics on graphs and trees, formalpowerseries, syntacticobjects, algebraicpictureprocessing, ?nite and- ?nite computations, acceptors and transducers for strings, trees, graphs, arrays, etc., decision problems, algebraic characterization of logical theories, process algebra, algebraic algorithms, algebraic coding theory, algebraicaspects of cr- tography. CAI 2009 was dedicated to Werner Kuich on the occasion of his retirement. ItwasheldinThessaloniki, Greece, duringMay19-22,2009andorganizedunder the auspices of the Department of Mathematics of the Aristotle University of Thessaloniki. The opening lecture was given by Werner Kuich, the tutorials by Alessandra Cherubini and Wan Fokkink, and the other four invited lectures by Bruno Courcelle, Dietrich Kuske, Detlef Plump, and Franz Winkler. This volume contains 2 papers from the tutorials, 5 papers of the invited lectures, and 16 contributed papers. We received 25 submissions, the contributors being from 14 and countries, and the Program Committee selected 16 papers. WearegratefultothemembersoftheProgramCommitteefortheevaluation of the submissions and the numerous referees who assisted in this work. We shouldliketo thankallthecontributorsofCAI2009andespeciallythehonorary guest Werner Kuich and the invited speakerswho kindly accepted our invitation to present their important work. Special thanks are due to Alfred Hofmann the Editorial Director of LNCS, who gave us the opportunity to publish the proceedingsofourconferenceintheLNCSseries, aswellastoAnnaKramerfrom Springer for the excellent cooperation. We are also grateful to the members of the OrganizingCommittee and a groupof graduatestudents who helped us with several organizing jobs. Cover Front matter 1. Cycle-Free Finite Automata in Partial Iterative Semirings Cycle-Free Finite Automata in Partial Iterative Semirings Introduction Cycle-Free Elements in Partial Iterative Semirings Cycle-Free Finite Automata Cycle-Free Finite Automata with Discounting 2. Picture Languages: From Wang Tiles to 2D Grammars Picture Languages: From Wang Tiles to 2D Grammars Introduction Basic Definitions Wang Tiles Recognizable Picture Languages Labeled Wang Tiles and Tiling Systems Unambiguous and Deterministic Classes of Recognizable Picture Languages Models of 2-Dimensional Finite Automata Regular Expressions Logic Formulas Summary Necessary Conditions for Recognizability Recognizable Picture Languages on One-Letter Alphabet Grammars for Generating Pictures Tile Grammars Tile Grammars and Tiling Systems Regional Tile Grammars Průša's Grammars Kolam Grammars Context-Free Matrix Grammars Grid Grammars Summary Conclusion 3. Process Algebra: An Algebraic Theory of Concurrency Process Algebra: An Algebraic Theory of Concurrency Introduction The General Framework Basic Process Algebra Syntax of BPA Transition Rules of BPA Bisimulation Axioms for BPA Algebra of Communicating Processes Parallelism and Communication Left Merge and Communication Merge Axioms for PAP Deadlock and Encapsulation Recursion Guarded Recursive Specifications Transition Rules for Guarded Recursion Recursive Definition and Specification Principles Abstraction Rooted Branching Bisimulation Guarded Linear Recursion Revisited Abstraction Operators Cluster Fair Abstraction Rule Alternating Bit Protocol Specification of the ABP Verification of the ABP 4. On Several Proofs of the Recognizability Theorem On Several Proofs of the Recognizability Theorem References 5. Theories of Automatic Structures and Their Complexity Theories of Automatic Structures and Their Complexity Introduction Preliminaries Structures Automatic Structures Model Checking The Logic FSO The Model Checking Problem Data Complexity Expression Complexity Bounded Degree References 6. The Graph Programming Language GP The Graph Programming Language GP Introduction Graph Transformation Conditional Rule Schemata Graph Programs Semantics of Graph Programs Implementation Conclusion 7. Canonical Reduction Systems in Symbolic Mathematics Canonical Reduction Systems in Symbolic Mathematics Introduction Canonical Reduction Relations and Systems Generating Canonical Reduction Systems Gauss Elimination in Linear Algebra Euclid's Algorithm for gcds of Univariate Polynomials Gröbner Bases in Multivariate Polynomial Rings The Knuth-Bendix Procedure for Term Rewriting Systems Conclusion 8. Solving Norm Form Equations over Number Fields Solving Norm Form Equations over Number Fields Introduction The Set of Solutions of $N_{L/K}(x_1\omega_1+\cdots +x_{\ell}\omega_{\ell}) = 1$ Solving the Equation $N_{L/K}(x_1\omega_1+\cdots +x_{\ell}\omega_{\ell}) = 1$ Solving the Equation $N_{L/K}(x_1\omega_1+\cdots +x_{\ell}\omega_{\ell}) = k$ Examples 9. A Note on Unambiguity, Finite Ambiguity and Complementation in Recognizable Two-Dimensional Languages A Note on Unambiguity, Finite Ambiguity and Complementation in Recognizable Two-Dimensional Languages Introduction Preliminaries Classes HP and HK Some Results on Classes HP and HK Necessary Conditions in the Unary Case Conclusions and Open Questions 10. Context-Free Categorical Grammars Context-Free Categorical Grammars Introduction Rewriting in a Category Basic Definitions Dual Approach Rewriting Structures Context-Freeness Word Grammars Words Inductive Grammar Projective Grammar Graphs and Hypergraphs Inductive Hypergraph Grammars Projective Graph Grammars Conclusion 11. An Eilenberg Theorem for Pictures An Eilenberg Theorem for Pictures Introduction Recognizability through Monoid Action Deformation Monoids Frame Recognizability Recognizability through Picture Monoids Syntactic 2-Monoids The Variety Theorem 12. On the Complexity of the Syntax of Tree Languages subtitle Dedicated to Prof. Werner Kuich on the occasion of his retirement On the Complexity of the Syntax of Tree Languages Introduction Basic Facts Syntactic Complexity of Tree Languages Refined Syntactic Complexity Constructive Complexity of a Tree Automaton 13. On the Reversibility of Parallel Insertion, and Its Relation to Comma Codes On the Reversibility of Parallel Insertion, and Its Relation to Comma Codes Introduction Preliminaries When Does $(L_1 \Leftarrow L_2) \Rightarrow L_2$ Equal $L_1$? Comma Codes Comma Intercodes Conclusion 14. Computation of Pell Numbers of the Form pX 2 Computation of Pell Numbers of the Form $pX^{2}$ Introduction The Reduction Integer Points to $Y^{2}$=$X^{3}$-32$p^{2}X$ Examples 15. Iteration Grove Theories with Applications subtitle Dedicated to Prof. Werner Kuich on the Occasion of His Retirement Iteration Grove Theories with Applications Dedicated to Prof. Werner Kuich on the Occasion of His Retirement Introduction Grove Theories Grove Theories Equipped with a Dagger or a Generalized Star Operation Ordered Iteration Grove Theories Applications 16. Combinatorics of Finite Words and Suffix Automata Combinatorics of Finite Wordsand Suffix Automata Introduction Notation and Background The Suffix Automaton The Size of the Suffix Automaton Binary Words Conclusions and Open Problems 17. Polynomial Operators on Classes of Regular Languages Polynomial Operators on Classes of Regular Languages Introduction Preliminaries Locally Finite Varieties of Languages Polynomial Operators of Bounded Length Generating Pseudovarieties by a Single Monoid 18. Self-dual Codes over Small Prime Fields from Combinatorial Designs Self-dual Codes over Small Prime Fields from Combinatorial Designs Introduction Ternary Self-dual Codes from Skew-Hadamard Matrices A Construction Method for Ternary Self-dual Codes Ternary Extremal Self-dual Codes Self-dual Codes over $GF$(5) from Combinatorial Designs A [72,36] Self-dual Code over $GF$(5) Optimal Minimum Distances of Self-dual Codes over $GF$(5) 19. A Backward and a Forward Simulation for Weighted Tree Automata A Backward and a Forward Simulation for Weighted Tree Automata Introduction Preliminaries A Backward Simulation A Forward Simulation 20. Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms â•fl Revisited Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms — Revisited Introduction Preliminaries Syntax-Directed Translation Schema Closure under Composition 21. Polynomial Interpolation of the k-th Root of the Discrete Logarithm Polynomial Interpolation of the k-th Root of the Discrete Logarithm Introduction Roots of Odd Order Square Roots of Discrete Logarithms 22. Single-Path Restarting Tree Automata Single-Path Restarting Tree Automata Introduction Preliminaries and Notation Restarting Tree Automata Single-Path Top-Down Tree Automata Single-Path Restarting Tree Automata Ground-Rewrite Restarting Tree Automata Conclusion 23. Parallel Communicating Grammar Systems with Regular Control Parallel Communicating Grammar Systems with Regular Control Introduction Regulated Parallel Communicating Grammar Systems and FRR Automata Parallel Communicating Grammar Systems Regulated Parallel Communicating Grammar Systems Freely Rewriting Restarting Automata Analysis by Reduction and Regulated Parallel Communicating Grammar Systems Conclusion Back matter