Computer Science - Theory and Applications [[electronic resource] ] : Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009, Proceedings / / edited by Anna Frid, Andrei S. Morozov, Andrey Rybalchenko, Klaus W. Wagner |
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 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2009 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
STACS 93 [[electronic resource] ] : 10th Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 25-27, 1993. Proceedings / / edited by Patrice Enjalbert, Alain Finkel, Klaus W. Wagner |
Edizione | [1st ed. 1993.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 1993 |
Descrizione fisica | 1 online resource (XIV, 730 p.) |
Disciplina | 004.0151 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Computers
Algorithms Computer logic Mathematical logic Arithmetic and logic units, Computer Theory of Computation Computation by Abstract Devices Algorithm Analysis and Problem Complexity Logics and Meanings of Programs Mathematical Logic and Formal Languages Arithmetic and Logic Structures |
ISBN | 3-540-47574-5 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Causal and distributed semantics for concurrent processes -- Editorial note -- Alternation for two-way machines with sublogarithmic space -- Separating the lower levels of the sublogarithmic space hierarchy -- Locating P/poly optimally in the extended low hierarchy -- Measure, stochasticity, and the density of hard languages -- Halting problem of one binary Horn clause is undecidable -- Decidability and undecidability results for duration calculus -- Defining ?-typed ?-calculi by axiomatizing the typing relation -- The complexity of logic-based abduction -- Treewidth of chordal bipartite graphs -- On paths in networks with valves -- Scheduling interval ordered tasks in parallel -- An O(?n)-worst-case-time solution to the granularity problem -- The synthesis problem of Petri nets -- General refinement and recursion operators for the Petri Box calculus -- On fairness in distributed automated deduction -- Divide-and-conquer algorithms on the hypercube -- A first-order isomorphism theorem -- Splittings, robustness and structure of complete sets -- Defying upward and downward separation -- Counting, selecting, and sorting by query-bounded machines -- Cancellation in context-free languages: Enrichment by reduction -- Counting overlap-free binary words -- The limit set of recognizable substitution systems -- Partially commutative Lyndon words -- Parallel architectures: Design and efficient use -- Weighted closest pairs -- Rectilinear path queries in a simple rectilinear polygon -- Parallel algorithm for the matrix chain product and the optimal triangulation problems (extended abstract) -- Multi-list ranking: complexity and applications -- Exact algorithms for a geometric packing problem (extended abstract) -- A decomposition theorem for probabilistic transition systems -- Local automata and completion -- Efficient compression of wavelet coefficients for smooth and fractal-like data -- On the equivalence of two-way pushdown automata and counter machines over bounded languages -- Computability properties of low-dimensional dynamical systems -- Fixed-parameter intractability II (extended abstract) -- Limits on the power of parallel random access machines with weak forms of write conflict resolution -- On using oracles that compute values -- Multicounter automata with sublogarithmic reversal bounds -- Structured operational semantics for concurrency and hierarchy -- The complexity of verifying functional programs -- Towards the formal design of self-stabilizing distributed algorithms -- Axiomatizations of temporal logics on trace systems -- Capabilities and complexity of computations with integer division -- Extended locally definable acceptance types -- Gap-definability as a closure property -- On the logical definability of some rational trace languages -- Solving systems of set constraints using tree automata -- Complement problems and tree automata in AC-like theories (extended abstract) -- Transparent (holographic) proofs -- Computing symmetric functions with AND/OR circuits and a single MAJORITY gate -- Threshold circuits for iterated multiplication: Using AC0 for free -- Circuits with monoidal gates -- A non-probabilistic switching lemma for the Sipser function -- Frontiers of feasible and probabilistic feasible Boolean manipulation with branching programs -- On syntactic congruences for ?—languages -- A polynomial time algorithm for the equivalence of two morphisms on ?-regular languages -- Locally threshold testable languages of infinite words -- Deterministic asynchronous automata for infinite traces -- Recursive automata on infinite words -- A complexity theoretic approach to incremental computation -- Precise average case complexity -- The bit probe complexity measure revisited -- Language learning with some negative information -- Language learning with a bounded number of mind changes -- Efficient sharing of many secrets -- The KIV system a tool for formal program development -- 1st Grade — A system for implementation, testing and animation of graph algorithms -- The program verifier Tatzelwurm -- LEDA a library of efficient data types and algorithms -- Defining ?-typed ?-calculi by axiomatizing the typing relation. |
Record Nr. | UNISA-996466078103316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 1993 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
STACS 94 [[electronic resource] ] : 11th Annual Symposium on Theoretical Aspects of Computer Science Caen, France, February 24–26, 1994 Proceedings / / edited by Patrice Enjalbert, Ernst W. Mayr, Klaus W. Wagner |
Edizione | [1st ed. 1994.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 1994 |
Descrizione fisica | 1 online resource (XIV, 786 p. 9 illus.) |
Disciplina | 004.0151 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Computers
Algorithms Computer logic Mathematical logic Computer programming Theory of Computation Computation by Abstract Devices Algorithm Analysis and Problem Complexity Logics and Meanings of Programs Mathematical Logic and Formal Languages Programming Techniques |
ISBN | 3-540-48332-2 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | The nature and meaning of perturbations in geometric computing -- One binary horn clause is enough -- Transforming constraint logic programs -- A hierarchy of temporal logics with past -- The complexity of resource-bounded first-order classical logic -- Two proof procedures for a cardinality based language in propositional calculus -- The alternation hierarchy for machines with sublogarithmic space is infinite -- Quasilinear time complexity theory -- Space-efficient deterministic simulation of probabilistic automata -- Reachability and the power of local ordering -- Are parallel machines always faster than sequential machines? -- Ground reducibility and automata with disequality constraints -- Perpetuality and strong normalization in orthogonal term rewriting systems -- About changing the ordering during Knuth-Bendix completion -- Combination of matching algorithms -- Periodic constant depth sorting networks -- Optimal pattern matching on meshes -- Faster sorting and routing on grids with diagonals -- Deterministic 1 -k routing on meshes with applications to worm-hole routing -- A unifying type-theoretic framework for objects -- Operational specifications with built-ins -- Reactive variables for system specification and design -- A new parallel vector model, with exact characterization of NCk -- On adaptive dlogtime and polylogtime reductions -- NCk(NP)=AC k?1(NP) -- Hypertransition systems -- On the star operation and the finite power property in free partially commutative monoids -- Coding with traces -- Monadic second-order logic over pictures and recognizability by tiling systems -- Q-grammars: Results, implementation -- A topology for complete semirings -- The global power of additional queries to random oracles -- Cook versus Karp-Levin: Separating completeness notions if NP is not small -- On sets bounded truth-table reducible to P-selective sets -- Two refinements of the polynomial hierarchy -- On different reducibility notions for function classes -- Optimal parallelization of Las Vegas algorithms -- Efficient parallel algorithms for geometric k-clustering problems -- A simple optimal parallel algorithm for reporting paths in a tree -- Parallel detection of all palindromes in a string -- On the structure of parameterized problems in NP -- On the approximability of finding maximum feasible subsystems of linear systems -- On the acceptance power of regular languages -- Complexity classes with finite acceptance types -- The complete axiomatization of Cs-congruence -- Transition system specifications in stalk format with bisimulation as a congruence -- Decidability questions for bisimilarity of Petri nets and some related problems -- The variable membership problem: Succinctness versus complexity -- Economy of description for single-valued transducers -- Automaticity: Properties of a measure of descriptional complexity -- Towards a theory of recursive structures -- Finding minimal generalizations for unions of pattern languages and its application to inductive inference from positive data -- Nondeterminism in patterns -- Upper bounds for the expected length of a longest common subsequence of two binary sequences -- The ambiguity of primitive words -- On codes having no finite completion -- A new approach to information theory -- On Voronoi diagrams in the L p -metric in higher dimensions -- Total protection of analytic invariant information in cross tabulated tables -- Dominating cliques in graphs with hypertree structure -- On vertex ranking for permutation and other graphs -- Finding all minimal separators of a graph -- On the complexity of the maximum cut problem. |
Record Nr. | UNISA-996466031603316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 1994 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|