Mathematical Foundations of Computer Science 1996

Word level model checking.- Code problems on traces.- Models of DNA computation.- Theory and practice of action semantics.- Linear time temporal logics over Mazurkiewicz traces.- Partial order reduction: Model-checking using representatives.- Nonmonotonic rule systems: Forward chaining, constraints, and complexity.- Mind the gap! Abstract versus concrete models of specifications.- A sequent calculus for subtyping polymorphic types.- Kolmogorov complexity: Recent research in Moscow.- A modal logic for data analysis.- From specifications to programs: A fork-algebraic approach to bridge the gap.- Logic of predicates with explicit substitutions.- On the query complexity of sets.- A Lambda Calculus of incomplete objects.- Bisimilarity problems requiring exponential time (Extended abstract).- Linear dynamic Kahn networks are deterministic.- Shortest path problems with time constraints.- Parallel Alternating-Direction Access Machine.- Specification and verification of timed lazy systems.- A class of information logics with a decidable validity problem.- On the power of nonconservative PRAM.- Self-similarity viewed as a local property via tile sets.- Simulation of specification statements in Hoare logic.- Equational properties of iteration in algebraically complete categories.- On unconditional transfer.- (poly(log log n), poly(log log n))—Restricted verifiers are unlikely to exist for languages in $$\mathcal{N}\mathcal{P}$$ *.- Minimizing congestion of layouts for ATM networks with faulty links.- Polynomial automaticity, context-free languages, and fixed points of morphisms (Extended abstract).- Causal testing.- Construction of list homomorphisms by tupling and fusion.- Probabilistic metric semantics for a simple language with recursion.- Dynamic graphs.- Equations on trees.- On the equivalence problem for E-pattern languages.- Specifying and verifying parametric processes.- On saturation with flexible function symbols.- Approximating good simultaneous Diophantine approximations is almost NP-hard.- On the conjugation of Standard morphisms.- A semantic matching algorithm: Analysis and implementation.- Routing on triangles, tori and honeycombs.- A uniform analysis of trie structures that store prefixing-keys with application to doubly-chained prefixing-tries.- On fairness in terminating and reactive programs.- Polynomial time samplable distributions.- From static to dynamic abstract data-types.