Implementation and Application of Automata : 19th International Conference, CIAA 2014, Giessen, Germany, July 30 -- August 2, 2014, Proceedings / / edited by Markus Holzer, Martin Kutrib

• Pubblicazione: Cham : , : Springer International Publishing : , : Imprint : Springer, , 2014
• Edizione: 1st ed. 2014.
• Descrizione fisica: 1 online resource (X, 347 p. 76 illus.)
• Disciplina: 511.3
• Soggetto topico: Computer science; Algorithms; Machine theory; Bioinformatics; Artificial intelligence—Data processing; Information storage and retrieval systems; Theory of Computation; Formal Languages and Automata Theory; Computational and Systems Biology; Data Science; Information Storage and Retrieval
• Persona (resp. second.): HolzerMarkus; KutribMartin
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di contenuto: Intro -- Preface -- Organization -- Table of Contents -- Invited Papers -- FPsolve: A Generic Solver for Fixpoint Equations over Semirings -- 1 Introduction -- 2 Scenario: A Recommendation System -- 3 Algorithms and Data Structures -- 3.1 Solving Linear Equations -- 3.2 Decomposition into Strongly-Connected Components -- 4 Implementation -- 4.1 Invocation of the Standalone Solver -- 4.2 Custom Semirings and Extensions -- 5 Conclusions and Related Tools -- References -- Restarting Automata for Picture Languages: A Survey on Recent Developments -- 1 Introduction -- 2 Pictures and Picture Languages -- 3 Sgraffito Automata -- 4 Deterministic Sgraffito Automata -- 5 Restarting Tiling Automata -- 6 Ordered Restarting Automata -- 7 Deterministic Three-Way ORWW-Automata -- 8 Deterministic Two-Way ORWW-Automata -- 9 Conclusion -- References -- Investigations on Automata and Languages over a Unary Alphabet -- 1 Introduction -- 2 Unary Finite Automata: Optimal Simulations -- 3 Unary Two-Way Automata -- 4 Beyond Finite Automata -- 5 Beyond Regular Languages -- 6 Final Remarks -- References -- Cellular Automata for Crowd Dynamics -- 1 Introduction -- 2 CA Models for Crowd Dynamics -- 3 Conclusions -- References -- Regular Papers -- Counting Equivalent Linear Finite Transducers Using a Canonical Form -- 1 Introduction -- 2 Basic Concepts -- 3 Testing the Equivalence of LFTs -- 4 Canonical LFTs -- 5 On the Size of Equivalence Classes of LFTs -- 6 Conclusion -- References -- On the Power of One-Way Automata with Quantum and Classical States -- 1 Introduction -- 2 Preliminaries -- 2.1 Linear Algebra -- 2.2 Languages and Formal Power Series -- 2.3 Finite Automata -- 3 Characterizing the Power of qcfas -- 4 Size-Cost of Language Operations on qcfas -- References -- On Comparing Deterministic Finite Automata and the Shuffle of Words -- 1 Introduction. ; 2 Preliminaries -- 3 Fixed-Length Skeleton Polynomial Algorithm -- 4 General coNP-Completeness -- References -- Minimal Partial Languages and Automata -- 1 Introduction -- 2 Approximating Minimal -DFAs -- 3 Computing Minimal -DFAs -- 3.1 Our Minlang Algorithm -- 3.2 Our Redundancy Check Algorithm -- 3.3 Our Partial Language Check Algorithm -- 4 Adapting Minlang for Infinite Languages -- 5 Conclusion and Open Problems -- References -- Large Aperiodic Semigroups -- 1 Introduction -- 2 Terminology and Notation -- 3 Unitary and Semiconstant DFAs -- 4 Unitary Semigroups -- 5 Semiconstant Semigroups -- References -- On the Square of Regular Languages -- 1 Introduction -- 2 Square for Automata with k Final States -- 2.1 An Application -- 3 Square of Languages over Unary Alphabet -- 3.1 Finite Unary Languages -- 3.2 General Unary Languages -- 4 Conclusions -- References -- Unary Languages Recognized by Two-Way One-Counter Automata -- 1 Introduction -- 2 Background -- 3 Main Results -- 3.1 Simulation of Multi-counter Automata on Unary Alphabet -- 3.2 Simulation of Turing Machines on Binary and General Alphabets -- 3.3 A Quantum Simplification -- 3.4 Unary 2D1CAs versus Two-Counter Machines -- References -- A Type System for Weighted Automata and Rational Expressions -- 1 Introduction -- 2 Typing Automata and Rational Expressions -- 2.1 Weighted Automata -- 2.2 Rational Expressions -- 3 The Type System -- 3.1 Operations on Automata -- 3.2 The Hierarchy of Types -- 3.3 Type Restriction -- 4 Implementation Facet -- 4.1 The Value/ValueSet Design Principle -- 4.2 Computations on Types -- 4.3 On-the-Fly Compilation -- 5 Future Work and Improvements -- 5.1 Syntactic and Semantic Improvements of Contexts -- 5.2 Dynamic Compilation Granularity -- 6 Conclusion -- References -- Bounded Prefix-Suffix Duplication -- 1 Introduction -- 2 Preliminaries. ; 3 Bounded Prefix-Suffix Duplication as a Formal Operation on Languages -- 3.1 Membership Problem -- 4 Bounded Prefix-Suffix Duplication Distances -- References -- Recognition of Labeled Multidigraphs by Spanning Tree Automata -- 1 Introduction -- 2 Preliminaries -- 3 Spanning Tree Automaton -- 3.1 Definition -- 3.2 Basic Properties -- 4 Membership Problem -- 4.1 NP-Completeness -- 4.2 Linear-Time Solvability of the Membership Problem for Graphs of Bounded Tree-Width -- 5 Conclusion and Future Work -- References -- Reset Thresholds of Automata with Two Cycle Lengths -- 1 Introduction -- 2 Wielandt-Type Automata -- 3 Dulmage-Mendelsohn-Type Automata -- References -- On the Ambiguity, Finite-Valuedness, and Lossiness Problems in Acceptors and Transducers -- 1 Introduction -- 2 Ambiguity in Acceptors -- 3 Finite-Valuedness in Transducers -- 4 Lossiness in Transducers -- 5 Finite-Valuedness in Context-Free Transducers -- 6 Undecidable Problems Concerning 2-Tape NFAs -- 7 Conclusion -- References -- Kleene Closure on Regular and Prefix-Free Languages -- 1 Introduction -- 2 Kleene Closure on Regular Languages: Contiguous Range of Complexities for Linear Alphabet -- 3 Kleene Closure on Prefix-Free Languages -- 4 Conclusions -- References -- Left is Better than Right for Reducing Nondeterminism of NFAs -- 1 Introduction -- 2 Preliminaries -- 3 NFA Constructions from Regular Expressions -- 4 NFA Reduction by Invariant Equivalences -- 5 Nondeterminism of NFAs -- 6 Experimental Results -- 6.1 Size Reduction of NFAs -- 6.2 Reduction of Nondeterminism -- 7 Conclusions -- References -- Analytic Functions Computable by Finite State Transducers -- 1 Introduction -- 2 Subshifts -- 3 Finite Accepting Automata -- 4 M¨obius Transformations -- 5 M¨obius Number Systems -- 6 Finite State Transducers -- 7 Analytic Functions -- 8 Rational Transformations and Intervals. ; 9 The Binary Signed System -- 10 Bimodular Systems -- 11 Conclusions -- References -- Partial Derivative and Position Bisimilarity Automata -- 1 Introduction -- 2 Regular Expressions and Automata -- 2.1 Position Automaton -- 2.2 Partial Derivative Automaton -- 3 Apd Characterizations and Bisimilarity -- 3.1 Linear Regular Expressions -- 3.2 Finite Languages -- 3.3 Comparing -- 3.4 General Regular Languages -- References -- The Power of Regularity-Preserving Multi Bottom-up Tree Transducers -- 1 Introduction -- 2 Notation -- 3 Formal Models -- 4 Main Results -- References -- Pushdown Machines for Weighted Context-Free Tree Translation -- 1 Introduction -- 2 Preliminaries -- 3 Weighted Synchronous Context-Free Tree Grammar -- 4 Weighted Pushdown Extended Tree Transducers -- 5 Main Result -- 6 Conclusion -- References -- Weighted Variable Automata over Infinite Alphabets -- 1 Introduction -- 2 Preliminaries -- 3 Weighted Variable Automata -- 4 Closure Properties of the Class VRec (K,Σ). -- 5 Rational Series over Infinite Alphabets -- 6 Application to Variable Finite Automata -- Conclusion -- References -- Implications of Quantum Automata for Contextuality -- 1 Preliminaries -- 1.1 Promise Problems -- 1.2 Quantum Automata -- 2 Quantum Automata for Promise Problems -- 2.1 Exact Rational (Sweeping) 2QCFA Algorithm -- 2.2 Exact Rational Restarting rtQCFA Algorithm -- 2.3 Las Vegas Rational rtQCFA Algorithm -- 2.4 Succinctness of Realtime QFAs -- 3 Noncontextual Inequalities from Automata -- 4 Discussion -- References -- Pairwise Rational Kernels Obtained by Automaton Operations -- 1 Introduction -- 2 Related Works -- 3 Background -- 3.1 Automata, Finite-State Transducers -- 3.2 Kernels and Rational Kernels -- 3.3 n-gram Kernel as a Rational Kernel -- 3.4 Pairwise Rational Kernels -- 4 New Pairwise Rational Kernels as Automaton Operations. ; 4.1 General Definitions -- 4.2 Automata Operations -- 4.3 New Pairwise Rational Kernels -- 4.4 Algorithms -- 5 Methods -- 5.1 Dataset and Kernels -- 5.2 Learning Procedure -- 6 Results -- 7 Conclusion -- References -- Author Index.
• Sommario/riassunto: This book constitutes the refereed proceedings of the 19th International Conference on Implementation and Application of Automata, CIAA 2014, held in Giessen, Germany, in July/August 2014. The 21 revised full papers presented together with 4 invited papers were carefully selected from 36 submissions. The papers cover all aspects of implementation, application, and theory of automata and related structures such as algorithms on automata, automata and logic, bioinformatics, complexity of automata operations, compilers, computer-aided verification, concurrency, data structure design for automata, data and image compression, design and architecture of automata software, digital libraries, DNA/molecular/membrane computing, document engineering, editors, environments, experimental studies and practical experience, implementation of verification methods and model checking, industrial applications, natural language and speech processing, networking, new algorithms for manipulating automata, object-oriented modeling, pattern-matching, pushdown automata and context-free grammars, quantum computing, structured and semi-structured documents, symbolic manipulation environments for automata, transducers and multi-tape automata, techniques for graphical display of automata, VLSI, viruses and related phenomena, and world-wide Web.
• Titolo autorizzato: Implementation and Application of Automata
• ISBN: 3-319-08846-7
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910483916603321
• Lo trovi qui: Univ. Federico II
• Serie: Theoretical Computer Science and General Issues, . 2512-2029 ; ; 8587