Fundamentals of Computation Theory : 24th International Symposium, FCT 2023, Trier, Germany, September 18-21, 2023, Proceedings / / Henning Fernau and Klaus Jansen, editors

• Pubblicazione: Cham, Switzerland : , : Springer, , [2023]; ©2023
• Edizione: First edition.
• Descrizione fisica: 1 online resource (450 pages)
• Disciplina: 004
• Soggetto topico: Computer science; Computer science - Mathematics
• Persona (resp. second.): FernauHenning; JansenKlaus
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: Intro -- Preface -- A Good Tradition -- The Newest Edition: Trier 2023 -- Highlights of the Conference -- Finally, Big Thanks … -- Organization -- Contents -- Convergence of Distributions on Paths -- 1 Introduction -- 2 Preliminaries -- 3 Umbrella Digraphs -- 4 Computing the Residual Matrix -- 5 Convergence of Distributions -- References -- Subhedge Projection for Stepwise Hedge Automata -- 1 Introduction -- 2 Preliminaries -- 3 Stepwise Hedge Automata (SHAs) -- 4 Downward Stepwise Hedge Automata (SHA"3223379 s) -- 5 Compiling SHAs to SHA"3223379 s with Projection States -- 6 Streaming Evaluators for SHA"3223379 s -- 7 Earliest Membership with Subhedge Projection -- 8 Experimental Evaluation -- 9 Conclusion and Future Work -- References -- The Rectilinear Convex Hull of Line Segments -- 1 Introduction -- 2 The Rectilinear Convex Hull -- 3 Rectilinear Convex Hull of Line Segments -- 3.1 Computing the -Wedges of Endpoints of Segments -- 3.2 Computing the -Wedges of the Points Inside the Segments -- 3.3 Computing -- 3.4 Rectilinear Convex Hull of a Set of Simple Polygons -- 4 Rectilinear Convex Hull of a Simple Polygonal Chain -- 5 Concluding Remarks -- References -- Domino Snake Problems on Groups -- 1 Introduction -- 2 Preliminaries -- 2.1 Symbolic Dynamics -- 2.2 Combinatorial Group Theory -- 3 Snake Behaviour -- 3.1 General Properties -- 4 Ossuary -- 4.1 Skeletons and Decidability -- 5 Snake Embeddings -- 6 Virtually Nilpotent Groups -- 7 Snakes and Logic -- References -- Parsing Unranked Tree Languages, Folded Once -- 1 Introduction -- 2 Preliminaries -- 3 Regular Tree Foldings -- 4 Unfolding Folded Trees -- References -- The Impact of State Merging on Predictive Accuracy in Probabilistic Tree Automata: Dietze's Conjecture Revisited -- 1 Introduction -- 2 Preliminaries -- 3 Dietze's Conjecture -- 4 Conclusion -- References. ; Computing Subset Vertex Covers in H-Free Graphs -- 1 Introduction -- 2 Preliminaries -- 3 NP-Hardness Results -- 4 Polynomial-Time Results -- 5 The Proof of Theorems 5 and 6 -- 6 Conclusions -- References -- On Computing Optimal Temporal Branchings -- 1 Introduction -- 2 Preliminaries -- 3 Temporal Branching and Preliminary Results -- 3.1 Temporal Out-Branching -- 3.2 Temporal In-Branching -- 4 Computing Maximum d-tobs for d {mt,st,ld} -- 4.1 Algorithm for mt -- 4.2 Algorithm for ld and st -- 5 Computing Maximum ft-tobs -- 6 Conclusions and Future Work -- References -- Contracting Edges to Destroy a Pattern: A Complexity Study -- 1 Introduction -- 2 Preliminaries -- 3 NP-Completeness -- 3.1 A General Reduction -- 3.2 Graphs with Universal Clique Separators -- 3.3 Stars and Small Graphs -- 3.4 Putting Them Together -- 4 W[2]-Hardness -- 4.1 A General Reduction for Trees -- 4.2 Stars and Bistars -- References -- Distance-Based Covering Problems for Graphs of Given Cyclomatic Number -- 1 Introduction -- 2 The General Method -- 3 Metric Dimension and Variants -- 4 Geodetic Sets and Variants -- 4.1 Geodetic Sets -- 4.2 Monitoring Edge-Geodetic Sets -- 4.3 Distance-edge-monitoring-sets -- 5 Path Covers and Variants -- 6 Algorithmic Consequences -- 7 Conclusion -- References -- An Efficient Computation of the Rank Function of a Positroid -- 1 Introduction -- 2 Preliminaries -- 3 The Rank-Function Algorithm -- 4 From Le-Diagram to Decorated Permutation -- 5 From Decorated Permutation to Le-Diagram -- 5.1 Removing Fixed Points -- 5.2 Filling the Bottom Row -- 5.3 Contracting an Element -- 6 Discussion -- References -- Minimizing Query Frequency to Bound Congestion Potential for Moving Entities at a Fixed Target Time -- 1 Introduction -- 1.1 The Query Model -- 1.2 Related Work -- 1.3 Our Results -- 2 Geometric Preliminaries. ; 3 Query Optimization at a Fixed Target Time -- 4 Towards Continuous Query Optimization -- 5 Discussion -- References -- Complexity of Conformant Election Manipulation -- 1 Introduction -- 2 Related Models -- 3 Preliminaries -- 3.1 Scoring Rules -- 3.2 Manipulative Actions -- 3.3 Computational Complexity -- 4 Conformant Manipulation -- 5 Conformant Bribery -- 6 Conclusion -- References -- -Factorization and the Binary Case of Simon's Congruence -- 1 Introduction -- 2 Preliminaries -- 3 -Factorization -- 4 The Binary Case of Simon's Congruence -- 5 Towards the Ternary Case of Simon's Congruence -- 6 Conclusion -- References -- Bounds for c-Ideal Hashing -- 1 Introduction -- 1.1 General Setting and Notation -- 1.2 Applications of Hashing -- 1.3 Theory of Hashing -- 1.4 Determinism Versus Randomization -- 1.5 Our Model and the Connection to Advice Complexity -- 1.6 Organization -- 2 Related Work and Contribution -- 3 General Bounds on Hc -- 4 Estimations for P(maxc) -- 4.1 Upper Bound -- 4.2 Lower Bound -- 5 Improvements for Edge Cases -- 6 Advice Complexity of Hashing -- 7 Conclusion -- References -- Parameterized Complexity of the -Free Edge Deletion Problem -- 1 Introduction -- 1.1 Notations and Definitions -- 1.2 Our Results -- 1.3 Review of Previous Work -- 2 W[1]-Hardness of -Free Edge Deletion Parameterized by Treewidth -- 3 -Free Edge Deletion on Planar Graphs -- 4 W[2]-Hardness of -Free Arc Deletion Parameterized by Solution Size -- 5 Conclusions and Open Problems -- References -- On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman -- 1 Introduction -- 2 Conclusion -- References -- The Complexity of (Pk, P)-Arrowing -- 1 Introduction and Related Work -- 2 Preliminaries -- 3 Polynomial-Time Cases -- 4 coNP-Complete Cases -- 4.1 Reductions -- 4.2 Existence of Transmitters -- 5 Conclusion and Future Work -- References. ; On Computing a Center Persistence Diagram -- 1 Introduction -- 2 Preliminaries -- 2.1 Persistence Diagram -- 2.2 Problem Definition -- 3 3-Bottleneck Matching Is NP-Complete -- 4 A Tight Approximation -- 4.1 Approximation for m-Bottleneck Matching -- 4.2 Generalization to the Center Persistence Diagram Problem Under the Bottleneck Distance -- 5 Concluding Remarks -- References -- Robust Identification in the Limit from Incomplete Positive Data -- 1 Introduction -- 2 Background -- 2.1 Identification in the Limit -- 2.2 String Extension Learning -- 2.3 Model-Theoretic Factors and Related Formal Language Classes -- 3 Robustness -- 3.1 Unaffectedness -- 3.2 Strong Robustness -- 3.3 Weak Robustness -- 4 Conclusions -- References -- Cordial Forests -- 1 Introduction -- 1.1 Parity Conditions for the Graceful Tree Conjecture -- 1.2 Outline -- 2 Parity Conditions -- 3 Twin-Constructions -- 4 Characterization of Cordial Forests -- 4.1 Labeling Trees -- 4.2 -Neutral Forests -- 4.3 Labeling Forests -- 5 Final Remarks -- References -- Vertex Ordering with Precedence Constraints -- 1 Introduction and Problem Definition -- 1.1 Problem Definition -- 1.2 Warm-Up (Simple Cases) -- 2 Definitions and Concepts -- 3 Polynomial Time Cases -- 3.1 Polynomial Time Algorithm for Trivially Perfect Bipartite Graph, Bipartite Cographs, and Bipartite Permutation Graphs -- 4 Linear Program Formulation of the Problem -- References -- Forwards- and Backwards-Reachability for Cooperating Multi-pushdown Systems -- 1 Introduction -- 2 Preliminaries -- 3 Introducing Cooperating Multi-pushdown Systems -- 4 Computing the Backwards Reachable Configurations -- 5 Computing the Forwards Reachable Configurations -- 5.1 Forwards Reachability in Homogeneous Systems -- 5.2 Forwards Reachability in Saturated Systems -- 5.3 Saturating a System -- 6 Summary, Consequences, and Open Questions. ; References -- Shortest Dominating Set Reconfiguration Under Token Sliding -- 1 Introduction -- 2 Preliminaries -- 3 Lower Bounds on Lengths of Reconfiguration Sequences -- 4 Algorithms for Finding a Shortest Reconfiguration Sequence -- 4.1 Trees -- 4.2 Interval Graphs -- 5 Conclusion -- References -- Computing Optimal Leaf Roots of Chordal Cographs in Linear Time -- 1 Introduction -- 2 Preliminaries -- 2.1 Chordal Cographs and Cotrees -- 2.2 Diameter, Radius and Center in Trees -- 2.3 Leaf Powers, Leaf Roots and Their Basic Properties -- 3 Optimal Leaf Root Construction for CCGs -- 4 Linear Time Leaf Root Construction for CCGs -- 5 Conclusion -- References -- Verified Exact Real Computation with Nondeterministic Functions and Limits -- 1 Introduction -- 2 Preliminaries -- 2.1 Nondeterministic Functions -- 2.2 Nondeterministic Limits -- 2.3 While Loops -- 3 The Programming Language -- 3.1 Syntax and Typing Rules -- 3.2 Denotational Semantics -- 4 Specifications -- 4.1 Assertion Language for Nondeterministic Functions -- 4.2 Total Correctness Specifications -- 5 Proof Rules -- 6 Examples -- 6.1 Two Dimensional Searching -- 6.2 Intermediate Value Theorem -- 7 Conclusion and Future Work -- References -- Exact and Parameterized Algorithms for the Independent Cutset Problem -- 1 Introduction -- 2 An Exact Exponential Algorithm -- 3 Parameterized Algorithms -- 3.1 Dual Parameterizations -- 3.2 Dominating Set -- 3.3 Distance to Bipartite Graphs -- 3.4 Distance to Chordal Graphs -- 3.5 Distance to P5-Free Graphs -- 3.6 Generalizing Distance to P5-Free Graphs -- References -- Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves -- 1 Introduction -- 1.1 Our Results -- 1.2 Related Results -- 1.3 Organization of the Paper -- 2 Preliminaries -- 3 Kernelization -- 4 FPT Algorithms -- 5 Conclusion -- References. ; Two UNO Decks Efficiently Perform Zero-Knowledge Proof for Sudoku.
• Titolo autorizzato: Fundamentals of Computation Theory
• ISBN: 3-031-43587-7
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 996550553503316
• Lo trovi qui: Univ. di Salerno
• Serie: Lecture notes in computer science ; ; Volume 14292.