STACS 93
Springer Berlin (Verlag)
978-3-540-56503-1 (ISBN)
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 toincremental 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.
| Erscheint lt. Verlag | 19.2.1993 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science |
| Zusatzinfo | XIV, 730 p. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 928 g |
| Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
| Informatik ► Weitere Themen ► Hardware | |
| Schlagworte | algorithm • Algorithm analysis and problem complexity • Algorithmen • algorithms • Algorithmus • Automat • Automata • Automata Theory • Complexity • Computational Geometry • Computer • Computer Science • Computer Science Logic • Computer-Science-Logik • Distributed Computing • Hardcover, Softcover / Informatik, EDV/Informatik • HC/Informatik, EDV/Informatik • Informatik • Komplexität • Logic • Programmiersprache • Programmiersprachen • programming • Programming language • Programming Languages • Semantics • Verteiltes Rechnen • Verteilte Verarbeitung |
| ISBN-10 | 3-540-56503-5 / 3540565035 |
| ISBN-13 | 978-3-540-56503-1 / 9783540565031 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
