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

Edizione	[1st ed. 2009.]
Pubbl/distr/stampa	Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2009
Descrizione fisica	1 online resource (XIII, 369 p.)
Disciplina	004.0151
Collana	Theoretical Computer Science and General Issues
Soggetto topico	Computer science Algorithms Machine theory Computer science—Mathematics Coding theory Information theory Theory of Computation Formal Languages and Automata Theory Mathematics of Computing Computer Science Logic and Foundations of Programming Coding and Information Theory
ISBN	1-280-38317-8 9786613561091 3-642-03351-2
Formato	Materiale a stampa
Livello bibliografico	Monografia
Lingua di pubblicazione	eng
Nota di contenuto	Invited Papers -- Well-Founded and Partial Stable Semantics Logical Aspects -- The Reachability Problem over Infinite Graphs -- Kolmogorov Complexity and Model Selection -- Automatic Verification of Heap-Manipulating Programs Using Separation Logic -- Accepted Papers -- Canonical Calculi: Invertibility, Axiom Expansion and (Non)-determinism -- Integrality Property in Preemptive Parallel Machine Scheduling -- Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes -- k-SAT Is No Harder Than Decision-Unique-k-SAT -- Unique Decipherability in the Monoid of Languages: An Application of Rational Relations -- Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model -- Approximability Distance in the Space of H-Colourability Problems -- On Random Ordering Constraints -- Depth Reduction for Circuits with a Single Layer of Modular Counting Gates -- A Feebly Secure Trapdoor Function -- Partitioning Graphs into Connected Parts -- Structural Complexity of AvgBPP -- Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials -- Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity -- One-Nonterminal Conjunctive Grammars over a Unary Alphabet -- Concatenation of Regular Languages and Descriptional Complexity -- Approximability of the Maximum Solution Problem for Certain Families of Algebras -- Complete Complexity Classification of Short Shop Scheduling -- Compressed Word Problems in HNN-Extensions and Amalgamated Products -- Variations on Muchnik’s Conditional Complexity Theorem -- An Optimal Bloom Filter Replacement Based on Matrix Solving -- Aperiodicity Measure for Infinite Sequences -- On the Complexity of Matroid Isomorphism Problems -- Breaking Anonymity by Learning a Unique Minimum Hitting Set -- The Budgeted Unique Coverage Problem and Color-Coding -- Formal Verification of Gate-Level Computer Systems -- On Models of a Nondeterministic Computation -- New Plain-Exponential Time Classes for Graph Homomorphism -- Languages Recognized with Unbounded Error by Quantum Finite Automata.
Record Nr.	UNISA-996465528903316

Edizione	[1st ed. 2015.]
Pubbl/distr/stampa	Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015
Descrizione fisica	1 online resource (XX, 443 p. 66 illus.)
Disciplina	004
Collana	Theoretical Computer Science and General Issues
Soggetto topico	Algorithms Computer science—Mathematics Discrete mathematics Computer science Numerical analysis Machine theory Discrete Mathematics in Computer Science Theory of Computation Numerical Analysis Computer Science Logic and Foundations of Programming Formal Languages and Automata Theory
ISBN	3-319-20297-9
Formato	Materiale a stampa
Livello bibliografico	Monografia
Lingua di pubblicazione	eng
Nota di contenuto	Propositional Proofs in Frege and Extended Frege Systems -- Circuit Complexity Meets Ontology-Based Data Access -- NEXP-Completeness and Universal Hardness Results for Justification Logic -- A Combinatorial Algorithm for the Planar Multi flow Problem with Demands Located on Three Holes -- Generalized LR Parsing for Grammars with Contexts -- On Compiling Structured CNFs to OBDDs -- Satisfiability of ECTL* with Tree Constraints -- On Growth and Fluctuation of k-Abelian Complexity -- A Polynomial-Time Algorithm for Outerplanar Diameter Improvement -- Editing to a Planar Graph of Given Degrees -- On the Satisfiability of Quantum Circuits of Small Treewidth -- Equations over Free Inverse Monoids with Idempotent Variables -- A Logical Characterization of Timed Pushdown Languages -- An In-place Priority Queue with O(1) Time for Push and lg n + O(1) Comparisons for Pop -- Resolution Complexity of Perfect Matching Principles for Sparse Graphs -- Operations on Self-verifying Finite Automata -- Automath Type Inclusion in Barendregt’s Cube -- Circuit Lower Bounds for Average-Case MA -- Making Randomness Public in Unbounded-Round Information Complexity -- First-Order Logic Definability of Free Languages -- Representation of (Left) Ideal Regular Languages by Synchronizing Automata -- Some Properties of Antistochastic Strings -- Approximation and Exact Algorithms for Special Cases of Connected f-Factors -- Rewriting Higher-Order Stack Trees -- Interacting with Modal Logics in the Coq Proof Assistant -- Delay Games with WMSOþU Winning Conditions -- Asymptotically Precise Ranking Functions for Deterministic Size-Change Systems.
Record Nr.	UNISA-996198516603316

Edizione	[1st ed. 2012.]
Pubbl/distr/stampa	Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2012
Descrizione fisica	1 online resource (XXIII, 327 p. 25 illus.)
Disciplina	005.1
Collana	Theoretical Computer Science and General Issues
Soggetto topico	Algorithms Computer science Machine theory Computer science—Mathematics Discrete mathematics Computer Science Logic and Foundations of Programming Formal Languages and Automata Theory Discrete Mathematics in Computer Science Theory of Computation Mathematics of Computing
ISBN	3-642-30642-X
Formato	Materiale a stampa
Livello bibliografico	Monografia
Lingua di pubblicazione	eng
Record Nr.	UNISA-996465274703316

Edizione	[1st ed. 2010.]
Pubbl/distr/stampa	Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010
Descrizione fisica	1 online resource (XI, 397 p. 49 illus.)
Disciplina	004.0151
Collana	Theoretical Computer Science and General Issues
Soggetto topico	Computer science Algorithms Machine theory Computer science—Mathematics Discrete mathematics Theory of Computation Computer Science Logic and Foundations of Programming Formal Languages and Automata Theory Discrete Mathematics in Computer Science
ISBN	1-280-38667-3 9786613564597 3-642-13182-4
Formato	Materiale a stampa
Livello bibliografico	Monografia
Lingua di pubblicazione	eng
Nota di contenuto	Algorithms for Energy Management -- Sofic and Almost of Finite Type Tree-Shifts -- Proof-Based Design of Security Protocols -- Approximating the Minimum Length of Synchronizing Words Is Hard -- Realizability of Dynamic MSC Languages -- The max quasi-independent set Problem -- Equilibria in Quantitative Reachability Games -- Quotient Complexity of Closed Languages -- Right-Sequential Functions on Infinite Words -- Kernelization -- Zigzags in Turing Machines -- Frameworks for Logically Classifying Polynomial-Time Optimisation Problems -- Validating the Knuth-Morris-Pratt Failure Function, Fast and Online -- Identical Relations in Symmetric Groups and Separating Words with Reversible Automata -- Time Optimal d-List Colouring of a Graph -- The Cantor Space as a Generic Model of Topologically Presented Knowledge -- Algorithmics – Is There Hope for a Unified Theory? -- Classifying Rankwidth k-DH-Graphs -- Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms -- A SAT Based Effective Algorithm for the Directed Hamiltonian Cycle Problem -- Balancing Bounded Treewidth Circuits -- Obtaining Online Ecological Colourings by Generalizing First-Fit -- Classical Simulation and Complexity of Quantum Computations -- Prefix-Free and Prefix-Correct Complexities with Compound Conditions -- Monotone Complexity of a Pair -- Symbolic Models for Single-Conclusion Proof Logics -- Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA -- Advancing Matrix Computations with Randomized Preprocessing -- Transfinite Sequences of Constructive Predicate Logics -- The Quantitative Analysis of User Behavior Online — Data, Models and Algorithms -- A Faster Exact Algorithm for the Directed Maximum Leaf Spanning Tree Problem -- Complexity of Propositional Proofs -- Quantization of Random Walks: Search Algorithms and Hitting Time -- Comparing Two Stochastic Local Search Algorithms for Constraint Satisfaction Problems -- Growth of Power-Free Languages over Large Alphabets -- A Partially Synchronizing Coloring -- An Encoding Invariant Version of Polynomial Time Computable Distributions -- Prehistoric Phenomena and Self-referentiality.
Record Nr.	UNISA-996465855203316