Fundamentals of Computation Theory: 10th International Conference, FCT ’95 Dresden, Germany, August 22–25, 1995 Proceedings

J. C. M. Baeten, J. A. Bergstra (auth.), Horst Reichel (eds.)3540602496, 9783540602491

This book presents the proceedings of the 10th International Conference on Fundamentals of Computation Theory, FCT ’95, held in Dresden, Germany in August 1995.
The volume contains five invited lectures and 32 revised papers carefully selected for presentation at FCT ’95. A broad spectrum of theoretical computer science is covered; among topics addressed are algorithms and data structures, automata and formal languages, categories and types, computability and complexity, computational logics, computational geometry, systems specification, learning theory, parallelism and concurrency, rewriting and high-level replacement systems, and semantics.

---

Table of contents :
Discrete time process algebra with abstraction….Pages 1-15
A duration calculus with infinite intervals….Pages 16-41
A delegation-based object calculus with subtyping….Pages 42-61
Model-checking for real-time systems….Pages 62-88
On polynomial ideals, their complexity, and applications….Pages 89-105
From a concurrent λ-calculus to the π-calculus….Pages 106-115
Rewriting regular inequalities….Pages 116-125
A simple abstract semantics for equational theories….Pages 126-135
Processes with multiple entries and exits….Pages 136-145
Efficient rewriting in cograph trace monoids….Pages 146-155
Effective category and measure in abstract complexity theory….Pages 156-170
About planar cayley graphs….Pages 171-180
On condorcet and median points of simple rectilinear polygons….Pages 181-190
Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs….Pages 191-200
r -Domination problems on homogeneously orderable graphs….Pages 201-210
Growing patterns in 1D cellular automata….Pages 211-220
Petri nets, commutative context-free grammars, and basic parallel processes….Pages 221-232
Implementation of a UU-algorithm for primitive recursive tree functions….Pages 233-242
Dummy elimination: Making termination easier….Pages 243-252
Computing Petri net languages by reductions….Pages 253-262
Categorial graphs….Pages 263-272
Effective systolic algorithms for gossiping in cycles and two-dimensional grids….Pages 273-282
Restarting automata….Pages 283-292
Optimal contiguous expression DAG evaluations….Pages 293-302
Communication as unification in the Petri Box Calculus….Pages 303-312
Distributed catenation and chomsky hierarchy….Pages 313-322
The power of frequency computation….Pages 323-332
Randomized incremental construction of simple abstract Voronoi diagrams in 3-space….Pages 333-342
Properties of probabilistic pushdown automata….Pages 343-352
Formal parametric equations….Pages 353-362
PRAM’s towards realistic parallelism: BRAM’s….Pages 363-373
Some results concerning two-dimensional turing machines and finite automata….Pages 374-382
How hard is to compute the edit distance….Pages 383-392
On the synchronization of semi-traces….Pages 393-403
Tiling with bars and satisfaction of boolean formulas….Pages 404-413
Axiomatizing Petri net concatenable processes….Pages 414-423
Functional sorts in data type specifications….Pages 424-433