Language and Automata Theory and Applications

Name: Language and Automata Theory and Applications | 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012, Proceedings

Adrian-Horia Dediu Carlos Martín-Vide(Herausgeber*in)

Springer (Verlag)

1. Auflage

Erschienen am 29. Februar 2012

XII, 556 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-28332-1 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken