Language and Automata Theory and Applications

Name: Language and Automata Theory and Applications | 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings

Adrian-Horia Dediu Jan Janousek Carlos Martín-Vide Bianca Truthe(Editor)

Springer (Publisher)

Published on 29. February 2016

XXII, 618 pages

E-Book

PDF with digital watermarking

System requirements

978-3-319-30000-9 (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
Abstracts of Invited Talks
Reconstructing Preferences from Opaque Transactions
Non-Zero Sum Games for Reactive Synthesis
Tangles and Connectivity in Graphs
Restricted Turing Machines and Language Recognition
Automata for Ontologies
Contents
Invited Talks
Non-Zero Sum Games for Reactive Synthesis
1 Introduction
2 Preliminaries
3 Classical Zero-Sum Setting
4 Assume Admissible Synthesis
5 Regret Minimization
6 Game Arenas with Expected Adversary
References
Tangles and Connectivity in Graphs
1 Introduction
2 Preliminaries
3 Tangles in a Graph
4 Tangles and Components
4.1 Biconnected and Triconnected Components
4.2 From Components to Tangles
4.3 From Tangles to Components
5 A Broader Perspective: Tangles and Connectivity Systems
5.1 Tangles
6 Decompositions and Duality
References
Restricted Turing Machines and Language Recognition
1 Introduction
2 Fast One-Tape Turing Machines
3 One-Tape Turing Machines with Rewriting Restrictions
4 Final Remarks
References
Automata for Ontologies
References
Automata and Logic
Reasoning with Prototypes in the Description Logic ALC Using Weighted Tree Automata
1 Introduction
2 Preliminaries
3 Prototypes and Weighted Tree Automata
4 Reasoning with Prototype Automata in ALC
5 Conclusions
References
+-Picture Languages Recognizable by Büchi-Tiling Systems
1 Introduction
2 Preliminaries
3 Büchi-Tiling Recognizable +-Picture Languages
4 A Logical Characterization of the Büchi-Tiling Recognizable +-Picture Languages
5 No Büchi Characterization Theorem For +-Picture Languages
6 Conclusion
References
A Logical Characterization for Dense-Time Visibly Pushdown Automata
1 Introduction
2 Preliminaries
3 Dense-Time Visibly Pushdown Automata (dtVPA)
4 Emptiness and Determinizability
5 Logical Characterization of dtVPA
References
A Complexity Measure on Büchi Automata
1 Introduction
2 Preliminaries
3 A Complexity Measure on NBAs
4 From NBk to DMk'
5 From DMk+ to NBk'
References
Compositional Bisimulation Minimization for Interval Markov Decision Processes
1 Introduction
2 Preliminaries
2.1 Interval Markov Decision Processes
2.2 Probabilistic Computation Tree Logic (PCTL)
3 Probabilistic Bisimulation for Interval MDPs
3.1 Compositional Reasoning
4 Hardness and Tractability
4.1 Decision Algorithm
5 Concluding Remarks
References
A Weighted MSO Logic with Storage Behaviour and Its Büchi-Elgot-Trakhtenbrot Theorem
1 Introduction
2 Preliminaries
3 Weighted Automata with Storage
4 Weighted Logic with Storage Behaviour
5 Results
References
Automata and Words
Colored Nested Words
1 Introduction
2 Colored Nested Words
3 Regularity
4 Colored Nested Word Automata
5 Equivalent Models
6 Closure Properties and Decision Problems
7 Grammar Characterization
References
Input-Driven Queue Automata with Internal Transductions
1 Introduction
2 Preliminaries
3 Closure Properties
4 Determinization
5 Decidability Questions
References
Periodic Generalized Automata over the Reals
1 Introduction
2 Periodic GKL Automata
3 Decidability
4 Structural Results
5 Further Questions
References
Minimal Separating Sequences for All Pairs of States
1 Introduction
2 Preliminaries
2.1 Partition Refinement
2.2 Splitting Trees and Refinable Partitions
3 Minimal Separating Sequences
4 Optimizing the Algorithm
5 Application in Conformance Testing
6 Experimental Results
7 Conclusion
References
Forkable Regular Expressions
1 Introduction
2 Preliminaries
3 Behaviors
4 Derivatives
5 Well-Behaved Behaviors
6 Related Work
References
On the Levenshtein Automaton and the Size of the Neighbourhood of a Word
1 Introduction
2 Definition and Construction of the Deterministic Universal Levenshtein Automaton
2.1 Preliminaries and Notations
2.2 Bit Vector Representation
2.3 Construction of the Nondeterministic Universal Levenshtein Automaton
2.4 Construction of the Deterministic Universal Levenshtein Automaton
3 Application to the Neighbourhood Counting Problem
3.1 A DFA for Encod(P,k)
3.2 Back to the Counting Problem
4 Conclusion
References
Combinatorics on Words
Parallelogram Morphisms and Circular Codes
1 Introduction
2 Words and Codes
3 Discrete Paths and Graphs
4 Parallelogram Networks
5 Main Result
6 Concluding Remarks
References
On Del-Robust Primitive Partial Words with One Hole
1 Introduction
2 Preliminaries
3 Del-Robust Primitive Partial Words with One Hole
4 Context-Freeness of Qp 1D
5 Counting n-Length Words in Qp1D
6 Conclusions
References
Optimal Bounds for Computing -gapped Repeats
1 Introduction
2 Number of Maximal Repeats and Subrepetitions
3 Computing All Maximal -gapped Repeats
4 Concluding Remarks
References
Complexity
On XOR Lemma for Polynomial Threshold Weight and Length
1 Introduction
2 Preliminaries
3 Upper Bounds on the Length of XOR of ANDs
4 The XOR Lemma for PTF Weight
5 Concluding Remarks
References
The Beachcombers' Problem: Walking and Searching from an Inner Point of a Line
1 Introduction
1.1 Related Work
1.2 Outline of the Paper
2 Preliminaries
2.1 Starting from an Endpoint
2.2 Starting from an Inner Point
3 Searching a Line Segment Starting from an Inner Point
3.1 Mobile Agents Which Cannot Turn Back
3.2 Mobile Agents Which Can Return to the Starting Point Instantaneously
3.3 Mobile Agents Which Can Turn Back
3.4 An Algorithm for Identical Agents Which Can Turn Back
4 Conclusions and Open Problems
References
Using Duality in Circuit Complexity
1 Introduction
2 Constant Size Circuits Families
3 The Block Product for Varieties of Languages
4 Duality and the Block Product
5 Equations for the Block Product
6 Conclusion
References
The Minimum Entropy Submodular Set Cover Problem
1 Introduction
2 Preliminaries
3 Minimum Entropy Submodular Set Cover: Definition, Special Cases and Applications
3.1 The Greedy Algorithm
4 Main Result and Definition of the Covering Coefficient
5 Proof of Main Result
6 Applications: Special Cases with =1
7 Network Flow Interpretation of and a Multistage Approach
8 Application to MEST
9 Conclusions and Open Problems
References
On the Capacity of Capacitated Automata
1 Introduction
2 Preliminaries
3 Closure Constructions
4 Decision Procedures
5 Conclusion and Future Work
References
On Limited Nondeterminism and ACC Circuit Lower Bounds
1 Introduction
2 A Consequence of the Inclusion EXP ACC0
3 An Exponential Size-Depth Tradeoff for ENP[2nc]
References
The Complexity of Induced Tree Reconfiguration Problems
1 Introduction
2 Preliminaries
2.1 Graphs
2.2 Reconfiguration Problem
3 PSPACE-Completeness
3.1 3SAT Reconfiguration Problem
3.2 Polynomial-Time Reduction
3.3 Token Sliding Case
3.4 Maximal Induced Tree Reconfiguration Problem
4 W[1]-Hardness
5 Fixed Parameter Tractability
6 Conclusion
References
Grammars
The Missing Case in Chomsky-Schützenberger Theorem
1 Introduction
2 Preliminaries
3 Homomorphic Characterization
4 Relation with Medvedev Theorem and Conclusion
References
Homomorphic Characterizations of Indexed Languages
1 Introduction
2 Epsilon-Reducible Context-Free Languages
2.1 Free Groups and Dyck Languages
2.2 -Reducible Context-Free Languages and Grammars
2.3 A Chomsky--Schützenberger-like Theorem for -CFLs
2.4 Related Works
3 Epsilon-Reducible Context-Free Transductions
3.1 Transductions
3.2 -Reducible Context-Free Transductions and Transducers
4 Characterizations of Indexed Languages
4.1 Indexed Grammars and Languages
4.2 Characterizations of Indexed Languages
References
Ogden's Lemma, Multiple Context-Free Grammars, and the Control Language Hierarchy
1 Introduction
2 Preliminaries
2.1 Multiple Context-Free Grammars
2.2 The Control Language Hierarchy
3 The Failure of Ogden's Lemma for Well-Nested MCFGs and 2-MCFGs
4 A Generalized Ogden's Lemma for a Subclass of the MCFGs
5 Relation to the Control Language Hierarchy
6 Conclusion
References
Grammatical Inference, Algorithmic Learning, and Patterns
Steganography Based on Pattern Languages
1 Introduction
1.1 Our Contributions
2 Basics and Notations
2.1 Steganography
2.2 Cryptographic Primitives
2.3 Pattern Languages
3 Steganography Using Patterns
3.1 Coding Bits by Random Subsets
3.2 Bounding the Rank of Matrices Obtained by Random Assignments of Intermediate Patterns
3.3 Modifying Strings of a Pattern Language to Embed Secrets
3.4 Sampling a Pattern Channel
3.5 A Secure Stegosystem for Pattern Channels
References
Inferring a Relax NG Schema from XML Documents
1 Introduction
2 Preliminaries
3 Inference of an NRHG from Trees
3.1 Primitive NRHG Construction
3.2 Grammar Optimization by Merging Indistinguishable Variables
3.3 Genetic Algorithm
4 Converting NRHG into Relax NG Schema
4.1 Horizontal NFA Construction
4.2 State Elimination for Obtaining Regular Expressions
4.3 Schema Refinement
5 Experimental Results
5.1 Experimental Setup
5.2 Size Reduction of NRHGs by Optimization
5.3 Precision of Inferred Schema
6 Conclusions
References
Noise Free Multi-armed Bandit Game
1 Introduction
2 Problem Setting
3 Adversary's Strategy
4 Lower Loss Bound
5 Concluding Remark
References
Graphs, Trees, and Weighted Automata
Properties of Regular DAG Languages
1 Introduction
2 Regular DAG Languages
3 Closure Properties
4 Necessary Properties of Regular DAG Languages
5 Finiteness
6 Conclusion
References
Normal Form on Linear Tree-to-Word Transducers
1 Introduction
2 Preliminaries
3 Earliest Linear Transducers
4 Reordering in Earliest Transducers
4.1 Reordering Erasing States
4.2 Reordering Producing States
5 Myhill-Nerode Theorem and Normal Form
6 Conclusion and Future Work
References
A Kleene Theorem for Weighted Tree Automata over Tree Valuation Monoids
1 Introduction
2 Trees and Tree Valuation Monoids
3 Rational Operations and Rational Tree Series
4 Weighted Tree Automata over Cutv-Monoids
5 From Automata to Rational Expressions and Vice Versa
References
Hankel Matrices for Weighted Visibly Pushdown Automata
1 Introduction and Background
1.1 Weighted Automata for Words and Nested Words
1.2 Hankel Matrices and Weighted Word Automata
1.3 Our Contribution
2 Preliminaries
2.1 Well-Nested Words
2.2 Nested Hankel Matrices
2.3 Weighted Visibly Pushdown Automata
3 Applications in Computational Learning Theory
3.1 Learning Weighted Visibly Pushdown Automata
4 Extension to Semirings
5 The Characterization of WVPA-Recognizability
5.1 Recognizability Implies Finite Rank of Nested Hankel Matrix
5.2 Finite Rank of Nested Hankel Matrix Implies Recognizability
References
Linear Context-Free Tree Languages and Inverse Homomorphisms
1 Introduction
2 Preliminaries
3 The Tree Language L
4 Derivation Trees
5 Dyck Words and Sequences of Chains
6 A Witness for L(G) =L
7 Conclusion
References
Language Varieties and Semigroups
Scalar Ambiguity and Freeness in Matrix Semigroups over Bounded Languages
1 Introduction
1.1 Probabilistic Finite Automata
2 Scalar Ambiguity and Freeness for Matrices
3 Ambiguity and Freeness over a Bounded Language
4 Conclusion
References
The Word Problem for HNN-extensions of Free Inverse Semigroups
1 Preliminaries
2 Effectiveness Analysis
3 The Word Problem for HNN-extensions of Free Inverse Semigroups
References
Parsing
Between a Rock and a Hard Place -- Uniform Parsing for Hyperedge Replacement DAG Grammars
1 Introduction
2 Preliminaries
3 Restricted DAG Grammars
4 A Polynomial Time Algorithm
5 Representing and Generating AMRs
6 NP-Hardness Results
7 Future Work
References
An Error Correcting Parser for Context Free Grammars that Takes Less Than Cubic Time
1 Introduction
2 A Simple Error Correcting Parser
2.1 Construction of a Covering Grammar
2.2 The Algorithm
3 Less Than Cubic Time Parser
4 Conclusions
References
System Analysis and Program Verification
Accurate Approximate Diagnosability of Stochastic Systems
1 Introduction
2 Specification of Diagnosability
2.1 Probabilistic Labelled Transition Systems
2.2 Partial Observation and Ambiguity
2.3 Fault Diagnosis
3 Analysis of Approximate Diagnosability
4 Conclusion
References
Proof--Based Synthesis of Sorting Algorithms for Trees
1 Introduction
1.1 Related Work
2 The Proof-Based Synthesis Method
2.1 Our Approach
2.2 Induction Principles
2.3 Special Inference Rules and Proof Strategies
3 Experiments
3.1 Synthesis of Sort-1
3.2 Additional Certification of the Synthesized Algorithm F1
3.3 Synthesis of Other Sorting Algorithms
4 Conclusions and Further Work
References
Unconventional Models of Computation
Reversible Shrinking Two-Pushdown Automata
1 Introduction
2 Preliminaries
3 On the Accepting Power of RTPDAs
3.1 Basic Results on RTPDAs
3.2 Separation of DTPDAs and RTPDAs
3.3 RevCRL is Incomparable with DCFL and CFL
4 Decidability Problems
References
Reachability in Resource-Bounded Reaction Systems
1 Introduction
2 Basic Notions
3 Inhibitorless Classes RS(,0) and RS(2,0)
4 Reactantless Classes RS(0,1) and RS(0,)
5 Single-Reactant Inhibitorless Class RS(1,0)
6 Conclusions
References
Canonical Multi-target Toffoli Circuits
1 Introduction
2 Reversible Circuits
2.1 Reversible Functions
2.2 Reversible Circuits
3 Multi-target Toffoli Circuits
4 Sequentialization, Parallelization and Shift
5 Waiting Degree
6 Canonical Circuits
7 Conclusion
References
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Language and Automata Theory and Applications

Description

More details

Other editions

Additional editions

Content

System requirements