Computer Science - Theory and Applications [[electronic resource] ] : 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013, Proceedings / / edited by Andrei A. Bulatov, Arseny M. Shur |
Edizione | [1st ed. 2013.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 |
Descrizione fisica | 1 online resource (XII, 445 p. 55 illus.) : digital |
Disciplina | 004.0151 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Algorithms
Computer science Computer science—Mathematics Discrete mathematics Machine theory Computer Science Logic and Foundations of Programming Theory of Computation Discrete Mathematics in Computer Science Formal Languages and Automata Theory |
ISBN | 3-642-38536-2 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | 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 Density of 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-Checking Bounded Multi-Pushdown Systems -- Multi-weighted Automata and MSO Logic -- Overlapping Tile Automata. |
Record Nr. | UNISA-996465582603316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Computer Science - Theory and Applications : 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013, Proceedings / / edited by Andrei A. Bulatov, Arseny M. Shur |
Edizione | [1st ed. 2013.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 |
Descrizione fisica | 1 online resource (XII, 445 p. 55 illus.) : digital |
Disciplina | 004.0151 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Algorithms
Computer science Computer science—Mathematics Discrete mathematics Machine theory Computer Science Logic and Foundations of Programming Theory of Computation Discrete Mathematics in Computer Science Formal Languages and Automata Theory |
ISBN | 3-642-38536-2 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | 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 Density of 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-Checking Bounded Multi-Pushdown Systems -- Multi-weighted Automata and MSO Logic -- Overlapping Tile Automata. |
Record Nr. | UNINA-9910483557703321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|