Automata, formal languages and algebraic systems : proceedings of AFLAS 2008, Kyoto, Japan, 20-22 September 2008

This volume consists of papers selected from the presentations at the workshop and includes mainly recent developments in the fields of formal languages, automata theory and algebraic systems related to the theoretical computer science and informatics. It covers the areas such as automata and grammars, languages and codes, combinatorics on words, cryptosystems, logics and trees, Grobner bases, minimal clones, zero-divisor graphs, fine convergence of functions, and others. CONTENTS 8 Preface 6 Solidifyable Minimal Clone of Partial Operation S. Busaman and K. Denecke 10 1. Introduction 10 2. Equivalent Strong Varieties of Partial Algebras 16 3. Minimal Partial Clones 20 4. Strongly Solidifyable Partial Clones 21 References 29 A Novel Cryptosystem Based on Finite Automata Without Output P. Domosi 32 1. Introduction 32 2. Preliminaries 33 3. A Novel Cipher 34 3.1. Key Automaton and Random Ciphertext Blocks 35 3.2. Encryption 35 3.3. Decryption 36 4. Encryption Without Backtracks 36 5. Cryptanalysis 36 5.1. Automatic Learning Algorithms 36 5.2. Adaptive Chosen-Ciphertext Attack, Adaptive Chosen- -Plaintext Attack, Adaptive Chosen-Plaintext -Chosen- -Ciphertext Attack 37 6. Performance 38 7. Conclusion 38 Acknowledgments 39 References 39 Linear Languages of Finite and In nite Words Z. Esik, M. Ito and W. Kuich 42 1. Linear languages 42 2. -monoids 44 3. Completely idempotent semiring-semimodule pairs 47 4. Conway semiring-semimodule pairs 50 5. Automata 52 6. Operational characterization of linear languages 53 References 55 Extended Temporal Logics on Finite Words Z. Esik and Sz. Iv an 56 1. Introduction 56 2. Trees 57 3. Temporal logics 59 4. The correspondence 61 5. Algebraic characterization 63 6. Ehrenfeucht-Fraısse type games 65 References 70 The Number of Distinct 4-Cycles and 2-Matchings of Some Zero-Divisor Graphs M. Kanemitsu 72 1. Introduction 72 2. Results 73 References 78 On Normal Form Grammars and Their Size A. Kelemenov a, L. Ciencialov a and L. Cienciala 80 1. Introduction 80 2. Preliminaries and formalism for language descriptions 82 3. Matrix algorithm and size estimation of languages 85 4. Partition of the derivations and size estimation of languages 89 5. Conclusion 92 References 93 Grobner Bases on Algebras Based on Well-Ordered Semigroups Y. Kobayashi 94 1. Well-ordered reexive semigroups 94 2. Factors and appearances 98 3. Rewriting on algebras 101 4. Grobner bases on algebras 105 5. Critical pair theorem 107 References 111 Concurrent Finite Automata and Related Language Classes M. Kudlek and G. Zetzsche 112 1. Introduction 112 2. Definitions 114 3. Normal Forms 117 4. Relations to Other Language Classes 118 5. Characterization and Decidability Results 119 6. Closure Properties 120 References 121 Finitely Expandable Deep PDAs P. Leupold and A. Meduna 122 1. Introduction 122 2. Definitions 123 3. A Hierarchy of Finitely Expandable Deep PDAs 125 4. Open Problems 132 References 132 The Primitivity Distance of Words G. Lischke 134 1. Introduction 134 2. Basic definitions and relationships 135 3. The distance to primitive words 139 4. The distance to nonprimitive words 140 5. Concluding remarks 144 Acknowledgement 145 References 145 Fine Convergence of Functions and Its E ectivization T. Mori, M. Yasugi and Y. Tsujii 148 1. Introduction 148 2. Fine convergence and continuous Fine convergence 150 3. Fine computability 154 4. Fine computable functions 157 5. Effective Fine convergence 160 6. Recursive functional equations and Fine computable functions 163 References 171 On a Hierarchy of Permutation Languages B. Nagy 172 1. Introduction 172 2. Basic Definitions and Preliminaries 174 3. Context-Free Grammars Extended with Permutation Rules 176 4. Conclusions, Further Remarks 186 Acknowledgements 186 References 186 Derivation Trees for Context-Sensitive Grammars B. Nagy 188 1. Introduction 188 2. Preliminaries 189 2.1. Chomsky-hierarchy: basic notions and de nitions 189 2.2. Derivation graphs for phrase-structure grammars 192 2.3. Derivation trees for context-free case 193 2.4. Derivation graphs for context-sensitive languages 195 2.4.1. Atanasiu's approach for monotonous grammars 196 3. A New Concept of Derivation Tree in Context-Sensitive Case 198 4. Left-Most Derivations in Context-Sensitive Case 203 5. Conclusions 207 Acknowledgements 207 References 208 On Proper Languages and Transformations of Lexicalized Types of Automata F. Otto 210 1. Introduction 210 2. Restarting Automata 213 3. Finite-State Acceptors and Pushdown Automata 219 4. Two-Pushdown Automata 221 5. Transformations Computed by Deterministic Types of Automata 224 6. Conclusion 229 References 229 Initial Literal Shu es of Uniform Codes G. Tanaka and Y. Kunimochi 232 1. Introduction 232 2. Initial Literal Shu es of Uniform Codes 234 References 246