Fundamentals of Computation Theory

The complexity class ? p 2 : Recent results and applications in AI and modal logic.- Proof systems for structured algebraic specifications: An overview.- Average-case analysis via incompressibility.- Locally computable enumerations.- The complexity of error-correcting codes.- Stochastic analysis of dynamic processes.- k-k Sorting on the multi-mesh.- Refinement of coloured petri nets.- Stratified petri nets.- Distributed acyclic orientation of asynchronous anonymous networks.- Generalized rational relations and their logical definability.- A note on broadcasting with linearly bounded transmission faults in constant degree networks.- Logics which capture complexity classes over the reals.- Criteria to disprove context-freeness of collage languages.- The subword complexity of fixed points of binary uniform morphisms.- Efficient parallel computing with memory faults.- Bounded concurrency.- Concerning the time bounds of existing shortest watchman route algorithms.- Query order in the polynomial hierarchy.- Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria.- Pattern-matching problems for 2-dimensional images described by finite automata.- The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups.- Contextual grammars with distributed catenation and shuffle.- A two-dimensional hierarchy for attributed tree transducers.- Synchronization of 1-way connected processors.- A linear-time heuristic for minimum rectangular coverings (Extended abstract).- On occurrence net semantics for petri nets with contacts.- Cellular automata universality revisited.- Trade-off results for connection management.- On the average complexity of the membership problem for a generalized Dyck language.- Towards optimal locality in mesh-indexings.- On the hierarchy of nondeterministic branching k-programs.- FDT is undecidable for finitely presented monoids with solvable word problems.- The equivalence of pebbles and sensing heads for finite automata.- From finite automata toward hybrid systems (Extended abstract).- On an optimal quantified propositional proof system nal proof system and a complete language for NP ? co-NP for NP ? co-NP.- Lower bounds in on-line geometric searching metric searching.- The complexity of universal text-learners.- Unique normal forms for nonlinear term rewriting systems: Root overlaps.- Behavioural characterizations of partial order logics.