Computer Science - Theory and Applications
Springer Berlin (Verlag)
978-3-642-38535-3 (ISBN)
The Lovasz Local Lemma - A Survey.- An Improved Knapsack Solver for Column Generation.- QuickHeapsort: Modifications and Improved Analysis.- Alphabetic Minimax Trees in Linear Time.- Decidability and Enumeration for Automatic Sequences: A Survey.- Walking on Data Words.- Careful Synchronization of Partial Automata with Restricted Alphabets.- Random Generation of Deterministic Acyclic Automata Using the Recursive Method.- Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height.- A Short Tutorial on Order-Invariant First-Order Logic.- Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams.- Parameterized Resolution with Bounded Conjunction.- Lower and Upper Bounds for the Length of Joins in the Lambek Calculus.- Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP.- Towards NEXP versus BPP?.- Information Lower Bounds via Self-reducibility.- On the Encoding Invariance of Polynomial Time Computable Distribution Ensembles.- Improving on Gutfreund, Shaltiel, and Ta-Shma's Paper "If NP Languages Are Hard on the Worst-Case, Then It Is Easy to Find Their Hard Instances".- Amortized Communication Complexity of an Equality Predicate.- On Coloring of Sparse Graphs.- On Recognizing Words That Are Squares for the Shuffle Product.- Cyclic Shift on Prefix-Free Languages.- Weak Abelian Periodicity of Infinite Words.- Universality of Regular Realizability Problems.- Potential Functions in Strategic Games.- The Probabilistic Min Dominating Set Problem.- Dichotomy of the H-Quasi-Cover Problem.- QCSP on Partially Reflexive Cycles - The Wavy Line of Tractability.- Quantum Alternation.- Real Numbers, Chaos, and the Principle of a Bounded Densityof Information.- Random Selection in Few Rounds.- One-Counter Verifiers for Decidable Languages.- More on the Complexity of Quantifier-Free Fixed-Size Bit-Vector Logics with Binary Encoding.- Composition with Algebra at the Background.- Model-CheckingBounded Multi-Pushdown Systems.- Multi-weighted Automata and MSO Logic.- Overlapping Tile Automata.
| Erscheint lt. Verlag | 16.5.2013 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science | Theoretical Computer Science and General Issues |
| Zusatzinfo | XII, 445 p. 55 illus. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 691 g |
| Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
| Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik | |
| Schlagworte | Algorithm analysis and problem complexity • Computational Complexity • Decidability • formal methods • multi-weighted automata • prefix-free languages |
| ISBN-10 | 3-642-38535-4 / 3642385354 |
| ISBN-13 | 978-3-642-38535-3 / 9783642385353 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
