Computer Science - Theory and Applications [[electronic resource] ] : Second International Symposium on Computer Science in Russia, CSR 2007, Ekaterinburg, Russia, September 3-7, 2007, Proceedings / / edited by Volker Diekert, Mikhail Volkov, Andrei Voronkov |
Edizione | [1st ed. 2007.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2007 |
Descrizione fisica | 1 online resource (XIII, 420 p.) |
Disciplina | 004.0947 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Computer science
Algorithms Artificial intelligence Computer science—Mathematics Bioinformatics Theory of Computation Artificial Intelligence Mathematics of Computing |
ISBN | 3-540-74510-6 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Proving Church’s Thesis -- The Limits of Quantum Computers -- Marrying Words and Trees -- TPTP, TSTP, CASC, etc. -- Abstract Modeling and Formal Verification of Microprocessors -- Sequences of Level 1, 2, 3,..., k,... -- Timers and Proximities for Mobile Ambients -- Pushing Random Walk Beyond Golden Ratio -- Reversible Machine Code and Its Abstract Processor Architecture -- A Fast Algorithm for Path 2-Packing Problem -- Decidability of Parameterized Probabilistic Information Flow -- Inverting Onto Functions and Polynomial Hierarchy -- Proved-Patterns-Based Development for Structured Programs -- Planarity, Determinants, Permanents, and (Unique) Matchings -- Equivalence Problems for Circuits over Sets of Natural Numbers -- Bouillon: A Wiki-Wiki Social Web -- A PDL-Like Logic of Knowledge Acquisition -- Resource Placement in Networks Using Chromatic Sets of Power Graphs -- Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth -- Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems -- New Bounds for MAX-SAT by Clause Learning -- Towards Hierarchical Clustering (Extended Abstract) -- Estimation of the Click Volume by Large Scale Regression Analysis -- Maximal Intersection Queries in Randomized Graph Models -- A Note on Specialization of Interpreters -- Efficient Computation in Groups Via Compression -- Constructing a Secret Binary Partition of a Digital Image Robust to a Loss of Synchronization -- On the Complexity of Matrix Rank and Rigidity -- On the Usage of Clustering for Content Based Image Retrieval -- Performance Modeling of Wormhole Hypermeshes Under Hotspot Traffic -- Application of Modified Coloured Petri Nets to Modeling and Verification of SDL Specified Communication Protocols -- Symmetry of Information and Nonuniform Lower Bounds -- Perceptrons of Large Weight -- A Padding Technique on Cellular Automata to Transfer Inclusions of Complexity Classes -- Kolmogorov Complexity, Lovász Local Lemma and Critical Exponents -- Generic Complexity of Presburger Arithmetic -- Everywhere ?-Repetitive Sequences and Sturmian Words -- Timed Traces and Strand Spaces -- On Empirical Meaning of Randomness with Respect to a Real Parameter -- An Efficient Algorithm for Zero-Testing of a Lacunary Polynomial at the Roots of Unity -- Generic Complexity of Undecidable Problems. |
Record Nr. | UNISA-996466094503316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2007 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Computer Science - Theory and Applications : Second International Symposium on Computer Science in Russia, CSR 2007, Ekaterinburg, Russia, September 3-7, 2007, Proceedings / / edited by Volker Diekert, Mikhail Volkov, Andrei Voronkov |
Edizione | [1st ed. 2007.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2007 |
Descrizione fisica | 1 online resource (XIII, 420 p.) |
Disciplina | 004.0947 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Computer science
Algorithms Artificial intelligence Computer science—Mathematics Bioinformatics Theory of Computation Artificial Intelligence Mathematics of Computing |
ISBN | 3-540-74510-6 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Proving Church’s Thesis -- The Limits of Quantum Computers -- Marrying Words and Trees -- TPTP, TSTP, CASC, etc. -- Abstract Modeling and Formal Verification of Microprocessors -- Sequences of Level 1, 2, 3,..., k,... -- Timers and Proximities for Mobile Ambients -- Pushing Random Walk Beyond Golden Ratio -- Reversible Machine Code and Its Abstract Processor Architecture -- A Fast Algorithm for Path 2-Packing Problem -- Decidability of Parameterized Probabilistic Information Flow -- Inverting Onto Functions and Polynomial Hierarchy -- Proved-Patterns-Based Development for Structured Programs -- Planarity, Determinants, Permanents, and (Unique) Matchings -- Equivalence Problems for Circuits over Sets of Natural Numbers -- Bouillon: A Wiki-Wiki Social Web -- A PDL-Like Logic of Knowledge Acquisition -- Resource Placement in Networks Using Chromatic Sets of Power Graphs -- Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth -- Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems -- New Bounds for MAX-SAT by Clause Learning -- Towards Hierarchical Clustering (Extended Abstract) -- Estimation of the Click Volume by Large Scale Regression Analysis -- Maximal Intersection Queries in Randomized Graph Models -- A Note on Specialization of Interpreters -- Efficient Computation in Groups Via Compression -- Constructing a Secret Binary Partition of a Digital Image Robust to a Loss of Synchronization -- On the Complexity of Matrix Rank and Rigidity -- On the Usage of Clustering for Content Based Image Retrieval -- Performance Modeling of Wormhole Hypermeshes Under Hotspot Traffic -- Application of Modified Coloured Petri Nets to Modeling and Verification of SDL Specified Communication Protocols -- Symmetry of Information and Nonuniform Lower Bounds -- Perceptrons of Large Weight -- A Padding Technique on Cellular Automata to Transfer Inclusions of Complexity Classes -- Kolmogorov Complexity, Lovász Local Lemma and Critical Exponents -- Generic Complexity of Presburger Arithmetic -- Everywhere ?-Repetitive Sequences and Sturmian Words -- Timed Traces and Strand Spaces -- On Empirical Meaning of Randomness with Respect to a Real Parameter -- An Efficient Algorithm for Zero-Testing of a Lacunary Polynomial at the Roots of Unity -- Generic Complexity of Undecidable Problems. |
Record Nr. | UNINA-9910484139303321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2007 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|
Developments in language theory : 13th international conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009 : proceedings / / Volker Diekert, Dirk Nowotka, eds |
Edizione | [1st ed. 2009.] |
Pubbl/distr/stampa | Berlin ; ; New York, : Springer, c2009 |
Descrizione fisica | 1 online resource (XIII, 503 p.) |
Disciplina | 005.131 |
Altri autori (Persone) |
DiekertVolker <1955->
NowotkaDirk |
Collana |
Lecture notes in computer science
LNCS sublibrary.SL 1,Theoretical computer science and general issues |
Soggetto topico |
Computational linguistics
Formal languages |
ISBN |
1-280-38307-0
9786613560988 3-642-02737-7 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Invited Talks -- Factorization Forests -- Weighted versus Probabilistic Logics -- Post Correspondence Problem and Small Dimensional Matrices -- Size Complexity of Two-Way Finite Automata -- Matrix Mortality and the ?erný-Pin Conjecture -- Regular Papers -- A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata -- Regular Languages Definable by Majority Quantifiers with Two Variables -- The Inclusion Problem of Context-Free Languages: Some Tractable Cases -- On the Complexity of Deciding Avoidability of Sets of Partial Words -- Closures in Formal Languages and Kuratowski’s Theorem -- Rich and Periodic-Like Words -- Traces of Control-Flow Graphs -- Left and Right Synchronous Relations -- An Extension of the Lyndon Schützenberger Result to Pseudoperiodic Words -- Asymptotic Cellular Complexity -- Strongly Regular Grammars and Regular Approximation of Context-Free Languages -- Powers of Regular Languages -- Existence and Nonexistence of Descriptive Patterns -- On Stateless Multihead Finite Automata and Multihead Pushdown Automata -- On Negative Bases -- Crucial Words for Abelian Powers -- Tight Bounds on the Descriptional Complexity of Regular Expressions -- Subshifts, Languages and Logic -- Magic Numbers and Ternary Alphabet -- The Pumping Lemma for Well-Nested Multiple Context-Free Languages -- The Support of a Recognizable Series over a Zero-Sum Free, Commutative Semiring Is Recognizable -- A Game-Theoretic Characterization of Boolean Grammars -- Word Equations with One Unknown -- On Equations over Sets of Numbers and Their Limitations -- Some Remarks on Superposition Based on Watson-Crick-Like Complementarity -- A Weighted ?-Calculus on Words -- Branching-Time Temporal Logics with Minimal Model Quantifiers -- Simulations by Time-Bounded Counter Machines -- Weighted Timed MSO Logics -- Balanced Words Having Simple Burrows-Wheeler Transform -- On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations -- Definability in the Infix Order on Words -- Two-Sided Bounds for the Growth Rates of Power-Free Languages -- On the Decidability of the Equivalence for a Certain Class of Transducers -- Erasing in Petri Net Languages and Matrix Grammars. |
Record Nr. | UNINA-9910484925903321 |
Berlin ; ; New York, : Springer, c2009 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|
STACS 2005 : 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005 : proceedings / / Volker Diekert, Bruno Durand (eds.) |
Edizione | [1st ed. 2005.] |
Pubbl/distr/stampa | Berlin ; ; New York, : Springer, c2005 |
Descrizione fisica | 1 online resource (XVI, 706 p.) |
Disciplina | 004 |
Altri autori (Persone) |
DiekertVolker <1955->
DurandB (Bruno) |
Collana | Lecture notes in computer science |
Soggetto topico | Computer science |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Invited Talks -- Automorphisms of Finite Rings and Applications to Complexity of Problems -- Algebraic Generating Functions in Enumerative Combinatorics and Context-Free Languages -- Algorithmics in Exponential Time -- Session 1A -- Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics -- Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms -- Truthful Approximation Mechanisms for Scheduling Selfish Related Machines -- Session 1B -- Counting in the Two Variable Guarded Logic with Transitivity -- The Variable Hierarchy of the ?-Calculus Is Strict -- The Core of a Countably Categorical Structure -- Session 2A -- How Common Can Be Universality for Cellular Automata? -- Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods -- Session 2B -- On the Decidability of Temporal Properties of Probabilistic Pushdown Automata -- Deciding Properties of Contract-Signing Protocols -- Session 3A -- Polylog-Time Reductions Decrease Dot-Depth -- On the Computational Complexity of the Forcing Chromatic Number -- More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP -- Session 3B -- Three Optimal Algorithms for Balls of Three Colors -- Cost Sharing and Strategyproof Mechanisms for Set Cover Games -- On Weighted Balls-into-Bins Games -- Session 4A -- Computing Minimal Multi-homogeneous Bézout Numbers Is Hard -- Dynamic Complexity Theory Revisited -- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size -- Session 4B -- Shortest Monotone Descent Path Problem in Polyhedral Terrain -- Packet Buffering: Randomization Beats Deterministic Algorithms -- Solving Medium-Density Subset Sum Problems in Expected Polynomial Time -- Session 5A -- Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms -- Regular Tree Languages Definable in FO -- Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations -- Session 5B -- Connectivity for Wireless Agents Moving on a Cycle or Grid -- Improved Algorithms for Dynamic Page Migration -- Approximate Range Mode and Range Median Queries -- Session 6A -- Topological Automata -- Minimizing NFA’s and Regular Expressions -- Session 6B -- Increasing Kolmogorov Complexity -- Kolmogorov-Loveland Randomness and Stochasticity -- Session 7A -- Information Theory in Property Testing and Monotonicity Testing in Higher Dimension -- On Nash Equilibria in Non-cooperative All-Optical Networks -- Speed Scaling to Manage Temperature -- Session 7B -- The Complexity of Solving Linear Equations over a Finite Ring -- A Lower Bound on the Complexity of Polynomial Multiplication Over Finite Fields -- Characterizing TC0 in Terms of Infinite Groups -- Session 8A -- Fast Pruning of Geometric Spanners -- The PIGs Full Monty – A Floor Show of Minimal Separators -- Centrality Measures Based on Current Flow -- Session 8B -- Varieties of Codes and Kraft Inequality -- Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes -- The Power of Commuting with Finite Sets of Words -- Session 9A -- Exact Quantum Algorithms for the Leader Election Problem -- Robust Polynomials and Quantum Algorithms -- Quantum Interactive Proofs with Competing Provers -- Session 9B -- Roundings Respecting Hard Constraints -- Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves -- Cycle Cover with Short Cycles -- Session 10A -- A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs -- All-Pairs Nearly 2-Approximate Shortest-Paths in O(n 2 polylog n) Time -- Session 10B -- Pattern Occurrences in Multicomponent Models -- Automatic Presentations for Finitely Generated Groups. |
Altri titoli varianti |
22nd Annual Symposium on Theoretical Aspects of Computer Science
Symposium on Theoretical Aspects of Computer Science Theoretical aspects of computer science |
Record Nr. | UNINA-9910484929903321 |
Berlin ; ; New York, : Springer, c2005 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|