Implementation and Application of Automata

Name: Implementation and Application of Automata | 20th International Conference, CIAA 2015, Umeå, Sweden, August 18-21, 2015, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

20th International Conference, CIAA 2015, Umeå, Sweden, August 18-21, 2015, Proceedings

Frank Drewes(Editor)

Springer (Publisher)

Published on 27. July 2015

XXIII, 317 pages

E-Book

PDF with digital watermarking

System requirements

978-3-319-22360-5 (ISBN)

€53.49incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

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

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Implementation and Application of Automata

Description

More details

Other editions

Additional editions

Content

System requirements