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

• Record Nr.: UNISA996550553503316
• Pubbl/distr/stampa: Cham, Switzerland : , : Springer, , [2023]; ©2023
• ISBN: 3-031-43587-7
• Edizione: [First edition.]
• Descrizione fisica: 1 online resource (450 pages)
• Collana: Lecture Notes in Computer Science Series ; ; Volume 14292
• Disciplina: 004
• Soggetti: Computer science; Computer science - Mathematics
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• 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.

Developments in Language Theory : 18th International Conference, DLT 2014, Ekaterinburg, Russia, August 26-29, 2014. Proceedings / / edited by Arseny M. Shur, Mikhail V. Volkov

• Record Nr.: UNINA9910483956103321
• Pubbl/distr/stampa: Cham : , : Springer International Publishing : , : Imprint : Springer, , 2014
• ISBN: 3-319-09698-2
• Edizione: [1st ed. 2014.]
• Descrizione fisica: 1 online resource (XVIII, 349 p. 51 illus.)
• Collana: Theoretical Computer Science and General Issues, , 2512-2029 ; ; 8633
• Disciplina: 511.3
• Soggetti: Computer science; Machine theory; Algorithms; Computer science—Mathematics; Discrete mathematics; Theory of Computation; Formal Languages and Automata Theory; Discrete Mathematics in Computer Science
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di contenuto: Finite Automata and Regular Languages On Automatic Transitive Graphs.- Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals -- On the Average Complexity of Brzozowski's Algorithm for Deterministic Automata with a Small Number of Final States -- State Complexity of Deletion -- Semisimple Synchronizing Automata and the Wedderburn-Artin Theory -- On two Algorithmic Problems about ; Synchronizing Automata (short paper) -- Synchronizing Automata with Random Inputs (short paper) -- Graph Spectral Properties of Deterministic Finite Automata (short paper) -- Pushdown Automata and Related Models -- Input-Driven Pushdown Automata with Limited Nondeterminism (invited paper) -- How to Remove the Look-Ahead of Top-Down Tree Transducers -- Scope-Bounded Pushdown Languages -- Visibly Pushdown Transducers with Well-nested Outputs -- Characterising REGEX Languages by Regular Languages Equipped with Factor-Referencing -- Pumping Lemma and Ogden Lemma for Displacement Context-free Grammars -- Combinatorics and Algorithmics on Words Aperiodic Tilings and Entropy -- On k-Abelian Pattern Matching -- On k-Abelian Palindromic Rich and Poor Words -- Variations of The Morse{Hedlund Theorem for k-Abelian Equivalence -- Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word -- Knight Tiles: Particles and Collisions in The Realm of 4-Way Deterministic Tilings -- Eigenvalues and Transduction of Morphic Sequences -- Breadth-First Serialisation of Trees and Rational Languages (short paper) -- Algebraic, Decidability and Complexity Problems for Languages Measuring Communication in Automata Systems (invited paper) -- From Algebra to Logic: There and Back Again { The Story of A Hierarchy (invited paper) -- Closure Properties of Pattern Languages -- Minimal and Hyper-Minimal Biautomata -- Deterministic Set Automata -- The Minimum Amount of Useful Space: New Results and New Directions -- Debates with Small Transparent Quantum Verifiers -- Embedding Finite and Infinite Words into Overlapping Tiles.
• Sommario/riassunto: This book constitutes the proceedings of the 18th International Conference on Developments in Language Theory, DLT 2014, held in Ekaterinburg, Russia, in August 2014. The 22 full papers and 5 short papers presented together with 3 invited talks were carefully reviewed and selected from 38 submissions. The papers are organized in topical subjects on Grammars, Acceptors and Transducers for Words, Trees and Graphs, Algebraic Theories of Automata, Algorithmic, Combinatorial and Algebraic Properties of Words and Languages, Variable Length Codes, Symbolic Dynamics, Cellular Automata, Polyominoes and Multidimensional Patterns, Decidability Questions, Image Manipulation and Compression, Efficient Text Algorithms, Relationships to Cryptography, Concurrency, Complexity Theory and Logic, Bio-Inspired Computing, and Quantum Computing.