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.
Author(s): Symeon Bozapalidis, George Rahonis
Series: Lecture Notes in Computer Science - Theoretical Computer Science and General Issues
Publisher: Springer
Year: 2008
Language: English
Pages: 298
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
