Descriptional Complexity of Formal Systems

26th IFIP WG 1.02 International Conference, DCFS 2025, Loughborough, UK, July 22–24, 2025, Proceedings

Andreas Malcher, Luca Prigioniero (Herausgeber)

Buch | Softcover

XXX, 225 Seiten

2025
Springer International Publishing (Verlag)
978-3-031-97099-3 (ISBN)

Artikel merken

This book constitutes the refereed proceedings of the 26th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2025, held in Loughborough, UK, during July 22 24, 2025.

This book includes 15 full papers, carefully reviewed and selected from 20 submissions, as well as 4 abstracts of the invited talks. The conference focus on all aspects of descriptional complexity, including automata, grammars, languages, and other formal systems; various modes of operations and complexity measures.

.- Fibonacci Pictures on a Binary Alphabet.

.- A Close Analysis of the Subset Construction.

.- k-local Graphs.

.- Word-Representable Graphs and Locality of Words.

.- Automata for Synchronised Shuffle on Backbones.

.- Two-Word Shuffle: Some Results.

.- Matrix Forbidding Grammars.

.- On the Decidability and Expressive Power of Several Theories Based on String Constraints.

.- Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals are Computationally Complete.

.- Disjunctive Complexity.

.- Two-Way Finite Automata with Translucent Input Letters.

.- Relative Densities of Formal Languages.

.- On A Measure for The Descriptional Complexity of Finite Automata with Translucent Words.

.- What is the Most Natural Generalization of the Pumping Lemmas for Regular and Context-Free Languages?.

.- Small Balanced Vertex Separators in NFA to Regular Expression Conversion.

Erscheinungsdatum	13.06.2025
Reihe/Serie	Lecture Notes in Computer Science
Zusatzinfo	XXX, 225 p. 29 illus., 14 illus. in color.
Verlagsort	Cham
Sprache	englisch
Maße	155 x 235 mm
Themenwelt	Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
Themenwelt	Informatik ► Weitere Themen ► Hardware
Schlagworte	Abstract Machines • Automata Theory • Computability • Computational Complexity • descriptional complexity • Formal Language Theory • formal systems • Models of Computation • Theory of Computation
ISBN-10	3-031-97099-3 / 3031970993
ISBN-13	978-3-031-97099-3 / 9783031970993
Zustand	Neuware