This book constitutes the refereed proceedings of the Third International Conference on Algebraic Informatics, CAI 2009, held in Thessaloniki, Greece, in May 2009.
The 16 full papers were carefully reviewed and selected from 25 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, algebraic aspects of cryptography.
Author(s): Stephen L. Bloom, Zoltan Ésik, Werner Kuich (auth.), Symeon Bozapalidis, George Rahonis (eds.)
Series: Lecture Notes in Computer Science 5725 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 361
Tags: Logics and Meanings of Programs; Mathematical Logic and Formal Languages; Symbolic and Algebraic Manipulation; Software Engineering; Discrete Mathematics in Computer Science; Mathematics of Computing
Front Matter....Pages -
Cycle-Free Finite Automata in Partial Iterative Semirings....Pages 1-12
Picture Languages: From Wang Tiles to 2D Grammars....Pages 13-46
Process Algebra: An Algebraic Theory of Concurrency....Pages 47-77
On Several Proofs of the Recognizability Theorem....Pages 78-80
Theories of Automatic Structures and Their Complexity....Pages 81-98
The Graph Programming Language GP....Pages 99-122
Canonical Reduction Systems in Symbolic Mathematics....Pages 123-135
Solving Norm Form Equations over Number Fields....Pages 136-146
A Note on Unambiguity, Finite Ambiguity and Complementation in Recognizable Two-Dimensional Languages....Pages 147-159
Context-Free Categorical Grammars....Pages 160-171
An Eilenberg Theorem for Pictures....Pages 172-188
On the Complexity of the Syntax of Tree Languages....Pages 189-203
On the Reversibility of Parallel Insertion, and Its Relation to Comma Codes....Pages 204-219
Computation of Pell Numbers of the Form pX 2 ....Pages 220-226
Iteration Grove Theories with Applications....Pages 227-249
Combinatorics of Finite Words and Suffix Automata....Pages 250-259
Polynomial Operators on Classes of Regular Languages....Pages 260-277
Self-dual Codes over Small Prime Fields from Combinatorial Designs....Pages 278-287
A Backward and a Forward Simulation for Weighted Tree Automata....Pages 288-304
Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms — Revisited....Pages 305-317
Polynomial Interpolation of the k-th Root of the Discrete Logarithm....Pages 318-323
Single-Path Restarting Tree Automata....Pages 324-341
Parallel Communicating Grammar Systems with Regular Control....Pages 342-360
Back Matter....Pages -
