Algebraic Informatics: 4th International Conference, CAI 2011, Linz, Austria, June 21-24, 2011, Proceedings (Lecture Notes in Computer Science, 6742)

Annotation This book constitutes the refereed proceedings of the 4th International Conference on Algebraic Informatics, CAI 2011, held in Linz, Austria, in June 2011. The 12 revised full papers presented together with 4 invited articles were carefully reviewed and selected from numerous submissions. The papers cover topics such as algebraic semantics on graph and trees, formal power series, syntactic objects, algebraic picture processing, finite and infinite computations, acceptors and transducers for strings, trees, graphs arrays, etc. decision problems, algebraic characterization of logical theories, process algebra, algebraic algorithms, algebraic coding theory, and algebraic aspects of cryptography Cover Lecture Notes in Computer Science 6742 Algebraic Informatics ISBN 9783642214929 Preface Organization Table of Contents Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems Introduction Preliminaries Algebraic Methods for Bounding Polynomial Growth Spectral Radius Joint Spectral Radius Automata Methods for Bounding Polynomial Growth Unifying Algebraic and Automata-Based Methods Automation and Experimental Results Automation Experimental Results Concluding Remarks References From Grammars and Automata to Algebras and Coalgebras Introduction Many-Sorted Signatures and Their Algebras -Algebras and F-Algebras Co/Induction, Abstraction, Restriction, Extension and Co/Recursion References Theme and Variations on the Concatenation Product The Instruments Semigroups and Semirings Syntactic Ordered Monoid Free Profinite Monoids Equations and Identities Varieties of Monoids Varieties of Languages Relational Morphisms Theme and Variations: The Concatenation Product Main Theme Three Variations Classical Area The Ground Bass: Schützenberger Products Transducers for the Product Linear Representations Algebraic Properties of the Schützenberger Product Passacaglia: Pumping Properties Chaconne: Closure Properties Varieties Closed under Product Varieties Closed under Modular Product Polynomial Closure Back to Identities Hierarchies and Bridges Harmony with Logic Other Variations, Recent Advances References Some Combinatorial Applications of Gr\"{o}bner Bases Introduction Gröbner Bases, Standard Monomials and Hilbert Functions Complete Uniform Families, Applications and Extensions Gröbner Bases and Standard Monomials for Complete Uniform Families Some Combinatorial Applications to q-Uniform Families Wilson's Rank Formula Generalizations of Uniform Families The Lex Game and Applications Partitions and Colorings Permutations, Trees and Partitions Graph Colorings Alon's Combinatorial Nullstellensatz Gröbner Bases and S-Extremal Set Systems References Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages Introduction Preliminaries Recognizability Conditions for Picture Languages Comparison of Recognizability Conditions for Picture Languages Conclusions and Open Problems References Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages Introduction Preliminaries Typed Monoids Typed Syntactic Monoid Weakly Closed Classes Varieties Discussion References Codes and Combinatorial Structures from Circular Planar Nearrings Introduction Preliminaries and Notations Circular Planar Nearrings PBIBDs and Association Scheme Disks Construction of PBIBDs Notations and Parameters Incidence Matrix of a Disk-Design Row and Column Codes from a Disk-Design Future Work References Independence of Hyperlogarithms over Function Fields via Algebraic Combinatorics Introduction Non Commutative Differential Equations Applications Through the Looking Glass: Passing from Right to Left Conclusion References Quantifier Elimination over Finite Fields Using Gr\"{o}bner Bases Introduction Preliminaries Ideals, Varieties, Nullstellensatz, and Gröbner Bases The First-Order Theory over a Finite Field Nullstellensatz in Finite Fields Quantifier Elimination Using Gröbner Bases Existential Quantification and Elimination Ideals Quantifier Elimination Using Elimination Ideals Formula Flattening with Ideal Operations Algorithm Description and Complexity Analysis Algorithm Description Complexity Analysis Example and Application A Walk-Through Example Analyzing a Biological Controller Design Conclusion References $F$-Rank-Width of (Edge-Colored) Graphs Introduction Preliminaries F-Rank-Width Rank-Width of -Symmetric F*-Graphs Vertex-Minor and Pivot-Minor Recognizing F-Rank-Width at Most k Specialisations to Graphs without Edge-Colors Algebraic Operations for F-Rank-Width Conclusion References An Algorithm for Computing a Basis of a Finite Abelian Group Introduction Preliminaries Our Results Auxiliary Results Computing the Order of an Element Proof of Theorem 1 Proofs of Corollaries 1 and 2 Conclusion References Rewriting in Varieties of Idempotent Semigroups Introduction Varieties of Idempotent Semigroups Rewriting on Varieties of Semigroups Generalities Term Rewriting and Known Results for Idempotent Semigroups Word Rewriting and Known Results for Idempotent Semigroups Conditional Word Rewriting Systems: Definitions and Examples Two Examples of Finite CWRS with Single Letter Deleting Rules A Finite CWRS for the Variety B2 Single Letter Deleting Identities and Single Letter Deleting Rewrite Systems References Simplifying Algebraic Functional Systems Introduction Preliminaries Problems Polymorphism Leading Variables Output Arity Filling in Head Variables Preparing Polymorphic Types Explicit Application Abstractions in Left-hand Sides and -Redexes Currying $\eta$-Expansion Conclusions References Hadamard Matrices, Designs and Their Secret-Sharing Schemes Introduction – Preliminaries Some Constructions for Hadamard Matrices Hadamard Matrices Obtained via Kronecker Product Paley Type Hadamard Matrices Hadamard Matrices Obtained from Two Circulant Submatrices Hadamard Matrices Obtained from Other Multiplication Methods List of Hadamard Matrices of Orders Up to 100 Hadamard 3-Designs and Secret-Sharing Schemes Algorithmic Construction of Secret-Sharing Schemes from Hadamard Matrices Conclusion References I-RiSC: An SMT-Compliant Solver for the Existential Fragment of Real Algebra Introduction Preliminaries SMT-Solving Real Algebra Computing Realizable Sign Conditions The I-RiSC Solver Data Structure Class Design Methods Example Optimizations Conclusion References Variable Tree Automata over Infinite Ranked Alphabets Introduction Preliminaries Variable Tree Automata Conclusions and Future Work References Author Index This book constitutes the refereed proceedings of the 5th International Conference on Algebraic Informatics, CAI 2013, held in Porquerolles, France in September 2013. The 19 revised full papers presented together with 5 invited articles were carefully reviewed and selected from numerous submissions.