This book constitutes the refereed proceedings of the 11th International Symposium on Fundamentals of Computer Theory, FCT'97, held in Krakow, Poland, in September 1997.
The 34 revised full papers presented in the volume were selected from a total of 72 submissions. Also included are six invited papers by leading scientists. The papers address a variety of current topics in theoretical computer science including models of computation, concurrency, algorithms, complexity theory, programming theory, formal languages, graph theory and discrete mathematics, networking, automata theory, term rewriting, etc.
Author(s): Thomas Eiter, Georg Gottlob (auth.), Bogdan S. Chlebus, Ludwik Czaja (eds.)
Series: Lecture Notes in Computer Science 1279
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1997
Language: English
Pages: 484
Tags: Theory of Computation; Discrete Mathematics in Computer Science; Computer Graphics; Data Structures
Proof systems for structured algebraic specifications: An overview....Pages 1-18
Average-case analysis via incompressibility....Pages 19-37
Locally computable enumerations....Pages 38-50
The complexity of error-correcting codes....Pages 51-66
Stochastic analysis of dynamic processes....Pages 67-84
k-k Sorting on the multi-mesh....Pages 85-92
Refinement of coloured petri nets....Pages 93-104
Stratified petri nets....Pages 105-116
Distributed acyclic orientation of asynchronous anonymous networks....Pages 117-128
Generalized rational relations and their logical definability....Pages 129-137
A note on broadcasting with linearly bounded transmission faults in constant degree networks....Pages 138-149
Logics which capture complexity classes over the reals....Pages 150-156
Criteria to disprove context-freeness of collage languages....Pages 157-167
The subword complexity of fixed points of binary uniform morphisms....Pages 169-178
Efficient parallel computing with memory faults....Pages 179-187
Bounded concurrency....Pages 188-197
Concerning the time bounds of existing shortest watchman route algorithms....Pages 198-209
Query order in the polynomial hierarchy....Pages 210-221
Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria....Pages 222-232
Pattern-matching problems for 2-dimensional images described by finite automata....Pages 233-244
The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups....Pages 245-256
Contextual grammars with distributed catenation and shuffle....Pages 257-268
A two-dimensional hierarchy for attributed tree transducers....Pages 269-280
Synchronization of 1-way connected processors....Pages 281-292
A linear-time heuristic for minimum rectangular coverings (Extended abstract)....Pages 293-304
On occurrence net semantics for petri nets with contacts....Pages 305-316
Cellular automata universality revisited....Pages 317-328
Trade-off results for connection management....Pages 329-339
On the average complexity of the membership problem for a generalized Dyck language....Pages 340-351
Towards optimal locality in mesh-indexings....Pages 352-363
On the hierarchy of nondeterministic branching k -programs....Pages 364-375
FDT is undecidable for finitely presented monoids with solvable word problems....Pages 376-387
The equivalence of pebbles and sensing heads for finite automata....Pages 388-399
From finite automata toward hybrid systems (Extended abstract)....Pages 400-410
On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP....Pages 411-422
Lower bounds in on-line geometric searching metric searching....Pages 423-428
The complexity of universal text-learners....Pages 429-440
Unique normal forms for nonlinear term rewriting systems: Root overlaps....Pages 441-451
Behavioural characterizations of partial order logics....Pages 452-462
....Pages 463-474
