Giorgio Ausiello, Giuseppe F. Italiano (auth.), Luboš Brim, Jozef Gruska, Jiří Zlatuška (eds.)3540648275, 9783540648277
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..
Table of contents :
Hypergraph traversal revisited: Cost measures and dynamic algorithms….Pages 1-16
Defining the Java Virtual Machine as platform for provably correct Java compilation….Pages 17-35
Towards a theory of recursive structures….Pages 36-53
Modularization and abstraction: The keys to practical formal verification….Pages 54-71
On the role of time and space in neural computation….Pages 72-83
From algorithms to working programs: On the use of program checking in LEDA….Pages 84-93
Computationally-sound checkers….Pages 94-116
Reasoning about the past….Pages 117-128
Satisfiability — Algorithms and logic….Pages 129-141
The joys of bisimulation….Pages 142-151
Towards algorithmic explanation of mind evolution and functioning….Pages 152-166
Combinatorial hardness proofs for polynomial evaluation….Pages 167-175
Minimum propositional proof length is NP-hard to linearly approximate….Pages 176-184
Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms….Pages 185-193
Locally explicit construction of rődl’s asymptotically good packings….Pages 194-202
Proof theory of fuzzy logics: Urquhart’s C and related logics….Pages 203-212
Nonstochastic languages as projections of 2-tape quasideterministic languages….Pages 213-219
Flow logic for Imperative Objects….Pages 220-228
Expressive completeness of Temporal Logic of action….Pages 229-238
Reducing AC-termination to termination….Pages 239-247
On one-pass term rewriting….Pages 248-256
On the word, subsumption, and complement problem for recurrent term schematizations….Pages 257-266
Encoding the hydra battle as a rewrite system….Pages 267-276
Computing ε-free NFA from regular expressions in O( n log 2 ( N )) time….Pages 277-285
Iterated length-preserving rational transductions….Pages 286-295
The head hierarchy for oblivious finite automata with polynomial advice collapses….Pages 296-304
The equivalence problem for deterministic pushdown transducers into abelian groups….Pages 305-315
The semi-full closure of Pure Type Systems….Pages 316-325
Predicative polymorphic subtyping….Pages 326-335
A computational interpretation of the λΜ-calculus….Pages 336-345
Polymorphic subtyping without distributivity….Pages 346-355
A (non-elementary) modular decision procedure for LTrL….Pages 356-365
Complete abstract interpretations made constructive….Pages 366-377
Timed bisimulation and open maps….Pages 378-387
Deadlocking states in context-free process algebra….Pages 388-398
A superpolynomial lower bound for a circuit computing the clique function with at most (1/6) log log n negation gates….Pages 399-408
On counting ac 0 circuits with negative constants….Pages 409-417
A second step towards circuit complexity-theoretic analogs of Rice’s theorem….Pages 418-426
Model checking Real-Time properties of symmetric systems….Pages 427-436
Locality of order-invariant first-order formulas….Pages 437-445
Probabilistic concurrent constraint programming: Towards a fully abstract model….Pages 446-455
Lazy functional algorithms for exact real functionals….Pages 456-464
Randomness vs. completeness: On the diagonalization strength of resource-bounded random sets….Pages 465-473
Positive turing and truth-table completeness for NEXP are incomparable….Pages 474-482
Tally NP sets and easy census functions….Pages 483-492
Average-case intractability vs. worst-case intractability….Pages 493-502
Shuffle on trajectories: The schützenberger product and related operations….Pages 503-511
Gaußian elimination and a characterization of algebraic power series….Pages 512-521
D0L-systems and surface automorphisms….Pages 522-532
About synchronization languages….Pages 533-542
When can an equational simple graph be generated by hyperedge replacement?….Pages 543-552
Spatial and temporal refinement of typed graph transformation systems….Pages 553-561
Approximating maximum independent sets in uniform hypergraphs….Pages 562-570
Representing hyper-graphs by regular languages….Pages 571-579
Improved time and space hierarchies of one-tape off-line TMs….Pages 580-588
Tarskian set constraints are in NEXPTIME….Pages 589-596
Speeding-up nondeterministic single-tape off-line computations by one alternation….Pages 597-606
Facial circuits of planar graphs and context-free languages….Pages 607-615
Optimizing OBDDs is still intractable for monotone functions….Pages 616-624
Blockwise variable orderings for shared BDDs….Pages 625-635
On the composition problem for OBDDs with multiple variable orders….Pages 636-644
Equations in transfinite strings….Pages 645-655
Minimal forbidden words and factor automata….Pages 656-664
On defect effect of bi-infinite words….Pages 665-673
On repetition-free binary words of minimal density….Pages 674-682
Embedding of hypercubes into grids….Pages 683-692
Tree decompositions of small diameter….Pages 693-701
Degree-preserving forests….Pages 702-712
A parallelization of Dijkstra’s shortest path algorithm….Pages 713-721
Comparison between the complexity of a function and the complexity of its graph….Pages 722-731
IFS and control languages….Pages 732-739
One quantifier will do in existential monadic second-order logic over pictures….Pages 740-750
On some recognizable picture-languages….Pages 751-759
On the complexity of wavelength converters….Pages 760-770
On Boolean vs. Modular arithmetic for circuits and communication protocols….Pages 771-779
Communication complexity and lower bounds on multilective computations….Pages 780-788
A finite hierarchy of the recursively enumerable real numbers….Pages 789-797
One guess one-way cellular arrays….Pages 798-806
Topological definitions of chaos applied to cellular automata dynamics….Pages 807-815
Characterization of sensitive linear cellular automata with respect to the counting distance….Pages 816-824
Additive cellular automata over ℤ p and the bottom of (CA,≤)….Pages 825-833
….Pages 834-843
Reviews
There are no reviews yet.