Developments in Language Theory

Name: Developments in Language Theory | 23rd International Conference, DLT 2019, Warsaw, Poland, August 5-9, 2019, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

23rd International Conference, DLT 2019, Warsaw, Poland, August 5-9, 2019, Proceedings

Piotrek Hofman Michal Skrzypczak(Herausgeber*in)

Springer (Verlag)

Erschienen am 24. Juli 2019

X, 319 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-030-24886-4 (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

Intro
Preface
Organization
Contents
Invited Papers
Inherent Size Blowup in -Automata
1 Introduction
2 -Automata and Their Acceptance Conditions
3 Succinctness
4 Boolean Operations and Decision Problems
5 Hyper-dual
6 Conclusions
References
Deciding Context Unification (with Regular Constraints)
1 Introduction
2 Definitions
2.1 Trees
2.2 Patterns
2.3 Context Unification: Formal Statement
3 Local Compression of Trees
3.1 Compression Operations
3.2 Compression of Non-crossing Patterns
4 Uncrossing
4.1 Uncrossing a Pair
4.2 Uncrossing Chains
4.3 Uncrossing Father-Leaf Subpattern
5 The Algorithm
6 Space Bounds
6.1 General Bounds
6.2 Strategy
7 Detailed Example
8 Regular Constraints
8.1 Tree Automata
8.2 Context Unification with Regular Constraints
8.3 Modifications of ContextEqSat
9 Open Questions
References
Single-Stranded Architectures for Computing
1 Introduction
2 Single-Stranded Architectures for Computing in Oritatami
2.1 A Single-Stranded Architecture for Counting in Binary
2.2 Arithmetic Overflow and Infinite Binary Counter.
2.3 Applications of the Binary Counter
3 Towards Algorithmic Programming of Oritatami Systems
3.1 Programmability of Modules: Self-standing Shape and Steric Hindrance
3.2 Towards Algorithmic Design of Folding Pathways
4 Conclusions
References
Regular Papers
A Linear Bound on the K-Rendezvous Time for Primitive Sets of NZ Matrices
1 Introduction
2 Notation and Preliminaries
3 The K-Rendezvous Time and a Recurrence Relation for Its Upper Bound
4 Solving the Recurrence
5 Numerical Results
6 Conclusions
References
Words of Minimum Rank in Deterministic Finite Automata
1 Introduction
2 Main Definitions and Preliminary Results
3 Strongly Connected Automata
3.1 A Lower Bound for Ternary Automata
3.2 Lower Bounds for Binary Automata
3.3 Upper Bound in the Case When the Rank Equals the Period
4 Eulerian Automata
4.1 The Rank Conjecture
4.2 A Corollary for Circular Automata
4.3 A Road Coloring Algorithm
References
On the Length of Shortest Strings Accepted by Two-Way Finite Automata
1 Introduction
2 Two-Way Finite Automata
3 Upper Bound
4 Simple Lower Bound
5 Improved Lower Bound
6 Small Alphabets
7 On Improving the Estimation
References
Characterizing the Valuedness of Two-Way Finite Transducers
1 Introduction
2 Preliminaries
3 Some Properties of Bounded-Crossing 2FTs
4 Sufficient and Necessary Conditions for the Infinite-Valuedness of 2FTs
References
Input-Driven Pushdown Automata for Edit Distance Neighborhood
1 Introduction
2 Input-Driven Pushdown Automata
3 Edit Distance Neighborhood
4 Concluding Remarks
References
The Relative Edit-Distance Between Two Input-Driven Languages
1 Introduction
2 Preliminaries
3 Edit-Distance
4 Inclusion Problem for IDPDAs
5 Relative Edit-Distance Problem
6 Conclusions
References
On Shrinking Restarting Automata of Window Size One and Two
1 Introduction
2 Definitions and Notation
3 On Monotone Shrinking Restarting Automata
4 On Non-monotone Shrinking Restarting Automata
5 Conclusion
References
The Teaching Complexity of Erasing Pattern Languages with Bounded Variable Frequency
1 Introduction
2 Preliminaries
3 Teaching Dimension and Preference-Based Teaching Dimension
4 Simple Block-Regular Patterns
5 Finite Distinguishability of m-Quasi-Regular, Non-cross m-Regular and m-Regular Patterns
6 Conclusion
References
On Timed Scope-Bounded Context-Sensitive Languages
1 Introduction
2 Preliminaries
3 Dense-Time Visibly Pushdown Multistack Automata
3.1 Switching Vectors
4 Scope-Bounded ECMVPA and dt-ECMVPA
5 Logical Characterization of k-dt-ECMVPA
References
Logics for Reversible Regular Languages and Semigroups with Involution
1 Introduction
2 Logics with Between and Neighbour
2.1 MSO (bet), MSO (N) and FO (bet)
2.2 FO (N)
3 Semigroups with Involution
4 Conclusion
References
Eventually Safe Languages
1 Introduction
2 Definitions
2.1 Logic
2.2 Automata
3 The Original Family Ln
4 A Family of LTL-definable Languages Kn with Succinct GFG Representations
4.1 Definition of the Language Kn
4.2 Aperiodicity of Kn and Succinctness of GFG Automaton
5 A Modal Logic for Eventually Safe Properties
5.1 The Safety Logic STL
5.2 The Logic ETL for Eventually Safe Properties
5.3 Properties of the Class ESafe
5.4 A Succinct ETL Formula for the Language Kn
5.5 From ETL to GFG CoBüchi Automata
6 Conclusion
References
Coinductive Algorithms for Büchi Automata
1 Introduction
2 Coinductive Algorithms for Finite Automata
2.1 Deterministic Automata: Hopcroft and Karp's Algorithm
2.2 Non-deterministic Automata: HKC
3 From Büchi Automata to Finite Words Automata
4 HKC for Büchi Automata
5 Conclusion and Future Work
References
Hole-Free Partially Directed Animals
1 Introduction
2 Notation and Preliminaries
3 A Dynamical System for Columns
4 Exhaustive Generation
4.1 Data Structure
4.2 Complexity
5 Conclusions and Further Work
References
First Lower Bounds for Palindromic Length
1 Introduction
2 General Properties
3 Prefix Palindromic Length of the Thue-Morse Word
4 A Lower Bound for Toeplitz Morphisms
5 Words with Longer Powers
6 Conclusion
References
On Palindromic Length of Sturmian Sequences
1 Introduction
2 Preliminaries
3 Images of Sturmian Words
4 Proofs of Main Theorems
References
Separating Many Words by Counting Occurrences of Factors
1 Introduction
2 Preliminaries
3 Separating Sets of Factors
4 Infinite Words
5 Regular Languages
6 Conclusion
References
k-Spectra of Weakly-c-Balanced Words
1 Introduction
2 Preliminaries
3 Cardinalities of k-Spectra of Weakly-c-Balanced Words
4 Cardinalities of k-Spectra of Weakly-0-Balanced Words
5 Reconstructing Weakly-0-Balanced Words from Their k-Spectra
6 Conclusions
References
Computing the k-binomial Complexity of the Thue-Morse Word
1 Introduction
2 Basics
2.1 Binomial Coefficients and Binomial Equivalence
2.2 Context of This Paper
3 Occurrences of Subwords in Images by
4 Computing b`3´9`42`"?613A``45`47`"603At,2(n)
5 How to Cut Factors of the Thue-Morse Word
6 Types Associated with a Factor
7 k-binomial Complexity of the Thue-Morse Word
References
Context-Free Word Problem Semigroups
1 Introduction
2 Preliminaries
3 Examples
4 Relationship to Word-Hyperbolicity and Automaticity
5 Direct Products
6 Free Products
7 Strong Semilattices
8 Rees Matrix Semigroups
9 Bruck-Reilly Extensions
10 Further Open Problems
References
Analysis of Symbol Statistics in Bicomponent Rational Models
1 Introduction
2 Problem Setting
3 Primitive Models
4 Bicomponent Models
4.1 Equipotent Case
5 Conclusions
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken