LEADER 11076nam 2200529 450 001 9910746297303321 005 20231121003716.0 010 $a3-031-43587-7 035 $a(MiAaPQ)EBC30750415 035 $a(Au-PeEL)EBL30750415 035 $a(OCoLC)1399170379 035 $a(EXLCZ)9928275621900041 100 $a20231121d2023 uy 0 101 0 $aeng 135 $aurcnu|||||||| 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 00$aFundamentals of Computation Theory $e24th International Symposium, FCT 2023, Trier, Germany, September 18-21, 2023, Proceedings /$fHenning Fernau and Klaus Jansen, editors 205 $aFirst edition. 210 1$aCham, Switzerland :$cSpringer,$d[2023] 210 4$dİ2023 215 $a1 online resource (450 pages) 225 1 $aLecture Notes in Computer Science Series ;$vVolume 14292 311 08$aPrint version: Fernau, Henning Fundamentals of Computation Theory Cham : Springer,c2023 9783031435867 320 $aIncludes bibliographical references and index. 327 $aIntro -- 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. 327 $aComputing 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. 327 $a3 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. 327 $aOn 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. 327 $aReferences -- 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. 327 $aTwo UNO Decks Efficiently Perform Zero-Knowledge Proof for Sudoku. 410 0$aLecture notes in computer science ;$vVolume 14292. 606 $aComputer science$vCongresses 606 $aComputer science$xMathematics$vCongresses 615 0$aComputer science 615 0$aComputer science$xMathematics 676 $a004 702 $aFernau$b Henning 702 $aJansen$b Klaus 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910746297303321 996 $aFundamentals of Computation Theory$92557870 997 $aUNINA