Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Combinatorial algorithms : 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings / / edited by Cristina Bazgan and Henning Fernau
| Combinatorial algorithms : 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings / / edited by Cristina Bazgan and Henning Fernau |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2022] |
| Descrizione fisica | 1 online resource (538 pages) |
| Disciplina | 004.0151 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico |
Combinatorial analysis
Algorithms |
| ISBN | 3-031-06678-2 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Record Nr. | UNISA-996476363703316 |
| Cham, Switzerland : , : Springer, , [2022] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Combinatorial algorithms : 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings / / edited by Cristina Bazgan and Henning Fernau
| Combinatorial algorithms : 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings / / edited by Cristina Bazgan and Henning Fernau |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2022] |
| Descrizione fisica | 1 online resource (538 pages) |
| Disciplina | 004.0151 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico |
Combinatorial analysis
Algorithms |
| ISBN | 3-031-06678-2 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Record Nr. | UNINA-9910574061003321 |
| Cham, Switzerland : , : Springer, , [2022] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Computer Science – Theory and Applications [[electronic resource] ] : 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings / / edited by Henning Fernau
| Computer Science – Theory and Applications [[electronic resource] ] : 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings / / edited by Henning Fernau |
| Edizione | [1st ed. 2020.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2020 |
| Descrizione fisica | 1 online resource (xi, 433 pages) |
| Disciplina | 004 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer science
Computer science—Mathematics Discrete mathematics Data structures (Computer science) Information theory Theory of Computation Discrete Mathematics in Computer Science Data Structures and Information Theory Mathematics of Computing |
| ISBN | 3-030-50026-8 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations -- Parameterized Analysis of Art Gallery and Terrain Guarding -- Central Positions in Social Networks -- Second-Order Finite Automata -- Isomorphic Distances Among Elections -- Tandem Duplications, Segmental Duplications and Deletions, and their Applications -- Faster 2-Disjoint-Shortest-Path Algorithm -- An Improvement to Chvátal and Thomassen's Upper Bound for Oriented Diameter -- The Normalized Algorithmic Information Distance Cannot be Approximated -- Definable Subsets of Polynomial-Time Algebraic Structures -- Families of Monotonic Trees: Combinatorial Enumeration and Asymptotics -- Nested Regular Expressions can be Compiled to Small Deterministic Nested Word Automata -- On Embeddability of Unit Disk Graphs onto Straight Lines.-On the Decision Tree Complexity of Threshold Functions -- Randomized and Symmetric Catalytic Computation -- On the Parameterized Complexity of the Expected Coverage Problem -- Computational Hardness of Multidimensional Subtraction Games -- Parameterized Complexity of Fair Feedback Vertex Set Problem -- The Power of Leibniz-like Functions as Oracles -- Optimal Skeleton Huffman Trees Revisited -- The Subtrace Order and Counting First-Order Logic -- Speedable left-c.e. Numbers -- The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters -- On the Transformation of LL(k)-linear Grammars to LL(1)-linear -- On Computing the Hamiltonian Index of Graphs -- A Lower Bound for the Query Phase of Contraction Hierarchies and Hub Labels -- Kernelization of Arc Disjoint Cycle Packing in $\alpha$-bounded Digraphs -- On Subquadratic Derivational Complexity of Semi-Thue Systems -- The Untold Story of SBP -- Weighted Rooted Trees: Fat or Tall -- Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversals. |
| Record Nr. | UNISA-996418309003316 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2020 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Computer Science – Theory and Applications : 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings / / edited by Henning Fernau
| Computer Science – Theory and Applications : 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings / / edited by Henning Fernau |
| Edizione | [1st ed. 2020.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2020 |
| Descrizione fisica | 1 online resource (xi, 433 pages) |
| Disciplina | 004 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer science
Computer science—Mathematics Discrete mathematics Data structures (Computer science) Information theory Theory of Computation Discrete Mathematics in Computer Science Data Structures and Information Theory Mathematics of Computing |
| ISBN | 3-030-50026-8 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations -- Parameterized Analysis of Art Gallery and Terrain Guarding -- Central Positions in Social Networks -- Second-Order Finite Automata -- Isomorphic Distances Among Elections -- Tandem Duplications, Segmental Duplications and Deletions, and their Applications -- Faster 2-Disjoint-Shortest-Path Algorithm -- An Improvement to Chvátal and Thomassen's Upper Bound for Oriented Diameter -- The Normalized Algorithmic Information Distance Cannot be Approximated -- Definable Subsets of Polynomial-Time Algebraic Structures -- Families of Monotonic Trees: Combinatorial Enumeration and Asymptotics -- Nested Regular Expressions can be Compiled to Small Deterministic Nested Word Automata -- On Embeddability of Unit Disk Graphs onto Straight Lines.-On the Decision Tree Complexity of Threshold Functions -- Randomized and Symmetric Catalytic Computation -- On the Parameterized Complexity of the Expected Coverage Problem -- Computational Hardness of Multidimensional Subtraction Games -- Parameterized Complexity of Fair Feedback Vertex Set Problem -- The Power of Leibniz-like Functions as Oracles -- Optimal Skeleton Huffman Trees Revisited -- The Subtrace Order and Counting First-Order Logic -- Speedable left-c.e. Numbers -- The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters -- On the Transformation of LL(k)-linear Grammars to LL(1)-linear -- On Computing the Hamiltonian Index of Graphs -- A Lower Bound for the Query Phase of Contraction Hierarchies and Hub Labels -- Kernelization of Arc Disjoint Cycle Packing in $\alpha$-bounded Digraphs -- On Subquadratic Derivational Complexity of Semi-Thue Systems -- The Untold Story of SBP -- Weighted Rooted Trees: Fat or Tall -- Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversals. |
| Record Nr. | UNINA-9910410054503321 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2020 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Fundamentals of Computation Theory : 24th International Symposium, FCT 2023, Trier, Germany, September 18-21, 2023, Proceedings / / Henning Fernau and Klaus Jansen, editors
| Fundamentals of Computation Theory : 24th International Symposium, FCT 2023, Trier, Germany, September 18-21, 2023, Proceedings / / Henning Fernau and Klaus Jansen, editors |
| Edizione | [First edition.] |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2023] |
| Descrizione fisica | 1 online resource (450 pages) |
| Disciplina | 004 |
| Collana | Lecture Notes in Computer Science Series |
| Soggetto topico |
Computer science
Computer science - Mathematics |
| ISBN | 3-031-43587-7 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| 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. |
| Record Nr. | UNISA-996550553503316 |
| Cham, Switzerland : , : Springer, , [2023] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Fundamentals of Computation Theory : 24th International Symposium, FCT 2023, Trier, Germany, September 18-21, 2023, Proceedings / / Henning Fernau and Klaus Jansen, editors
| Fundamentals of Computation Theory : 24th International Symposium, FCT 2023, Trier, Germany, September 18-21, 2023, Proceedings / / Henning Fernau and Klaus Jansen, editors |
| Edizione | [First edition.] |
| Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2023] |
| Descrizione fisica | 1 online resource (450 pages) |
| Disciplina | 004 |
| Collana | Lecture Notes in Computer Science Series |
| Soggetto topico |
Computer science
Computer science - Mathematics |
| ISBN | 3-031-43587-7 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| 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. |
| Record Nr. | UNINA-9910746297303321 |
| Cham, Switzerland : , : Springer, , [2023] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Grammatical Inference: Algorithms and Applications [[electronic resource] ] : 6th International Colloquium: ICGI 2002, Amsterdam, The Netherlands, September 23-25, 2002. Proceedings / / edited by Pieter Adriaans, Henning Fernau, Menno van Zaanen
| Grammatical Inference: Algorithms and Applications [[electronic resource] ] : 6th International Colloquium: ICGI 2002, Amsterdam, The Netherlands, September 23-25, 2002. Proceedings / / edited by Pieter Adriaans, Henning Fernau, Menno van Zaanen |
| Edizione | [1st ed. 2002.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2002 |
| Descrizione fisica | 1 online resource (X, 318 p.) |
| Disciplina | 005.13/1 |
| Collana | Lecture Notes in Artificial Intelligence |
| Soggetto topico |
Natural language processing (Computer science)
Programming languages (Electronic computers) Artificial intelligence Mathematical logic Computer logic Natural Language Processing (NLP) Programming Languages, Compilers, Interpreters Artificial Intelligence Mathematical Logic and Formal Languages Logics and Meanings of Programs |
| ISBN | 3-540-45790-9 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Contributions -- Inference of Sequential Association Rules Guided by Context-Free Grammars -- PCFG Learning by Nonterminal Partition Search -- Inferring Subclasses of Regular Languages Faster Using RPNI and Forbidden Configurations -- Beyond EDSM -- Consistent Identification in the Limit of Rigid Grammars from Strings Is NP-hard -- Some Classes of Regular Languages Identifiable in the Limit from Positive Data -- Learning Probabilistic Residual Finite State Automata -- Fragmentation: Enhancing Identifiability -- On Limit Points for Some Variants of Rigid Lambek Grammars -- Generalized Stochastic Tree Automata for Multi-relational Data Mining -- On Sufficient Conditions to Identify in the Limit Classes of Grammars from Polynomial Time and Data -- Stochastic Grammatical Inference with Multinomial Tests -- Learning Languages with Help -- Incremental Learning of Context Free Grammars -- Estimating Grammar Parameters Using Bounded Memory -- Stochastic k-testable Tree Languages and Applications -- Fast Learning from Strings of 2-Letter Rigid Grammars -- Learning Locally Testable Even Linear Languages from Positive Data -- Inferring Attribute Grammars with Structured Data for Natural Language Processing -- A PAC Learnability of Simple Deterministic Languages -- On the Learnability of Hidden Markov Models -- Shallow Parsing Using Probabilistic Grammatical Inference -- Learning of Regular Bi-? Languages -- Software Descriptions -- The EMILE 4.1 Grammar Induction Toolbox -- Software for Analysing Recurrent Neural Nets That Learn to Predict Non-regular Languages -- A Framework for Inductive Learning of Typed-Unification Grammars -- A Tool for Language Learning Based on Categorial Grammars and Semantic Information -- ‘NAIL’: Artificial Intelligence Software for Learning Natural Language -- Lyrebird™: Developing Spoken Dialog Systems Using Examples -- Implementing Alignment-Based Learning. |
| Record Nr. | UNISA-996465421403316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2002 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Grammatical Inference: Algorithms and Applications : 6th International Colloquium: ICGI 2002, Amsterdam, The Netherlands, September 23-25, 2002. Proceedings / / edited by Pieter Adriaans, Henning Fernau, Menno van Zaanen
| Grammatical Inference: Algorithms and Applications : 6th International Colloquium: ICGI 2002, Amsterdam, The Netherlands, September 23-25, 2002. Proceedings / / edited by Pieter Adriaans, Henning Fernau, Menno van Zaanen |
| Edizione | [1st ed. 2002.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2002 |
| Descrizione fisica | 1 online resource (X, 318 p.) |
| Disciplina | 005.13/1 |
| Collana | Lecture Notes in Artificial Intelligence |
| Soggetto topico |
Natural language processing (Computer science)
Programming languages (Electronic computers) Artificial intelligence Mathematical logic Computer logic Natural Language Processing (NLP) Programming Languages, Compilers, Interpreters Artificial Intelligence Mathematical Logic and Formal Languages Logics and Meanings of Programs |
| ISBN | 3-540-45790-9 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Contributions -- Inference of Sequential Association Rules Guided by Context-Free Grammars -- PCFG Learning by Nonterminal Partition Search -- Inferring Subclasses of Regular Languages Faster Using RPNI and Forbidden Configurations -- Beyond EDSM -- Consistent Identification in the Limit of Rigid Grammars from Strings Is NP-hard -- Some Classes of Regular Languages Identifiable in the Limit from Positive Data -- Learning Probabilistic Residual Finite State Automata -- Fragmentation: Enhancing Identifiability -- On Limit Points for Some Variants of Rigid Lambek Grammars -- Generalized Stochastic Tree Automata for Multi-relational Data Mining -- On Sufficient Conditions to Identify in the Limit Classes of Grammars from Polynomial Time and Data -- Stochastic Grammatical Inference with Multinomial Tests -- Learning Languages with Help -- Incremental Learning of Context Free Grammars -- Estimating Grammar Parameters Using Bounded Memory -- Stochastic k-testable Tree Languages and Applications -- Fast Learning from Strings of 2-Letter Rigid Grammars -- Learning Locally Testable Even Linear Languages from Positive Data -- Inferring Attribute Grammars with Structured Data for Natural Language Processing -- A PAC Learnability of Simple Deterministic Languages -- On the Learnability of Hidden Markov Models -- Shallow Parsing Using Probabilistic Grammatical Inference -- Learning of Regular Bi-? Languages -- Software Descriptions -- The EMILE 4.1 Grammar Induction Toolbox -- Software for Analysing Recurrent Neural Nets That Learn to Predict Non-regular Languages -- A Framework for Inductive Learning of Typed-Unification Grammars -- A Tool for Language Learning Based on Categorial Grammars and Semantic Information -- ‘NAIL’: Artificial Intelligence Software for Learning Natural Language -- Lyrebird™: Developing Spoken Dialog Systems Using Examples -- Implementing Alignment-Based Learning. |
| Record Nr. | UNINA-9910143898703321 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2002 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Language and Automata Theory and Applications [[electronic resource] ] : 4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010, Proceedings / / edited by Carlos Martin-Vide, Henning Fernau, Adrian Horia Dediu
| Language and Automata Theory and Applications [[electronic resource] ] : 4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010, Proceedings / / edited by Carlos Martin-Vide, Henning Fernau, Adrian Horia Dediu |
| Edizione | [1st ed. 2010.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 |
| Descrizione fisica | 1 online resource (XIV, 622 p. 92 illus.) |
| Disciplina | 410.1/15 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer programming
Compilers (Computer programs) Pattern recognition systems Computer science Algorithms Artificial intelligence Programming Techniques Compilers and Interpreters Automated Pattern Recognition Theory of Computation Artificial Intelligence |
| ISBN |
1-280-38660-6
9786613564528 3-642-13089-5 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Talks -- Complexity in Convex Languages -- Three Learnable Models for the Description of Language -- Arbology: Trees and Pushdown Automata -- Analysis of Communicating Automata -- Regular Papers -- Complexity of the Satisfiability Problem for a Class of Propositional Schemata -- A Simple n-Dimensional Intrinsically Universal Quantum Cellular Automaton -- A Fast Longest Common Subsequence Algorithm for Similar Strings -- Abelian Square-Free Partial Words -- Avoidable Binary Patterns in Partial Words -- Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata -- Pregroup Grammars with Letter Promotions -- A Hierarchical Classification of First-Order Recurrent Neural Networks -- Choosing Word Occurrences for the Smallest Grammar Problem -- Agreement and Cliticization in Italian: A Pregroup Analysis -- Geometricity of Binary Regular Languages -- On the Expressive Power of FO[?+?] -- Finding Consistent Categorial Grammars of Bounded Value: A Parameterized Approach -- Operator Precedence and the Visibly Pushdown Property -- On the Maximal Number of Cubic Runs in a String -- On the Hamiltonian Operators for Adiabatic Quantum Reduction of SAT -- Parametric Metric Interval Temporal Logic -- Short Witnesses and Accepting Lassos in ?-Automata -- Grammar-Based Compression in a Streaming Model -- Simplifying Regular Expressions -- A Programming Language Tailored to the Specification and Solution of Differential Equations Describing Processes on Networks -- The Inclusion Problem for Regular Expressions -- Learnability of Automatic Classes -- Untestable Properties Expressible with Four First-Order Quantifiers -- The Copying Power of Well-Nested Multiple Context-Free Grammars -- Post Correspondence Problem with Partially Commutative Alphabets -- Reversible Pushdown Automata -- String Extension Learning Using Lattices -- The Equivalence Problem of Deterministic Multitape Finite Automata: A New Proof of Solvability Using a Multidimensional Tape -- Primitive Words Are Unavoidable for Context-Free Languages -- Modal Nonassociative Lambek Calculus with Assumptions: Complexity and Context-Freeness -- Hard Counting Problems for Partial Words -- Exact Analysis of Horspool’s and Sunday’s Pattern Matching Algorithms with Probabilistic Arithmetic Automata -- SA-REPC – Sequence Alignment with Regular Expression Path Constraint -- CD-Systems of Stateless Deterministic R(1)-Automata Accept All Rational Trace Languages -- A Boundary between Universality and Non-universality in Extended Spiking Neural P Systems -- Using Sums-of-Products for Non-standard Reasoning -- Restarting Automata with Structured Output and Functional Generative Description -- A Randomized Numerical Aligner (rNA) -- Language-Based Comparison of Petri Nets with Black Tokens, Pure Names and Ordered Data -- Verifying Complex Continuous Real-Time Systems with Coinductive CLP(R) -- Incremental Building in Peptide Computing to Solve Hamiltonian Path Problem -- Variable Automata over Infinite Alphabets -- Some Minimality Results on Biresidual and Biseparable Automata -- Extending Stochastic Context-Free Grammars for an Application in Bioinformatics -- Chomsky-Schützenberger-Type Characterization of Multiple Context-Free Languages -- Complexity of Guided Insertion-Deletion in RNA-Editing. |
| Record Nr. | UNISA-996465879103316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Language and automata theory and applications : 4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010 : proceedings / / Adrian Horia Dediu, Henning Fernau, Carlos Martin-Vide (eds.)
| Language and automata theory and applications : 4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010 : proceedings / / Adrian Horia Dediu, Henning Fernau, Carlos Martin-Vide (eds.) |
| Edizione | [1st ed.] |
| Pubbl/distr/stampa | Berlin, : Springer, 2010 |
| Descrizione fisica | 1 online resource (XIV, 622 p. 92 illus.) |
| Disciplina | 410.1/15 |
| Altri autori (Persone) |
Horia DediuAdrian
FernauHenning Martin VideCarlos |
| Collana |
Lecture notes in computer science
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
| Soggetto topico |
Machine theory
Formal languages Mathematical linguistics |
| ISBN |
1-280-38660-6
9786613564528 3-642-13089-5 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Talks -- Complexity in Convex Languages -- Three Learnable Models for the Description of Language -- Arbology: Trees and Pushdown Automata -- Analysis of Communicating Automata -- Regular Papers -- Complexity of the Satisfiability Problem for a Class of Propositional Schemata -- A Simple n-Dimensional Intrinsically Universal Quantum Cellular Automaton -- A Fast Longest Common Subsequence Algorithm for Similar Strings -- Abelian Square-Free Partial Words -- Avoidable Binary Patterns in Partial Words -- Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata -- Pregroup Grammars with Letter Promotions -- A Hierarchical Classification of First-Order Recurrent Neural Networks -- Choosing Word Occurrences for the Smallest Grammar Problem -- Agreement and Cliticization in Italian: A Pregroup Analysis -- Geometricity of Binary Regular Languages -- On the Expressive Power of FO[?+?] -- Finding Consistent Categorial Grammars of Bounded Value: A Parameterized Approach -- Operator Precedence and the Visibly Pushdown Property -- On the Maximal Number of Cubic Runs in a String -- On the Hamiltonian Operators for Adiabatic Quantum Reduction of SAT -- Parametric Metric Interval Temporal Logic -- Short Witnesses and Accepting Lassos in ?-Automata -- Grammar-Based Compression in a Streaming Model -- Simplifying Regular Expressions -- A Programming Language Tailored to the Specification and Solution of Differential Equations Describing Processes on Networks -- The Inclusion Problem for Regular Expressions -- Learnability of Automatic Classes -- Untestable Properties Expressible with Four First-Order Quantifiers -- The Copying Power of Well-Nested Multiple Context-Free Grammars -- Post Correspondence Problem with Partially Commutative Alphabets -- Reversible Pushdown Automata -- String Extension Learning Using Lattices -- The Equivalence Problem of Deterministic Multitape Finite Automata: A New Proof of Solvability Using a Multidimensional Tape -- Primitive Words Are Unavoidable for Context-Free Languages -- Modal Nonassociative Lambek Calculus with Assumptions: Complexity and Context-Freeness -- Hard Counting Problems for Partial Words -- Exact Analysis of Horspool’s and Sunday’s Pattern Matching Algorithms with Probabilistic Arithmetic Automata -- SA-REPC – Sequence Alignment with Regular Expression Path Constraint -- CD-Systems of Stateless Deterministic R(1)-Automata Accept All Rational Trace Languages -- A Boundary between Universality and Non-universality in Extended Spiking Neural P Systems -- Using Sums-of-Products for Non-standard Reasoning -- Restarting Automata with Structured Output and Functional Generative Description -- A Randomized Numerical Aligner (rNA) -- Language-Based Comparison of Petri Nets with Black Tokens, Pure Names and Ordered Data -- Verifying Complex Continuous Real-Time Systems with Coinductive CLP(R) -- Incremental Building in Peptide Computing to Solve Hamiltonian Path Problem -- Variable Automata over Infinite Alphabets -- Some Minimality Results on Biresidual and Biseparable Automata -- Extending Stochastic Context-Free Grammars for an Application in Bioinformatics -- Chomsky-Schützenberger-Type Characterization of Multiple Context-Free Languages -- Complexity of Guided Insertion-Deletion in RNA-Editing. |
| Record Nr. | UNINA-9910484987803321 |
| Berlin, : Springer, 2010 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||