
Language and Automata Theory and Applications
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions

Content
- Title
- Preface
- Organization
- Table of Contents
- Invited Talks
- Measuring Information in Timed Languages
- References
- Automata-Based Symbolic Representations of Polyhedra
- Introduction
- Basic Notions and Notations
- Polyhedra
- Topological Components
- Incidence Relation
- Extension to Polyhedral Partitions
- Towards a Better Data Structure for Polyhedra
- Real-Vector Automata
- Point Decision in RVA
- Principles of IRVA
- Decision Structure for Directions
- Implicit Real-Vector Automata
- Syntax
- Semantics
- Canonicity
- Canonical IRVA Representations
- Minimization Algorithm
- Combination Operation
- Conclusions and Perspectives
- References
- Around the Physical Church-Turing Thesis: Cellular Automata, Formal Languages, and the Principles of Quantum Theory
- The Church-Turing Thesis and Its Various Forms
- Why a Thesis?
- The Physical Church-Turing Thesis
- Beyond Natural Numbers
- Indexings
- Real Numbers
- Non-determinism
- Gandy's Proof
- Gandy's Hypotheses
- Gandy's Proof
- Criticizing Gandy's Hypotheses
- The Physical Church-Turing Thesis and the Galileo Thesis
- The Galileo Thesis
- The Physical Church-Turing Thesis Implies the Galileo Thesis
- An Algorithmic Description of the Laws of Nature
- A Property of Nature or of the Theory?
- The Physical Church-Turing Thesis and the Quantum Theory
- The Bounded Density of Information in the Quantum Case
- The Bounded Velocity of Information in the Quantum Case
- Conclusion
- References
- A Parameterized Complexity Tutorial
- Introduction
- Preamble
- The Idea
- Some Definitions
- Positive Techniques
- Bounded Search Trees
- Kernelization
- Iterative Compression
- Other Techniques
- Parametric Intractability
- XP-Optimality
- Other Things
- Left Out
- References
- The Computer Science of DNA Nanotechnology
- Regular Papers
- The Minimal Cost Reachability Problem in Priced Timed Pushdown Systems
- Introduction
- Preliminaries
- Priced Timed Pushdown Systems
- From Priced to Unpriced Timed Pushdown Systems
- From Timed Pushdown Systems to Pushdown Systems
- Conclusion
- References
- Unification Modulo Chaining
- Introduction
- Notation and Preliminaries
- Inference System for BC-Unification
- Inference System INFl for List-Equations
- Solving a BC-Unification Problem
- BC1-Unification Is NP-Complete
- An Illustrative Example
- Conclusion
- References
- Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits
- Introduction
- Main Result
- Approximate Isomorphism for ACs,d,n
- Exact Isomorphism Test for Low Degree Polynomials
- The Approximate Isomorphism Algorithm
- A General Approximate Isomorphism Algorithm
- References
- Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space
- Introduction
- RTMs and RMFAs
- Reversible Turing Machines
- Reversible Multihead Finite Automata
- RMFAs Characterize Reversible Logspace
- Encoding an RTM Configuration
- Simulating RTM Transitions
- Simulating an RMFA with a Logarithmic Space RTM
- Further Discussion of RMFAs
- Conclusion
- References
- Defining Contexts in Context-Free Grammars
- Introduction
- Definition by Deduction
- Definition by Language Equations
- Normal Form
- Parsing Algorithm
- Recognition in Linear Space
- Future Work
- References
- Longest Common Extensions via Fingerprinting
- Introduction
- Preliminaries
- The [k] Algorithm
- Data Structure
- Query
- Preprocessing
- Experimental Results
- Tested Algorithms
- Test Inputs and Setup
- Results
- Cache Optimization
- Conclusions
- References
- Fast and Cache-Oblivious Dynamic Programming with Local Dependencies
- Introduction
- Memory Models
- Previous Results
- Our Results
- Basic Definitions
- A New Algorithm for LCS
- Computing Boundaries
- Computing the LCS
- Analysis
- Experimental Results
- Setup
- Results
- References
- An Efficient Implicit OBDD-Based Algorithm for Maximal Matchings
- Introduction
- Preliminaries
- OBDDs and Functional Operations
- OBDD-Based Graph Algorithms and Matching Problems
- The Maximal Matching Algorithm
- Concluding Remarks
- References
- Strong Termination for Gap-Order Constraint Abstractions of Counter Systems
- Introduction
- Preliminaries
- Properties of Monotonicity Graphs
- Results on the Reachability Relation in GCS
- Strong Termination for Simple GCS
- S Satisfies the Termination Condition
- Strong Termination for Unrestricted GCS
- References
- Covering Space in the Besicovitch Topology
- Introduction
- Definitions and Tools
- Toeplitz Configurations and Their Construction
- The Result for the General Case
- Quasiperiodic Case Study
- Regular Toeplitz Case Study
- Finite Words and the Hamming Distance
- Result for Regular Toeplitz Configurations
- Bound Tightness for Regular Toeplitz Configurations
- References
- Approximate Regular Expressions and Their Derivatives
- Introduction
- Preliminaries
- Comparison Functions: Symbols, Sequences and Words
- Word Comparison Functions, Quotients and Derivatives
- Quotient of an Fk(L) Language
- Brzozowski Derivatives
- Antimirov Derivatives
- Conclusion
- References
- Catalytic Petri Nets Are Turing Complete
- Introduction
- Petri Nets and Firing Strategies
- Membrane Systems with Catalysts
- Relating Petri Nets and Membrane Systems
- Catalytic Petri Nets Are Turing Complete
- Conclusion and Future Work
- References
- Computational Complexity of Rule Distributions of Non-uniform Cellular Automata
- Introduction
- Notations and Definitions
- Number Conservation
- Surjectivity and Injectivity
- Equicontinuity and Sensitivity for Linear r-CA
- Conclusions
- References
- Conservative Groupoids Recognize Only Regular Languages
- Introduction
- Conservative Groupoids and Tournaments
- Commutative Case
- Building the Grammar
- Correctness of the Grammar
- Completeness of the Grammar
- Regularity of the Language Generated by the Grammar
- Non-commutative Case
- Building the Grammar
- Regularity of the Language Generated by the Grammar
- Languages Recognized by Conservative Groupoids
- Conclusion and Future Work
- References
- Advice Complexity of Online Coloring for Paths
- Overview of Advice Complexity
- Definitions
- Advice Complexity Definitions
- Online Coloring Definitions
- Theorems
- Proof of Theorem 1
- Proof of Theorem 2
- Conclusion
- References
- A Faster Grammar-Based Self-index
- Introduction
- Adding Bookmarks to a Balanced SLP
- Listing Occurrences
- Postscript
- References
- Learnability of Co-r.e. Classes
- Introduction
- Learnability
- Characterisations of Conservative Learning
- Indexed Families of Recursive Sets
- General Classes of r.e. Sets, Co-r.e. Sets, and Separations
- Conclusion
- References
- Two-Way Automata Making Choices Only at the Endmarkers
- Introduction
- Preliminaries
- The Subroutine Reach
- Simulation by Halting Self-verifying Automata
- Subexponential Deterministic Simulation
- Conditional and Unambiguous Simulations
- The Alternating Case
- Concluding Remarks
- References
- Polynomial-Time Algorithms for Learning Typed Pattern Languages
- Introduction
- Preliminaries and Background
- Pattern Languages and Typed Pattern Languages
- Learnability
- Type Witnesses
- Polynomial-Time Learning of Typed Pattern Languages
- Extensions of the Presented Results
- Learning Typed Pattern Languages over Infinitely Many Types
- Consistent Learning of Typed Pattern Languages
- Conclusion
- References
- Forbidding Sets and Normal Forms for Language Forbidding-Enforcing Systems
- Introduction
- Language Forbidding-Enforcing Systems
- Subword-Free and Subword-Incomparable Normal Forms
- Connecting Words and Minimal Normal Form
- Normal Forms for Strict Forbidding Sets
- Concluding Remarks
- References
- Applying Tree Languages in Proof Theory
- Introduction
- Rigid Tree Languages
- From Proofs to Tree Languages
- From Tree Languages to Proofs
- Applications
- Conclusion
- References
- The Membership Problem for Regular Expressions with Unordered Concatenation and Numerical Constraints
- Introduction
- Regular Expressions with Unordered Concatenation and Numerical Constraints
- Complexity of Membership under Unordered Concatenation
- Term Trees, Positions, and Subscripting
- Finite Automata with Counters
- Finite Automata with Counters
- Word Recognition
- Unambiguity
- Related Work
- Conclusion
- References
- Characterizing the Rational Functions by Restarting Transducers
- Introduction
- Restarting Transducer with Window Size One
- Restarting Automata with Window Size One
- Restarting Transducer
- Examples of Functions Computed by RR(1)-Transducers
- Relations Computed by nf-RR(1)-Transducers
- Sequential and Rational Functions
- Concluding Remarks
- References
- Weak Synchronization and Synchronizability of Multitape Pushdown Automata and Turing Machines
- Introduction
- Preliminaries
- Weak Synchronization of Multitape Automata
- Technique 1: Simulation by 1NPDAs with Reversal-Bounded Counters
- Technique 2: Reduction from Post Correspondence Problem
- Technique 3: Reduction from Halting Problems
- Space-Bounded Multitape Turing Machines
- Summary
- References
- Feasible Automata for Two-Variable Logic with Successor on Data Words
- Introduction
- Notation
- Weak Data Automata
- A Logical Characterization of Weak Data Automata
- From Weak Data Automata to EMSO2(+1,)
- From EMSO2(+1,) to Weak Data Automata
- Weak Büchi Data Automata
- Conclusion
- References
- Nash Equilibria in Concurrent Priced Games
- Introduction
- Preliminaries
- Temptation and Punishment
- Equilibrium Automaton
- Complexity of the Decision Variant
- Conclusion
- References
- Computing by Observing Insertion
- Computing by Observing
- Insertion Observer Systems
- Insertion Systems
- Observers
- Insertion Observer Systems
- Computing by Observing Insertion Systems
- Observing only Change
- Conclusions
- References
- On the Parameterized Complexity of Default Logic and Autoepistemic Logic
- Introduction
- Preliminaries
- MSO-Encodings
- Default Logic
- Autoepistemic Logic
- Pseudo-cliques
- Conclusion
- References
- Cayley Graph Automatic Groups Are Not Necessarily Cayley Graph Biautomatic
- Introduction
- Cayley Graph Automatic and Cayley Graph Biautomatic Groups
- (Free-abelian)-by-free Groups with Undecidable Conjugacy Problem
- References
- On Model Checking for Visibly Pushdown Automata
- Introduction
- Visibly Pushdown Automata
- Definitions
- Universality and Inclusion Checking
- Emptiness Checking
- Universality Checking
- Inclusion Checking
- Implementation and Experiments
- Conclusion
- References
- Automaton-Based Array Initialization Analysis
- Introduction
- A Simple Imperative Language and Its Semantics
- Regular Trace Approximation
- The Static Analysis Algorithm
- Dealing with Implicit Upper Bounds and Side-Effects
- Experiments
- Conclusion
- References
- Dynamics of Circuits and Intersecting Circuits
- Definitions and Preliminary Results
- Main Result
- Comparisons and Bounds
- Conclusion
- References
- Canonizable Partial Order Generators
- Introduction
- Transitive Reduction of Slice Graphs and Its Consequences
- Slices
- Sliced Transitive Reduction
- References
- Ogden's Lemma for ET0L Languages
- Introduction
- Definitions
- Previous Work
- Main Results
- Applications
- Concluding Remarks
- References
- Patterns with Bounded Treewidth
- Introduction
- Preliminaries
- Patterns and Words as Relational Structures
- Patterns with Restricted Scope Coincidence Degree
- References
- P-NP Threshold for Synchronizing Road Coloring
- Introduction
- Preliminaries
- SRCPC3 Is NP-complete for C 4 and 3
- Complexity of SRCPC for C=1,2 and 1
- Conclusions and Future Work
- References
- k-Automatic Sets of Rational Numbers
- Introduction
- Representing Rational Numbers
- Examples
- Basic Results
- Solvability Results
- References
- On Stable and Unstable Limit Sets of Finite Families of Cellular Automata
- Introduction
- Definitions
- Limit Sets and Basic Results
- Hierarchies
- Boolean Operations
- Conclusions
- References
- Automaton Ranks of Some Self-similar Groups
- Introduction
- Self-similar Groups and Their Automaton Ranks
- The Language of Wreath Products
- Automaton Groups and Automaton Ranks
- Automaton Ranks of Free Abelian Groups
- The Groups .HH as Automaton Groups
- The Case of Alternating Groups An, n&4
- The Case H=PSL2(p), p&3
- References
- One-Way Reversible and Quantum Finite Automata with Advice
- Background, Motivations, and Challenges
- Basic Terminology
- Reversible Finite Automata with Advice
- Properties of Advice for Quantum Computation
- References
- Integration of the Dual Approaches in the Distributional Learning of Context-Free Grammars
- Introduction
- Preliminaries
- Learning Targets
- Hypotheses
- Construction
- Properties of Hypotheses
- Learning of G(p,q,r)
- Identification in the Limit from Positive Data and Membership Queries
- Learning Algorithm for G(p,q,r)
- Learning of G(r)
- Minimally Adequate Teacher
- Learning Algorithm for G(r)
- Concluding Remarks
- References
- Author Index
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.