[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Fundamentals of Computation Theory

23rd International Symposium, FCT 2021, Athens, Greece, September 12–15, 2021, Proceedings

  • Conference proceedings
  • © 2021

Overview

Editors:
  1. Evripidis Bampis

    1. Sorbonne University, Paris, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Aris Pagourtzis

    1. National Technical University of Athens, Athens, Greece

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 12867)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: FCT 2021.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

eBook USD 79.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 99.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

About this book

This book constitutes the proceedings of the 23rd International Symposium on Fundamentals of Computation Theory, FCT 2021, held in Athens, Greece, in September 2021. The 30 full papers included in this volume were carefully reviewed and selected from 94 submissions. In addition, the book contains 2 invited talks. The papers cover topics of all aspects of theoretical computer science, in particular algorithms, complexity, formal and logical methods.


Similar content being viewed by others

Keywords

Table of contents (32 papers)

  1. Front Matter

    Pages i-xix
    Download chapter PDF

  2. Invited Papers

    1. Front Matter

      Pages 1-1
      Download chapter PDF

    2. Two-Sided Matching Markets with Strongly Correlated Preferences

      • Hugo Gimbert, Claire Mathieu, Simon Mauras
      Pages 3-17

    3. Communicating Finite State Machines and an Extensible Toolchain for Multiparty Session Types

      • Nobuko Yoshida, Fangyi Zhou, Francisco Ferreira
      Pages 18-35

  3. Contributed Papers

    1. Front Matter

      Pages 37-37
      Download chapter PDF

    2. First-Order Logic and Its Infinitary Quantifier Extensions over Countable Words

      • Bharat Adsul, Saptarshi Sarkar, A. V. Sreejith
      Pages 39-52

    3. From Symmetry to Asymmetry: Generalizing TSP Approximations by Parametrization

      • Lukas Behrendt, Katrin Casel, Tobias Friedrich, J. A. Gregor Lagodzinski, Alexander Löser, Marcus Wilhelm
      Pages 53-66

    4. A Poly-log Competitive Posted-Price Algorithm for Online Metrical Matching on a Spider

      • Max Bender, Jacob Gilbert, Kirk Pruhs
      Pages 67-84

    5. Computational Complexity of Covering Disconnected Multigraphs

      • Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, Michaela Seifrtová
      Pages 85-99

    6. The Complexity of Bicriteria Tree-Depth

      • Piotr Borowiecki, Dariusz Dereniowski, Dorota Osula
      Pages 100-113

    7. TS-Reconfiguration of Dominating Sets in Circle and Circular-Arc Graphs

      • Nicolas Bousquet, Alice Joffard
      Pages 114-134

    8. Bipartite 3-Regular Counting Problems with Mixed Signs

      • Jin-Yi Cai, Austen Z. Fan, Yin Liu
      Pages 135-148

    9. The Satisfiability Problem for a Quantitative Fragment of PCTL

      • Miroslav Chodil, Antonín Kučera
      Pages 149-161

    10. Beyond the BEST Theorem: Fast Assessment of Eulerian Trails

      • Alessio Conte, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Giulia Punzi
      Pages 162-175

    11. Linear-Time Minimal Cograph Editing

      • Christophe Crespelle
      Pages 176-189

    12. Regular Model Checking with Regular Relations

      • Vrunda Dave, Taylor Dohmen, Shankara Narayanan Krishna, Ashutosh Trivedi
      Pages 190-203

    13. Minimum Consistent Subset Problem for Trees

      • Sanjana Dey, Anil Maheshwari, Subhas C. Nandy
      Pages 204-216

    14. Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes

      • David Eppstein, Siddharth Gupta, Elham Havvaei
      Pages 217-229

    15. The Space Complexity of Sum Labelling

      • Henning Fernau, Kshitij Gajjar
      Pages 230-244

    16. On Minimizing Regular Expressions Without Kleene Star

      • Hermann Gruber, Markus Holzer, Simon Wolfsteiner
      Pages 245-258
Back to top

Other volumes

  1. Fundamentals of Computation Theory

Editors and Affiliations

  • Sorbonne University, Paris, France

    Evripidis Bampis

  • National Technical University of Athens, Athens, Greece

    Aris Pagourtzis

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation