Computer Science -- Theory and Applications

Name: Computer Science -- Theory and Applications | 7th International Computer Science Symposium in Russia, CSR 2012, Niszhny Novgorod, Russia, July 3-7, 2012, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

7th International Computer Science Symposium in Russia, CSR 2012, Niszhny Novgorod, Russia, July 3-7, 2012, Proceedings

Edward Hirsch Juhani Karhumäki Arto Lepistö Michail Prilutskii(Herausgeber*in)

Springer (Verlag)

Erschienen am 11. August 2012

XXIII, 327 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-30642-6 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title Page
Preface
Organization
Table of Contents
Opening Talk
Can the Theory of Algorithms Ratify the ``Invisible Hand of the Market''?
Introduction
References
Full Papers
Resilient Quicksort and Selection
Introduction
Preliminaries
Previous Work
Our Contribution
Randomized Sorting
Resilient Selection
Deterministic Sorting
References
General Quantitative Specification Theories with Modalities
Introduction
Structured Modal Transition Systems
Refinement Distances
Structural Composition and Quotient
Conjunction
Conclusion
References
The Complexity of Intersecting Finite Automata Having Few Final States
Introduction
Our Contribution
Preliminaries
Basic Definitions and Notation
Problems
Groups and Abelian Groups
Some Observations on Commutative Monoids
Conclusion and Further Work
News about Semiantichains and Unichain Coverings
Introduction
Constructions
A Bad Example
Checking Tests for Read-Once Functions over Arbitrary Bases
Introduction
Background and Related Work
Basic Definitions
The Relevance Hypercube Method
Assumptions and Notation
Some Observations
Auxiliary Lemmas
Main Theorem
Discussion
Approximating Minimum Power Edge-Multi-Covers
Introduction
Motivation and Problems Considered
Our Results
Overview of the Techniques
Proof of Theorem 1
Reduction to Bipartite Graphs
An O(logk)-Approximation Algorithm for General Costs
A Constant Ratio Approximation Algorithm for Unit Costs
Proof of Theorem 2
Conclusions and Open Problems
A Lower Bound on Circuit Complexity of Vector Function in U2
Introduction
New Lower Bound
Computing All MOD-Functions Simultaneously
Introduction
Preparations
Basic Facts from Number Theory
Encodings
Building Blocks
Upper Bounds
C(ALLMODrn) = O(n)
C(ALLMODr1, ., rnn) = O(n loglogn)
Further Directions
Bounded Synchronization Delay in Omega-Rational Expressions
Introduction
Preliminaries
Local Divisors
Schützenberger's Class SD
SD Equals AP
Finitely Many c
Infinitely Many c
SD= AP Implies SF= AP
Towards Optimal Degree-Distributions for Left-Perfect Matchings in Random Bipartite Graphs
Introduction
Motivation and Related Work
Results
Optimality of Concentration in a Unit Length Interval
Average Degrees of Different Nodes are Close
Optimal Distributions Use Only Two Neighboring Degrees
A Conjecture: Essentially Two Different Strategies
Conclusion
Robust Sensor Range for Constructing Strongly Connected Spanning Digraphs in UDGs
Introduction
Related Work
Results and Outline of the Paper
Robustness of Unit Disk Graphs
Efficiently Computing Weak t-Robustness
Digraph with Max Out-Degree Four
Digraph with Max Out-Degree Three
Conclusion
Worst-Case Optimal Priority Queues via Extended Regular Counters
Introduction
Description of the Data Structure
Priority-Queue Operations
Violation Reductions
Extended Regular Binary Counters
Conclusions
The Complexity of Minor-Ancestral Graph Properties with Forbidden Pairs
Introduction
Main Result
Discussion
Deciding Membership in co-FSP
Forbidden Edge Pairs
Fixed Parameter Tractability
Conclusions
Satisfiability Thresholds beyond k-XORSAT
Introduction
Contribution
Motivation
Notation and Basics for the12mumod3-Case
Structure of the Proof of Theorem 5
Structure of the Proof of Theorem 9
Uniquely Extendible Constraints
Finding Vertex-Surjective Graph Homomorphisms
Introduction
Definitions and Preliminaries
Hard Cases
Tractable Cases
Conclusions
Broadcast Domination on Block Graphs in Linear Time
Introduction
Definitions and Notation
General Properties of Dominating Broadcasts
Structural Properties of Dominating Broadcasts on Block Graphs
Algorithmic Properties of Dominating Broadcasts on Block Graphs
A Linear-time Algorithm for Optimal Broadcasts on Block Graphs
Concluding Remarks
Characterizing Certain Topological Specifications
Introduction
The Languages We Consider
Saturation
Bisimulations
The Characterization Theorem
Concluding Remarks
Descriptional Complexity of Operations on Alternating and Boolean Automata
Introduction
Preliminaries
Optimal Simulation of AFAs by NFAs
Boolean and Alternating State Complexity of Basic Regular Operations
Conclusions
Consistency of Multidimensional Combinatorial Substitutions
Introduction
Definitions
Undecidability Results
Undecidability of Consistency
Undecidability of Overlapping
Decidability Results
Decidability of Consistency for Domino-Complete Substitutions
Decidability of Overlapping for Consistent Domino-Complete Substitutions
Conclusion and Open Problems
Two-Way Automata Characterizations of L/poly versus NL
Introduction
Preparation
Automata
Problems
Transducers, Reductions, and Completeness
Closures
Characterizations and Conjectures
Conclusion
Cutting through Regular Post Embedding Problems
Introduction
Basic Notation and Definitions
Deciding PEP partialdir, or PEP with Partial Directness
Counting the Number of Solutions
Universal Variants of PEP partialdir
Undecidability for PEP co&dir and Other Extensions
Concluding Remarks
On the Advice Complexity of the Set Cover Problem
Introduction and Preliminaries
Bounds Measured in the Size of X
Bounds Measured in the Size of S
Conclusion
Constraint Satisfaction with Counting Quantifiers
Introduction
Preliminaries
Game Characterisation
Complexity of a Single Quantifier
Counting Quantifiers on Cliques and Cycles
Cliques: Proof of Theorem 1
Cycles: Proof of Theorem 2
Extensions of the CSP
Bipartite Graphs
The Complexity of QCSP(C*4)
Conclusion
Space-Bounded Kolmogorov Extractors
Introduction
Preliminaries
Kolmogorov Complexity
Extractors
Balanced Tables
Nisan-Wigderson Generators
Constant-depth Circuits for Approximate Counting
Main Result
Overview
Proof Idea
Derandomization Plan
The Weakening of Balancing Conditions
Existence of Balanced Tables in the Output of the NW-generator
Searching for a Good Seed
Completion of the Proof
Some Results on more Flexible Versions of Graph Motif
Introduction
Maximizing the Solution Size
Minimizing the Number of Substitutions
Using Modularity
Definitions and Properties
When Modules Join Graph Motif
Difficulty of the Problem
Algorithms for the Decision Problem
Open Problems
A Characterization of Cellular Automata Generated by Idempotents on the Full Shift
Introduction
Definitions and Useful Lemmas
Cellular Automata Generated by Idempotents on the Full Shift
Forbidding a Word from the Input: E
Encoding Aperiodic Parts and Memorizing Periodic Parts: A
Periodic Subwords of Small Enough Period: P
The Final Touch: F
Examples and Decidability Questions
Examples
Decidability Questions
Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
Introduction
Concepts
On Some Characteristics of Monomials
Canonical form of Polynomials
Checking Algorithm of Polynomiality for Functions
Boolean Composition of Visual Secret Sharing Schemes
Introduction
Definitions, Notations and Facts
Visual Secret Sharing Schemes
Contrast as Objective Function in a Linear Program
The Composition of Two Access Structures
Conjunction of Two Threshold-Schemes
Proof of Claim 1
Proof of Claim 2
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken