Description 
1 online resource (xiv, 568 pages) : illustrations 
Series 
LNCS sublibrary. SL 1, Theoretical computer science and general issues 

Lecture notes in computer science ; 11088 

LNCS sublibrary. SL 1, Theoretical computer science and general issues.


Lecture notes in computer science ; 11088

Contents 
Block sortingbased transformations on words: beyond the magic BWT  The Runs Theorem and Beyond  A Brief Excursion to Parity Games  A tale of conjunctive grammars  Groups, languages and dendric shifts  Some Open Problems in Polyomino Tilings  Weak Cost Register Automata are Still Powerful  From TwoWay Transducers to Regular Function Expressions  Decidability of Right OneWay Jumping Finite Automata  Additive Number Theory via Approximation by Regular Languages  Treetograph transductions with scope  A Characterization of Completely Reachable Automata  Inequalities for onestep products  On the commutative equivalence of contextfree languages  Simon's theorem for scattered words  The Synchronizing Probability Function for Primitive Sets of Matrices  Recognizability for automata  SiteDirected Deletion  Counting Subwords and Regular Languages  Deque languages, automata and planar graphs  A General Approach to State Complexity of Operations: Formalization and Limitations  On Matching Generalised Repetitive Patterns  Intersection NonEmptiness and Hardness within Polynomial Time  Complexity of decision problems on totally rigid acyclic tree grammars  A Pattern Logic for Automata with Outputs  The Intersection Problem for Finite Semigroups  On Completely Reachable Automata and Subset Reachability  On Minimal Grammar Problems for Finite Languages  Reversible Pushdown Transducers  Twoway Automata and OneTape Machines: Read Only versus Linear Time  Dynamics of the Independence Number and Automata Synchronization  Closest Substring Problems for Regular Languages  Computational Complexity of Decision Problems on SelfVerifying Finite Automata  Generalizations of Checking Stack Automata: Characterizations and Hierarchies  On Counting Functions of Languages  Towards exact state complexity bounds for inputdriven pushdown automata  On Abelian Subshifts  Reachability Problems in Nondeterministic Polynomial Maps on the Integers  Projection for Büchi Tree Automata with Constraints between Siblings  The Computational Power of Parsing Expression Grammars  On finitely ambiguous Büchi automata  Uniformization Problem for Variants of First Order Logic over Finite Words  On deterministic ordered restartdelete automata  Complementation of Finitely Ambiguous Büchi Automata  A Structural Lemma for Deterministic ContextFree Languages 
Summary 
This book constitutes the proceedings of the 22nd International Conference on Developments in Language Theory, DLT 2018, held in Tokyo, Japan, in September 2018. The 39 full papers presented in this volume were carefully reviewed and selected from 84 submissions. The papers cover the following topics and areas: combinatorial and algebraic properties of words and languages; grammars, acceptors and transducers for strings, trees, graphics, arrays; algebraic theories for automata and languages; codes; efficient text algorithms; symbolic dynamics; decision problems; relationships to complexity theory and logic; picture description and analysis, polyominoes and bidimensional patterns; cryptography; concurrency; celluar automata; bioinspired computing; quantum computing 
Notes 
Includes author index 

International conference proceedings 

Online resource; title from PDF title page (SpringerLink, viewed September 7, 2018) 
Subject 
Formal languages  Congresses.

Genre/Form 
Conference papers and proceedings.


Conference papers and proceedings.

Form 
Electronic book

Author 
Hoshi, Mizuho, 1985 editor


Seki, Shinnosuke, editor

ISBN 
3319986546 (electronic bk.) 

9783319986548 (electronic bk.) 

(print) 
