Descriptional Complexity of Formal Systems
25th IFIP WG 1.02 International Conference, DCFS 2023, Potsdam, Germany, July 4-6, 2023, Proceedings
Published on 30. May 2023
Book
Paperback/Softback
XVI, 197 pages
978-3-031-34325-4 (ISBN)
Description
This book constitutes the proceedings of the 25th International Conference on Descriptional Complexity of Format Systems, DCFS 2023, which took place in Potsdam, Germany, in July 2023.
The 14 full papers, including one invited presentation as a full paper, presented in this volume were carefully reviewed and selected from 16 submissions. The conference focus on all aspects of descriptional complexity, including automata, grammars, languages, and other formal systems; various modes of operations and complexity measures.
More details
Series
Edition
1st ed. 2023
Language
English
Place of publication
Cham
Switzerland
Publishing group
Springer International Publishing
Target group
Professional and scholarly
Illustrations
29 s/w Abbildungen, 13 farbige Abbildungen
XVI, 197 p. 42 illus., 13 illus. in color.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 12 mm
Weight
335 gr
ISBN-13
978-3-031-34325-4 (9783031343254)
DOI
10.1007/978-3-031-34326-1
Schweitzer Classification
Other editions
Additional editions
Henning Bordihn | Nicholas Tran | György Vaszil
Descriptional Complexity of Formal Systems
25th IFIP WG 1.02 International Conference, DCFS 2023, Potsdam, Germany, July 4-6, 2023, Proceedings
E-Book
06/2023
Springer
€64.19
Available for download
Content
Operational State Complexity Revisited: the Contribution of Monsters and Modifiers.- Hypercubes and Isometric Words based on Swap and Mismatch Distance.- Defying Gravity and Gadget Numerosity: The Complexity of the Hanano Puzzle.- Existential and Universal Width of Alternating Finite Automata.- On Jaffe's Pumping Lemma, Revisited .- Operational Complexity: NFA-to-DFA Trade-Off.- The Word Problem for Finitary Automaton Groups.- Separating Words Problem over Groups.- Complexity of Exclusive Nondeterministic Finite Automata.- Shortest Accepted Strings for Two-Way Finite Automata: Approaching the Lower Bound.- Pushdown and One-Counter Automata: Constant and Non-Constant Memory Usage.- Construction of a Bi-Infinite Power Free Word with a Given Factor and a Non-Recurrent Letter.- Merging two Hierarchies of External Contextual Grammars with Subregular Selection.- A Tight Upper Bound on the Length of Maximal Bordered Box Repetition-Free Words.