Developments in Language Theory

Name: Developments in Language Theory | 26th International Conference, DLT 2022, Tampa, FL, USA, May 9-13, 2022, Proceedings
Brand: Springer
Price: 80.24 EUR
Availability: OnlineOnly

26th International Conference, DLT 2022, Tampa, FL, USA, May 9-13, 2022, Proceedings

Volker Diekert Mikhail Volkov(Herausgeber*in)

Springer (Verlag)

Erschienen am 8. Mai 2022

XVIII, 325 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-031-05578-2 (ISBN)

80,24 €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
Abstracts of Invited Talks
Algebraic Methods for Periodicity in Multidimensional Symbolic Dynamics
Non-deterministic Transducers
Origin-Equivalence for Macro Tree Transducers
Contents
Invited Talks
Can Formal Languages Help Pangenomics to Represent and Analyze Multiple Genomes?
1 Introduction
2 Preliminaries
3 Lyndon Words and Lyndon-Based Factorization
3.1 Some Applications: Representing and Querying Read Sequences
4 Sample Specific Strings and Structural Variations in Human Genome
5 Open Problems
References
Word Equations in the Context of String Solving
1 Introduction
2 String Solving
3 A Closer Look at Solution-Sets
3.1 Parametric Solutions
3.2 Graph Representations of Solution-Sets
3.3 Nielsen Transformations
3.4 Restricted Word Equations
4 Conclusions
References
A Survey on Delegated Computation
1 Introduction
2 Model and Definitions
3 Delegated Computation of Ring Multiplication
3.1 Algebraic Setting
3.2 An Example Protocol
3.3 Related Work
4 Delegated Computation of Group Exponentiation
4.1 Algebraic Setting and Preliminaries
4.2 An Example Protocol
4.3 Related Work
5 Delegation of Pairings
5.1 Algebraic Setting
5.2 An Example Protocol
5.3 Related Work
6 Conclusions and Directions for Future Research
References
Regular Papers
Checking Regular Invariance Under Tightly-Controlled String Modifications
1 Introduction
2 Preliminaries
3 Model
4 Complexity of the Invariance-Checking Problem
5 Invariance-Checking : Special Case
6 Conclusions and Future Work
References
Deciding Atomicity of Subword-Closed Languages
1 Introduction
2 Main Result
3 Concluding Remarks and Open Problems
References
Prefix Palindromic Length of the Sierpinski Word
1 Introduction
2 Definitions, Notation, Known Results
3 Auxiliary Functions qj(n)
4 Function q and Its First Differences
5 Difference Between p(n) and q(n)
6 First Differences of p(n)
References
Preservation of Normality by Unambiguous Transducers
1 Introduction
2 Basic Definitions
2.1 Normality
2.2 Automata and Transducers
2.3 Weighted Automata
3 Results
4 Markov Chain of an Unambiguous Automaton
5 Sketches of Proofs
6 Conclusion
References
A Full Characterization of Bertrand Numeration Systems
1 Introduction
2 Basic Notation
3 Characterization of Bertrand Numeration Systems
4 Linear Bertrand Numeration Systems
5 Lexicographically Greastest Words of Each Length
6 The Non-canonical -shift
References
On the Decidability of Infix Inclusion Problem
1 Introduction
2 Preliminaries
3 IIP on Finite Languages
4 IIP on Infinite Languages
5 Conclusions
References
Column Representation of Sturmian Words in Cellular Automata
1 Introduction
2 Preliminaries
2.1 Words
2.2 Continued Fraction Expansion
2.3 Standard Sequences and Directed Sequences
3 Cellular Automata
4 Construction of Numbers
5 Construction of Prefixes
6 Conclusions
References
Logarithmic Equal-Letter Runs for BWT of Purely Morphic Words
1 Introduction
2 Preliminaries
3 BWT-Highly Compressible Morphisms
4 Upper and Lower Bounds for rbwt
4.1 Combinatorial Structure of Binary Morphisms
4.2 Logarithmic Bounds for rbwt in Case of Binary Morphisms
5 Conclusions and Further Work
References
On Perfect Coverings of Two-Dimensional Grids
1 Introduction and Preliminaries
2 Line Polynomial Factors
3 Perfect Coverings
3.1 Infinite Grids
3.2 General Convex Neighborhoods
4 Algorithmic Aspects
References
Automata-Theoretical Regularity Characterizations for the Iterated Shuffle on Commutative Regular Languages
1 Introduction
2 Preliminaries
3 Type I Languages
4 Type II Languages
5 Automata-Theoretical Characterizations
6 Decision Problems
7 Conclusion
References
On the Complexity of Decision Problems for Counter Machines with Applications to Coding Theory
1 Introduction
2 Preliminaries
3 Complexity of Decision Problems for Restrictions of 2NCM
3.1 The Non-emptiness Problem
3.2 Other Decision Problems
4 Complexity of k-Infix-Freeness of Languages
5 Generalizations of k-Infix-Freeness
References
Visit-Bounded Stack Automata
1 Introduction
2 Preliminaries
2.1 Stack Automata
3 Visit-Bounded Automata
4 Semilinearity
5 Other Expensive Instruction Sets
References
Well Quasi-Orders Arising from Finite Ordered Semigroups
1 Introduction
2 Preliminaries
3 What Makes an Ordered Semigroup Congenial
4 Effective Characterization of the Class C
5 Other Necessary and Sufficient Conditions
6 Conclusion
References
The Billaud Conjecture for 69640972 86418188 = 4, and Beyond
1 Introduction
2 Preliminaries
3 Languages of Fixed Points and Their Parents
4 A `Blueprint' for a Billaud Conjecture Proof for Fixed
5 A Proof for the Billaud Conjecture for 69640972 86418188 = 4
References
Weighted Tree Automata with Constraints
1 Introduction
2 Preliminaries
3 Weighted Tree Grammars with Constraints
4 Closure Properties
5 Towards HOM Problem
References
Performing Regular Operations with 1-Limited Automata
1 Introduction
2 Preliminaries
3 Product and Kleene Star
3.1 Simulations of Operations on
3.2 Simulations of Operations on
4 Union, Intersection, and Complementation
4.1 Simulations of Operations on
4.2 Simulations of Operations on
5 Reversal
References
Binomial Complexities and Parikh-Collinear Morphisms
1 Introduction
1.1 Binomial Coefficients and Complexity Functions
1.2 Questions Addressed in This Paper
2 Several Answers to Question A
3 An Interlude: Parikh-Collinear Morphisms
3.1 A Characterization of Parikh-Collinear Morphisms
3.2 Proof of Theorem 10
4 Binomial Properties of the Thue-Morse Morphism
4.1 The First k Binomial Complexities
4.2 The (k+1)-Binomial Complexity
5 Answer to Question B and Beyond
References
Rational Index of Languages with Bounded Dimension of Parse Trees
1 Introduction
2 Definitions
3 Upper Bound on the Rational Index
4 Lower Bound on the Rational Index
5 Rational Indices for Some Language Families
6 Conclusion and Open Problems
References
Measuring Power of Locally Testable Languages
1 Introduction
2 Preliminaries
2.1 Density of Formal Languages
2.2 Measurability of Formal Languages
2.3 Fragments of Star-Free Languages
3 Measuring Power of Locally Testable Languages
4 Measuring Power of Alphabet and Piecewise Testable Languages
5 Summary and Future Work
References
The Power Word Problem in Graph Products
1 Introduction
2 Preliminaries
3 Cyclic Normal Forms and Conjugacy
4 The Power Word Problem in Graph Products
References
On One-Counter Positive Cones of Free Groups
1 Introduction
2 One-Counter Languages and Bi-infinite Words
3 Free Groups and Bi-infinite Words
4 The Space of Orders Defined by Spaced Words
References
Kolmogorov Complexity Descriptions of the Exquisite Behaviors of Advised Deterministic Pushdown Automata
1 Background and Our Challenges
1.1 Kolmogorov Complexity Approaches to Formal Languages
1.2 Advice-Aided Languages and Pumping Lemmas
1.3 Overview of Main Contributions
2 Preparation: Notions and Notation
2.1 Numbers, Alphabets, Languages, etc.
2.2 One-Way Deterministic Pushdown Automata
2.3 Kolmogorov Complexity Primer
3 Advised Computation
4 Kolmogorov Complexity Approach
4.1 Key Lemma - KC-DCFL/n Lemma
4.2 Applications of the KC-DCFL/n Lemma
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken