Fundamentals of Computation Theory: 10th International Conference, FCT '95, Dresden, Germany, August 22 - 25, 1995. Proceedings (Lecture Notes in Computer Science (965))

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. 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 Discrete Time Process Algebra With Abstraction / J.c.m. Baeten And J.a. Bergstra -- A Duration Calculus With Infinite Intervals / Z. Chaochen, D.v. Hung And L. Xiaoshan -- A Delegation-based Object Calculus With Subtyping / K. Fisher And J.c. Mitchell -- Model-checking For Real-time Systems / K.g. Larsen, P. Pettersson And W. Yi -- On Polynomial Ideals, Their Complexity, And Applications / E.w. Mayr -- From A Concurrent [lambda]-calculus To The [pi]-calculus / R.m. Amadio, L. Leth And B. Thomsen -- Rewriting Regular Inequalities / V. Antimirov -- A Simple Abstract Semantics For Equational Theories / G. Barthe -- Processes With Multiple Entries And Exits / J.a. Bergstra And G.h. Stefanescu -- Efficient Rewriting In Cograph Trace Monoids / M. Bertol -- Effective Category And Measure In Abstract Complexity Theory / C. Calude And M. Zimand -- About Planar Cayley Graphs / Th. Chaboud. Horst Reichel, (ed.). Includes Bibliographical References. Process algebra in the form of ACP [BEK85, BAW90], CCS [MIL89] or CSP [BRHR84] involves no explicit mention of time.