Overview

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.

Full Product Details

Author:   Henning Bordihn ,  Nicholas Tran ,  György Vaszil
Publisher:   Springer International Publishing AG
Imprint:   Springer International Publishing AG
Edition:   1st ed. 2023
Volume:   13918
Weight:   0.338kg
ISBN:  

9783031343254

ISBN 10:   3031343255
Pages:   197
Publication Date:   30 May 2023
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   Manufactured on demand  
We will order this item for you from a manufactured on demand supplier.

Table of Contents

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.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions