Buch, Englisch, 854 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 1291 g
Buch, Englisch, 854 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 1291 g
Reihe: Lecture Notes in Computer Science
ISBN: 978-3-540-64827-7
Verlag: Springer
The 71 revised full papers presented were carefully reviewed and selected from a total of 168 submissions. Also included are 11 full invited surveys by prominent leaders in the area. The papers are organized in topical sections on problem complexity; logic, semantics, and automata; rewriting; automata and transducers; typing; concurrency, semantics, and logic; circuit complexity; programming; structural complexity; formal languages; graphs; Turing complexity and logic; binary decision diagrams, etc..
Zielgruppe
Research
Autoren/Hrsg.
Weitere Infos & Material
Hypergraph traversal revisited: Cost measures and dynamic algorithms.- Defining the Java Virtual Machine as platform for provably correct Java compilation.- Towards a theory of recursive structures.- Modularization and abstraction: The keys to practical formal verification.- On the role of time and space in neural computation.- From algorithms to working programs: On the use of program checking in LEDA.- Computationally-sound checkers.- Reasoning about the past.- Satisfiability — Algorithms and logic.- The joys of bisimulation.- Towards algorithmic explanation of mind evolution and functioning.- Combinatorial hardness proofs for polynomial evaluation.- Minimum propositional proof length is NP-hard to linearly approximate.- Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms.- Locally explicit construction of r?dl's asymptotically good packings.- Proof theory of fuzzy logics: Urquhart's C and related logics.- Nonstochastic languages as projections of 2-tape quasideterministic languages.- Flow logic for Imperative Objects.- Expressive completeness of Temporal Logic of action.- Reducing AC-termination to termination.- On one-pass term rewriting.- On the word, subsumption, and complement problem for recurrent term schematizations.- Encoding the hydra battle as a rewrite system.- Computing ?-free NFA from regular expressions in O(n log2(N)) time.- Iterated length-preserving rational transductions.- The head hierarchy for oblivious finite automata with polynomial advice collapses.- The equivalence problem for deterministic pushdown transducers into abelian groups.- The semi-full closure of Pure Type Systems.- Predicative polymorphic subtyping.- A computational interpretation of the ??-calculus.- Polymorphic subtyping withoutdistributivity.- A (non-elementary) modular decision procedure for LTrL.- Complete abstract interpretations made constructive.- Timed bisimulation and open maps.- Deadlocking states in context-free process algebra.- A superpolynomial lower bound for a circuit computing the clique function with at most (1/6) log log n negation gates.- On counting ac 0 circuits with negative constants.- A second step towards circuit complexity-theoretic analogs of Rice's theorem.- Model checking Real-Time properties of symmetric systems.- Locality of order-invariant first-order formulas.- Probabilistic concurrent constraint programming: Towards a fully abstract model.- Lazy functional algorithms for exact real functionals.- Randomness vs. completeness: On the diagonalization strength of resource-bounded random sets.- Positive turing and truth-table completeness for NEXP are incomparable.- Tally NP sets and easy census functions.- Average-case intractability vs. worst-case intractability.- Shuffle on trajectories: The schützenberger product and related operations.- Gaußian elimination and a characterization of algebraic power series.- D0L-systems and surface automorphisms.- About synchronization languages.- When can an equational simple graph be generated by hyperedge replacement?.- Spatial and temporal refinement of typed graph transformation systems.- Approximating maximum independent sets in uniform hypergraphs.- Representing hyper-graphs by regular languages.- Improved time and space hierarchies of one-tape off-line TMs.- Tarskian set constraints are in NEXPTIME.- ??*-Equational theory of context unification is ? 1 0 -hard.- Speeding-up nondeterministic single-tape off-line computations by one alternation.- Facial circuits of planar graphs and context-free languages.-Optimizing OBDDs is still intractable for monotone functions.- Blockwise variable orderings for shared BDDs.- On the composition problem for OBDDs with multiple variable orders.- Equations in transfinite strings.- Minimal forbidden words and factor automata.- On defect effect of bi-infinite words.- On repetition-free binary words of minimal density.- Embedding of hypercubes into grids.- Tree decompositions of small diameter.- Degree-preserving forests.- A parallelization of Dijkstra's shortest path algorithm.- Comparison between the complexity of a function and the complexity of its graph.- IFS and control languages.- One quantifier will do in existential monadic second-order logic over pictures.- On some recognizable picture-languages.- On the complexity of wavelength converters.- On Boolean vs. Modular arithmetic for circuits and communication protocols.- Communication complexity and lower bounds on multilective computations.- A finite hierarchy of the recursively enumerable real numbers.- One guess one-way cellular arrays.- Topological definitions of chaos applied to cellular automata dynamics.- Characterization of sensitive linear cellular automata with respect to the counting distance.- Additive cellular automata over ?p and the bottom of (CA,?).
