Algebraic Informatics
4th International Conference, CAI 2011, Linz, Austria, June 21-24, 2011, Proceedings
Published on 21. June 2011
X, 261 pages
978-3-642-21493-6 (ISBN)
Description
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.
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.
More details
Other editions
Additional editions
Franz Winkler
Algebraic Informatics
4th International Conference, CAI 2011, Linz, Austria, June 21-24, 2011, Proceedings
Book
06/2011
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Invited Papers
- 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
- $\Sum$-Algebras and F-Algebras
- Co/Induction, Abstraction, Restriction, Extension and Co/Recursion
- References
- Theme and Variations on the Concatenation Product
- TheInstruments
- 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¨utzenberger Products
- Transducers for the Product
- Linear Representations
- Algebraic Properties of the Sch¨utzenberger 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
- Contributed Papers
- 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 $\sigma$-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
