Algebraic Informatics

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.

Klappentext

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.

Inhalt
Invited Paper of Werner Kuich.- Cycle-Free Finite Automata in Partial Iterative Semirings.- Tutorials.- Picture Languages: From Wang Tiles to 2D Grammars.- Process Algebra: An Algebraic Theory of Concurrency.- Invited Papers.- On Several Proofs of the Recognizability Theorem.- Theories of Automatic Structures and Their Complexity.- The Graph Programming Language GP.- Canonical Reduction Systems in Symbolic Mathematics.- Contributed Papers.- Solving Norm Form Equations over Number Fields.- A Note on Unambiguity, Finite Ambiguity and Complementation in Recognizable Two-Dimensional Languages.- Context-Free Categorical Grammars.- An Eilenberg Theorem for Pictures.- On the Complexity of the Syntax of Tree Languages.- On the Reversibility of Parallel Insertion, and Its Relation to Comma Codes.- Computation of Pell Numbers of the Form pX 2.- Iteration Grove Theories with Applications.- Combinatorics of Finite Words and Suffix Automata.- Polynomial Operators on Classes of Regular Languages.- Self-dual Codes over Small Prime Fields from Combinatorial Designs.- A Backward and a Forward Simulation for Weighted Tree Automata.- Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms Revisited.- Polynomial Interpolation of the k-th Root of the Discrete Logarithm.- Single-Path Restarting Tree Automata.- Parallel Communicating Grammar Systems with Regular Control.