Amazon cover image
Image from Amazon.com

Descriptional complexity of formal systems : 22nd International Conference, DCFS 2020, Vienna, Austria, August 24-26, 2020, Proceedings / Galina Jirásková, Giovanni Pighizzini, (eds.).

By: Contributor(s): Material type: TextTextSeries: Lecture notes in computer science ; 12442. | LNCS sublibrary. SL 1, Theoretical computer science and general issues.Publisher: Cham, Switzerland : Springer, [2020]Description: 1 online resource (x, 245 pages) : illustrations (some color)Content type:
  • text
Media type:
  • computer
Carrier type:
  • online resource
ISBN:
  • 9783030625368
  • 3030625362
Other title:
  • DCFS 2020
Subject(s): Genre/Form: Additional physical formats: Print version:: No titleDDC classification:
  • 005.131 23
LOC classification:
  • QA76.9.L63
  • QA76.5913
Online resources:
Contents:
Intro -- Preface -- Organization -- Contents -- Mutually Accepting Capacitated Automata -- 1 Introduction -- 2 Preliminaries -- 3 Expressive Power -- 3.1 Regularity -- 3.2 Determinism -- 3.3 Closure Properties -- 4 Decision Problems -- References -- Bad Pictures: Some Structural Properties Related to Overlaps -- 1 Introduction -- 2 Preliminaries -- 2.1 Basic Notions and Results on Strings -- 2.2 Basic Notions on Pictures -- 3 Good and Bad Pictures -- 4 Index of Bad Pictures -- References -- Regular Expression Length via Arithmetic Formula Complexity -- 1 Introduction -- 2 Preliminaries
3 Reduction to Monotone Arithmetic Formula Size -- 3.1 Bounds for Uniform Languages -- 3.2 Blow-Up of Language Operations -- 3.3 Limitations of the Arithmetic Bound -- 4 Direct Lower Bounds -- 4.1 The Divisibility Language -- 4.2 Utilizing Noncommutativity -- 5 Conclusion -- References -- Crisp-Determinization of Weighted Tree Automata over Additively Locally Finite and Past-Finite Monotonic Strong Bimonoids Is Decidable -- 1 Introduction -- 2 Preliminaries -- 2.1 General Notions and Notations -- 2.2 Trees and Contexts -- 2.3 Strong Bimonoids -- 3 Weighted Tree Automata with Run Semantics
4 Pumping Lemma -- 5 Main Result -- References -- On the Power of Generalized Forbidding Insertion-Deletion Systems -- 1 Introduction -- 2 Important Definitions -- 3 Main Results -- 4 Conclusions -- References -- State Complexity Bounds for the Commutative Closure of Group Languages -- 1 Introduction -- 2 Prerequisites -- 2.1 Unary Languages -- 3 Results -- 3.1 Intuition, Method of Proof and Main Results -- 3.2 A Regularity Condition by Decomposing into Unary Automata -- 3.3 The Special Case of Group Languages -- 4 Conclusion -- References
Multiple Concatenation and State Complexity (Extended Abstract) -- 1 Introduction -- 2 Preliminaries -- 3 Construction of NFAs for Multiple Concatenation -- 4 Tightness for a (k+1)-letter Alphabet -- 5 Tightness for a k-letter Alphabet -- 6 Binary and Ternary Languages -- 7 Unary Cyclic Languages -- 8 Conclusions -- References -- Combining Limited Parallelism and Nondeterminism in Alternating Finite Automata -- 1 Introduction -- 2 Preliminaries -- 2.1 Tree Width of Alternating Machines -- 3 Decision Problems -- 4 Width Measure Bounds -- References
Longer Shortest Strings in Two-Way Finite Automata -- 1 Introduction -- 2 Definitions -- 3 Shortest Strings in 2DFA -- 4 Iterating Semi-direction-determinate Automata -- 5 Encoding in a Fixed Alphabet -- 6 Automata with Longer Shortest Strings -- 7 Transforming Semi-direction-determinate to One-Way -- 8 Conclusion -- References -- Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Motion -- 1 Introduction -- 2 Definitions and Preliminaries -- 3 Complexity of Mutual Nondeterministic Simulations -- 4 Costs of Simulations Involving Deterministic Devices
Summary: This book constitutes the proceedings of the 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020, which was supposed to take place in Vienna, Austria, in August 2020, but the conference was canceled due to the COVID-19 crisis. The 19 full papers presented in this volume were carefully reviewed and selected from 31 submissions. They deal with all aspects of descriptional complexity and costs of description of objects in various computational models, such as Turing machines, pushdown automata, finite automata, grammars, and others.
Holdings
Item type Current library Collection Call number Status Date due Barcode Item holds
eBook eBook e-Library eBook LNCS Available
Total holds: 0

This book constitutes the proceedings of the 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020, which was supposed to take place in Vienna, Austria, in August 2020, but the conference was canceled due to the COVID-19 crisis. The 19 full papers presented in this volume were carefully reviewed and selected from 31 submissions. They deal with all aspects of descriptional complexity and costs of description of objects in various computational models, such as Turing machines, pushdown automata, finite automata, grammars, and others.

Includes author index.

Online resource; title from PDF title page (SpringerLink, viewed January 27, 2021).

Intro -- Preface -- Organization -- Contents -- Mutually Accepting Capacitated Automata -- 1 Introduction -- 2 Preliminaries -- 3 Expressive Power -- 3.1 Regularity -- 3.2 Determinism -- 3.3 Closure Properties -- 4 Decision Problems -- References -- Bad Pictures: Some Structural Properties Related to Overlaps -- 1 Introduction -- 2 Preliminaries -- 2.1 Basic Notions and Results on Strings -- 2.2 Basic Notions on Pictures -- 3 Good and Bad Pictures -- 4 Index of Bad Pictures -- References -- Regular Expression Length via Arithmetic Formula Complexity -- 1 Introduction -- 2 Preliminaries

3 Reduction to Monotone Arithmetic Formula Size -- 3.1 Bounds for Uniform Languages -- 3.2 Blow-Up of Language Operations -- 3.3 Limitations of the Arithmetic Bound -- 4 Direct Lower Bounds -- 4.1 The Divisibility Language -- 4.2 Utilizing Noncommutativity -- 5 Conclusion -- References -- Crisp-Determinization of Weighted Tree Automata over Additively Locally Finite and Past-Finite Monotonic Strong Bimonoids Is Decidable -- 1 Introduction -- 2 Preliminaries -- 2.1 General Notions and Notations -- 2.2 Trees and Contexts -- 2.3 Strong Bimonoids -- 3 Weighted Tree Automata with Run Semantics

4 Pumping Lemma -- 5 Main Result -- References -- On the Power of Generalized Forbidding Insertion-Deletion Systems -- 1 Introduction -- 2 Important Definitions -- 3 Main Results -- 4 Conclusions -- References -- State Complexity Bounds for the Commutative Closure of Group Languages -- 1 Introduction -- 2 Prerequisites -- 2.1 Unary Languages -- 3 Results -- 3.1 Intuition, Method of Proof and Main Results -- 3.2 A Regularity Condition by Decomposing into Unary Automata -- 3.3 The Special Case of Group Languages -- 4 Conclusion -- References

Multiple Concatenation and State Complexity (Extended Abstract) -- 1 Introduction -- 2 Preliminaries -- 3 Construction of NFAs for Multiple Concatenation -- 4 Tightness for a (k+1)-letter Alphabet -- 5 Tightness for a k-letter Alphabet -- 6 Binary and Ternary Languages -- 7 Unary Cyclic Languages -- 8 Conclusions -- References -- Combining Limited Parallelism and Nondeterminism in Alternating Finite Automata -- 1 Introduction -- 2 Preliminaries -- 2.1 Tree Width of Alternating Machines -- 3 Decision Problems -- 4 Width Measure Bounds -- References

Longer Shortest Strings in Two-Way Finite Automata -- 1 Introduction -- 2 Definitions -- 3 Shortest Strings in 2DFA -- 4 Iterating Semi-direction-determinate Automata -- 5 Encoding in a Fixed Alphabet -- 6 Automata with Longer Shortest Strings -- 7 Transforming Semi-direction-determinate to One-Way -- 8 Conclusion -- References -- Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Motion -- 1 Introduction -- 2 Definitions and Preliminaries -- 3 Complexity of Mutual Nondeterministic Simulations -- 4 Costs of Simulations Involving Deterministic Devices

Powered by Koha