Implementation and Application of Automata : 20th International Conference, CIAA 2015, Umeå, Sweden, August 18-21, 2015, Proceedings / / edited by Frank Drewes

• Pubblicazione: Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015
• Edizione: 1st ed. 2015.
• Descrizione fisica: 1 online resource (XXIII, 317 p. 60 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.): DrewesFrank
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di contenuto: Intro -- Preface -- Organization -- Invited Papers -- Automata and Logics for Concurrent Systems:Five Models in Five Pages -- Resource Automatic Structures for Verificationof Boundedness Properties -- Finite-State Technologyin Natural Language Processing -- Hardware Implementationsof Finite Automata and Regular Expressions -- Contents -- Invited Papers -- Automata and Logics for Concurrent Systems: Five Models in Five Pages -- 1 Introduction -- 2 Finite Automata -- 3 Class Memory Automata -- 4 Nested-Word Automata -- 5 Asynchronous Automata -- 6 Message-Passing Automata -- 7 Conclusion -- References -- Hardware Implementations of Finite Automata and Regular Expressions -- 1 Introduction -- 2 Typical Solutions -- 2.1 Abstractions -- 2.2 Implementations -- 2.3 Gaps in Current Solutions -- 3 New Implementations -- 4 Ongoing and Future Work -- References -- Regular Papers -- Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems -- 1 Introduction -- 1.1 Motivation -- 1.2 Problems Considered and Summary of Results -- 1.3 Related Work -- 2 Definitions and Problem Formulation -- 2.1 Formal Definition of the SyDS Model -- 2.2 Additional Terminology and Notation -- 2.3 Problem Formulations -- 2.4 Preliminary Results -- 3 Threshold Inference from Homogeneous Behavior Specifications -- 3.1 Inferring Thresholds from Stable Configurations -- 3.2 Inferring Thresholds from Unstable Configurations -- 4 Inference from Heterogeneous Collections of Behavior -- 4.1 The Complexity of ITSUC -- 4.2 Fixed Parameter Tractability of ITSUC -- 5 Future Research Directions -- References -- From Ambiguous Regular Expressions to Deterministic Parsing Automata -- 1 Introduction -- 2 Basic Definitions -- 3 Parser Construction -- 4 Tree and Complexity -- 5 Disambiguation Criteria -- 6 Conclusion -- References. ; Deciding Synchronous Kleene Algebra with Derivatives -- 1 Introduction -- 2 Deciding Synchronous Kleene Algebra -- 2.1 Partial Derivative Automata for SKA -- 2.2 Equivalence of SKA Expressions -- 2.3 Implementation and Experimental Results -- 3 Deciding Synchronous Kleene Algebra with Tests -- 3.1 SKAT and Guarded Synchronous Strings -- 3.2 Automata for Guarded Synchronous Strings -- 3.3 Partial Derivatives for SKAT -- 4 Experimental Results -- 5 Conclusion -- References -- On the Hierarchy of Block Deterministic Languages -- 1 Introduction -- 2 Preliminaries -- 2.1 Languages and Automata Basics -- 2.2 One-Unambiguous Regular Languages -- 2.3 Block Deterministic Regular Languages -- 3 Previous Results on Block-Deterministic Languages -- 4 A Witness for the Infinite Hierarchy -- References -- Security of Numerical Sensors in Automata -- 1 Introduction -- 2 Preliminaries -- 3 Maximal Mutual Information -- 4 Secure Numerical Sensing in Automata -- 4.1 Secure Numerical Sensing w.r.t. Estimated Mutual Information Rate -- 4.2 Secure Numerical Sensing in Automata -- 5 Conclusions -- References -- Jumping Finite Automata: Characterizations and Complexity -- 1 Introduction -- 2 Operations on Languages and Their Properties -- 3 Alphabetic Shuffle Expressions -- 4 Representations and Normal Forms -- 5 Comparing JFA and REG -- 6 Complexity of Parsing -- References -- Run-Length Encoded Nondeterministic KMP and Suffix Automata -- 1 Introduction -- 2 Notions and Basic Definitions -- 3 The Shift-And and BNDM Algorithms -- 4 RLE-Based Encoding of the Nondeterministic KMP and Suffix Automata -- 4.1 Computation of j -- 5 The Variants of Shift-And and BNDM -- 6 Comparison with the 1-Factorization Encoding -- 7 Conclusions -- References -- More on Deterministic and Nondeterministic Finite Cover Automata -- 1 Introduction -- 2 Preliminaries. ; 3 Lower Bound Techniques for Cover Automata -- 4 Conversions Between Finite Automata and Cover Automata -- 4.1 From Finite Automata to Cover Automata -- 4.2 From Cover Automata to Finite Automata -- 5 Determinization of Finite Cover Automata -- 6 Average Size Comparisons of Finite Cover Automata -- 7 Conclusions -- References -- On the Number of Synchronizing Colorings of Digraphs -- 1 Introduction -- 2 General Statements -- 3 Experimental Investigation of Digraphs -- 3.1 Algorithms -- 3.2 Experimental Results from Exhaustive Enumeration -- 3.3 Experiments on Random Digraphs -- 4 Digraphs with Specific Synchronizing Ratios -- 5 Conclusions and Open Problems -- References -- On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism -- 1 Introduction -- 1.1 Theoretical Background on NFA -- 1.2 Theoretical Background on Markov Chains -- 2 Random Generation of Non Deterministic Automata Using Markov Chain -- 3 Random Generation of Non Deterministic Automata upto Isomorphism -- 3.1 Metropolis-Hastings Algorithm -- 3.2 Counting Automorphisms -- 3.3 Isomorphism Problem for Automata with a Bounded Degree -- 3.4 Practical Computation Using Labelings -- 3.5 Experiments -- 4 Conclusion -- References -- Random Generation and Enumeration of Accessible Deterministic Real-Time Pushdown Automata -- 1 Introduction -- 2 Formal Background -- 3 Random Generation and Enumeration of RDPDA -- 3.1 Enumeration of RDPDA -- 3.2 Random Generation -- 4 Influence of the Accepting Condition -- 4.1 Emptiness of Accepted Languages -- 4.2 Empty-Stack Reachability -- 4.3 Reachability (with No Stack Condition) -- 4.4 A Rejection Algorithm for Reachable Complete RDPDA -- 5 Conclusion -- References -- Subword Metrics for Infinite Words -- 1 Introduction -- 2 Notation and Preliminaries -- 3 The CANTOR Topology and Regular -Languages. ; 3.1 Basic Properties of the CANTOR Topology -- 3.2 Regular -Languages -- 4 Topologies Defined by Subword Metrics -- 4.1 Shift-Invariance -- 4.2 Balls in (X,I) and (X,) -- 4.3 Non-Preservation of Regular -Languages -- 5 Completeness and Compactness -- 6 Subword Complexity -- References -- From Two-Way to One-Way Finite Automata---Three Regular Expression-Based Methods -- 1 Introduction -- 2 Notation and Definitions -- 3 Overview -- 4 Method 1: 2DFA to 1NFA/1DFA -- 5 Construction Details -- 6 Method 2: 2NFA to 1DFA by Complement Construction -- 6.1 A Note on the Construction -- 7 Method 3: 2NFA to 1DFA Directly -- 8 Implementations -- 9 Practical Concerns -- 10 Conclusion -- References -- Describing Homing and Distinguishing Sequences for Nondeterministic Finite State Machines via Synchronizing Automata -- 1 Introduction -- 2 Preliminaries -- 3 Describing the Set of All Homing Sequences of a Nondeterministic FSM via a Synchronizing Automaton -- 4 Describing the Set of All Distinguishing Sequences of a Nondeterministic FSM via a Synchronizing Automaton -- 5 Conclusion -- References -- Expressive Capacity of Concatenation Freeness -- 1 Introduction -- 2 Preliminaries and Definitions -- 3 Limits of Concatenation-Free Expressions -- 4 Closure Properties -- 5 Relations with Other Subregular Families -- References -- The Membership Problem for Linear and Regular Permutation Languages -- 1 Introduction -- 2 Preliminaries -- 3 The Non-uniform Membership Problem for PermLin -- 4 The Uniform Membership Problem for PermReg -- 5 Parameterized Complexity of the Uniform Membership Problem -- 6 Conclusions -- References -- Classical and Quantum Counter Automata on Promise Problems -- 1 Introduction -- 2 Definitions -- 3 Main Results -- 3.1 Separation of Exact 1Q1CAs and 1D1CAs -- 3.2 Separation of Las Vegas 1P1CAs and 1D1CAs. ; 3.3 A New Result on Blind Counter Automata -- References -- State Complexity of Prefix Distance -- 1 Introduction -- 2 Preliminaries -- 3 State Complexity of Prefix Neighbourhoods -- 4 Nondeterministic State Complexity -- 4.1 Prefix and Suffix Distance -- 4.2 Substring Distance Neighbourhoods -- 5 Conclusion -- References -- (Un)decidability of the Emptiness Problem for Multi-dimensional Context-Free Grammars -- 1 Introduction -- 2 Two-Dimensional Context-Free Grammars -- 3 Emptiness Problem -- 4 Three-Dimensional Kolam Grammar -- 5 Representable Functions -- 6 Conclusion -- References -- On the Disambiguation of Weighted Automata -- 1 Introduction -- 2 Preliminaries -- 3 R-Pre-disambiguation of Weighted Automata -- 3.1 Relation R over Q Q -- 3.2 Construction -- 3.3 Properties of the Resulting WFA -- 4 Disambiguation Algorithm -- 5 Sufficient Conditions -- 6 Experiments -- 7 Conclusion -- References -- Checking Whether an Automaton Is Monotonic Is NP-complete -- 1 Introduction -- 2 Monotonic Automata -- 2.1 MONOTONIC Is NP-complete -- 2.2 Reduction from MONOTONIC to MONOTONIC2 -- 3 Oriented Automata -- 4 Discussion -- References -- On the Semantics of Regular Expression Parsing in the Wild -- 1 Introduction -- 2 Definitions -- 3 Converting Regular Expressions into pTr -- 4 A Normal Form for Prioritized Transducers -- 5 Equivalence and Parsing with Prioritized Transducers -- 6 Conclusions and Future Work -- References -- Tool Demonstration Papers -- Introducing Code Adviser: A DFA-driven Electronic Programming Tutor -- 1 Introduction -- 2 How Code Adviser Works -- 3 Acting Intelligent -- 4 One Step Bug Repair -- 5 Discussing Bug Repair -- 6 Code Adviser in Action -- 7 Reflections on Automatic Tutoring -- References -- BSP: A Parsing Tool for Ambiguous Regular Expressions -- 1 Tool Description -- 2 Future Developments -- References -- Author Index.
• Sommario/riassunto: This book constitutes the refereed proceedings of the 20th International Conference on Implementation and Application of Automata, CIAA 2015, held in held in Umeå, Sweden, in August 2015. The 22 revised full papers presented together with 4 invited papers and 2 toool demonstration papers were carefully reviewed and selected from 49 submissions. The papers cover all aspects of cover automata, counter automata, decision algorithms on automata, descriptional complexity, expressive power of automata, homing sequences, jumping finite automata, multi-dimensional languages, parsing and pattern matching, quantum automata, realtime pushdown automata, random generation of automata, regular expressions, security issues, sensors in automata, transducers, transformation of automata, and weighted automata.
• Titolo autorizzato: Implementation and Application of Automata
• ISBN: 3-319-22360-7
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910483396803321
• Lo trovi qui: Univ. Federico II
• Serie: Theoretical Computer Science and General Issues, . 2512-2029 ; ; 9223