Algebraic Informatics: Second International Conference, CAI 2007, Thessalonkik, Greece, May 21-25, 2007, Revised Selected and Invited Papers (Lecture Notes in Computer Science (4728))

This book constitutes the refereed proceedings of the Second International Conference on Algebraic Informatics, CAI 2007, held in Thessaloniki, Greece, in May 2007. The 10 revised full papers presented together with 9 invited papers were carefully reviewed and selected from 29 submissions. The papers cover topics such as algebraic semantics on graphs and trees, formal power series, syntactic objects, algebraic picture processing, infinite computation, acceptors and transducers for strings, trees, graphs, arrays, etc., and decision problems. LNCS 4728 - Algebraic Informatics......Page 1 Preface......Page 5 Organization......Page 6 Table of Contents......Page 7 Introduction......Page 9 Inputstrings as Addresses......Page 10 Image Generation by Finite Acceptors......Page 11 Bi-level Images in 2D......Page 12 Bintrees for Addressing......Page 13 Bit-Planes for Grayscale and Colour-Images......Page 14 Weighted Finite Automata......Page 16 WFA and Polynomials......Page 17 Image- and Video-Compression with WFA......Page 19 Parametric Weighted Finite Automata......Page 21 PWFA over a Unary Alphabet......Page 22 Curves and Segments with Parametric Polynomial Representation......Page 24 Spline Curves and 3D-Patches......Page 26 Conclusions and Open Problems......Page 27 Introduction......Page 31 Complexity......Page 32 Other Complexity Functions......Page 33 Palindromic Closure......Page 35 Justin's Formula......Page 36 Mechanical Words......Page 38 Finite Sturmian Words......Page 39 Standard and Central Words......Page 40 Characterizations of Central Words......Page 41 Balance......Page 43 Lexicographic Ordering......Page 45 Burrows-Wheeler Transformation......Page 47 Sturmian Graphs......Page 50 Introduction......Page 56 Signatures and Trees......Page 57 Tree-Based Generators......Page 58 String Generation......Page 59 Tree Generation......Page 60 Graph Generation......Page 62 Generation of Line Drawings......Page 64 Generation of Collages......Page 66 Music Generation......Page 69 Delegation Networks......Page 70 Nondeterministic Functions and Algebras......Page 71 The Definition and Semantics of Delegation Networks......Page 72 An Example......Page 74 Conclusion and Outlook......Page 78 Bifinite Chu Spaces......Page 81 Introduction......Page 83 Preliminaries......Page 85 Unambiguity and Determinism in Tiling Systems......Page 87 Tiling Automata......Page 91 Quantum Informatics......Page 95 Basics of Quantum Information Processing......Page 96 Why Quantum Mechanics Is as It Is?......Page 100 Quantum (Finite) Automata......Page 101 Quantum Computation Primitives - Universality, Optimization......Page 106 Quantum Circuits That Can be Simulated Classically......Page 107 Quantum Algorithms Design Challenges......Page 108 Quantum Entanglement......Page 111 Quantum and Other Non-Localities......Page 113 Bell Inequalities......Page 116 Grand Challenges of Quantum Informatics......Page 117 Introduction......Page 120 Characterizations of Recognizable Picture Languages......Page 121 Regular Picture Languages......Page 124 Concatenation Alternation Hierarchy......Page 125 Conclusion......Page 126 Introduction to Graph Transformation......Page 130 Graph and Typed Graph Transformation......Page 132 Overview of Results for (Typed) Graph Transformations......Page 139 Transformations in Adhesive HLR Systems......Page 150 Conclusion......Page 153 Introduction......Page 155 Preliminaries......Page 157 Deterministic Recognizable Languages......Page 159 Properties of DREC(1)......Page 160 DREC(1) and Some Regular Families......Page 164 Conclusions and Open Questions......Page 166 Introduction......Page 168 Polyominoes......Page 170 Recognizable Picture Languages and Polyominoes......Page 173 $L_h$-convex and $L_v$-convex polyominoes......Page 176 Introduction......Page 180 Tree Generation......Page 182 An Algebra for Music......Page 185 Variations and Canons......Page 188 Conclusion......Page 194 References......Page 195 Introduction......Page 197 Aperiodicity in Tree Automata......Page 198 Aperiodicity and the Cascade Product......Page 201 Strict Containments......Page 204 Decidability and Complexity......Page 206 Aperiodicity and Logic......Page 208 A Variant of Aperiodicity......Page 211 Conclusions......Page 213 Introduction......Page 216 Magmoids and Graphs......Page 218 Recognizability and Syntactic Complexity......Page 220 The Syntactic Complexity of Eulerian Graphs......Page 221 Introduction......Page 226 Weighted Tree Automaton......Page 228 Learning Algorithm......Page 230 An Example......Page 239 Complexity Analysis......Page 241 Introduction......Page 244 Notation and Definitions......Page 246 Some Useful Properties of $G_{n, n, p}$......Page 247 Bounds for the Second Eigenvalue and the Mixing Time......Page 248 Conclusions and Future Work......Page 252 Introduction......Page 255 CafeOBJ Basics......Page 256 Observational Transition Systems......Page 257 Notation......Page 258 The Key Agreement Protocol......Page 259 SNEP Modeling......Page 260 Key Agreement Protocol Modeling......Page 263 Proof Scores of Authentication Property......Page 264 Proof Scores of Key Agreement Property......Page 265 Conclusion......Page 266 Introduction......Page 268 Roubaud Relative Associativity......Page 269 Notation and Definitions......Page 270 Coherence Results......Page 271 Rational Formal Power Series......Page 275 Kleene Theorem......Page 276 Generalization of the Relative Associativity......Page 278 Conclusion......Page 280 Introduction......Page 283 Preliminaries......Page 284 Growing Linear Tree Grammars......Page 286 Restarting Tree Automata......Page 292 Conclusion......Page 295 Author Index......Page 298 Annotation This book constitutes the refereed proceedings of the Second International Conference on Algebraic Informatics, CAI 2007, held in Thessaloniki, Greece, in May 2007. The papers cover topics such as algebraic semantics on graphs and trees, formal power series, syntactic objects, algebraic picture processing, infinite computation, acceptors and transducers for strings, trees, graphs, arrays, etc., and decision problems