Fundamentals of Computation Theory: FCT ’85 Cottbus, GDR, September 9–13, 1985

Māris Alberts (auth.), Lothar Budach (eds.)3540156895, 9783540156895

This volume contains abridged versions of most of the sectional talks and some invited lectures given at the International Conference on Fundamentals of Computation Theory held at Kazan State University, Kazan, USSR, June 22-26, 1987. The conference was the sixth in the series of FCT Conferences organized every odd year, and the first one to take place in the USSR. FCT ’87 was organized by the Section of Discrete Mathematics of the Academy of Sciences in the USSR, the Moscow State University (Department of Discrete Mathematics), and the Kazan State University (Department of Theoretical Cybernetics). This volume contains selected contributions to the following fields: Mathematical Models of Computation, Synthesis and Complexity of Control Systems, Probabilistic Computations, Theory of Programming, Computer-Assisted Deduction. The volume reflects the fact that FCT ’87 was organized in the USSR: A wide range of problems typical of research in Mathematical Cybernetics in the USSR is comprehensively represented.

---

Table of contents :
Space complexity of alternating Turing machines….Pages 1-7
A unifying theorem for algebraic semantics and dynamic logics….Pages 8-17
On some “non-uniform” complexity measures….Pages 18-27
Fast parallel vertex colouring….Pages 28-35
Muller automata and bi-infinite words….Pages 36-43
On formal languages, probabilities, paging and decoding algorithms….Pages 44-52
On the restriction of some NP-complete graph problems to permutation graphs….Pages 53-62
Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic….Pages 63-69
Algorithms solving path systems….Pages 70-79
Decidability of confluence for ground term rewriting systems….Pages 80-89
Lower bounds on the complexity of 1-time only branching programs (Preliminary version)….Pages 90-99
On coordinated rewriting….Pages 100-111
Elements of a general theory of combinatorial structures….Pages 112-127
A language theoretic approach to serialization problem in concurrent systems….Pages 128-145
Logic programming and substitutions….Pages 146-158
A lower bound on the oscilation complexity of context-free languages….Pages 159-166
Depth efficient transformations of arithmetic into boolean circuits….Pages 167-174
Free cost measures of trees….Pages 175-190
Discrete extremal problems on covering….Pages 191-207
Parallel algorithms for connected components in a graph….Pages 208-217
Statistical testing of finite sequences based on algorithmic complexity….Pages 218-226
Lower bounds for boolean formulae of depth 3 and the topology of the n-Cube (Preliminary version)….Pages 227-233
Clustering to minimize the sum of volumes of convex hulls of clusters is NP-complete….Pages 234-241
Linear comparison complexity of the n-cube membership problem….Pages 242-248
String grammars with disconnecting….Pages 249-256
Array processing machines….Pages 257-268
A fast heuristic for covering polygons by rectangles….Pages 269-278
К Вопросу О Раэрещимости Теории Свободной Группы….Pages 279-284
Products of group languages….Pages 285-299
The complexity of embedding graphs into binary trees….Pages 300-309
On some topological properties of logic programs….Pages 310-319
Recent results on continuous ordered algebras….Pages 320-330
Are lower bounds on the complexity lower bounds for universal circuits?….Pages 331-340
Probabilistic algorithms in group theory….Pages 341-350
Recent results on codes….Pages 351-360
A multiparameter analysis of the boundedness problem for vector addition systems….Pages 361-370
About two-way transducers….Pages 371-379
Parallel time O(log N) recognition of unambiguous CFLs….Pages 380-389
On colour critical graphs….Pages 390-401
Generalized thue-morse sequences….Pages 402-411
Tree-partite graphs and the complexity of algorithms….Pages 412-421
A quadratic regularity test for non-deleting macro s grammars….Pages 422-430
Continuous abstract data types: Basic machinery and results….Pages 431-441
On the length of single dynamic tests for monotone boolean functions….Pages 442-449
Enumerative combinatorics and algebraic languages….Pages 450-464
On several kinds of space-bounded on-line multicounter automata….Pages 465-473
Iterated linear control and iterated one-turn pushdowns….Pages 474-484
On the boolean closure of NP….Pages 485-493
The critical complexity of all (monotone) boolean functions and monotone graph properties….Pages 494-502
Degeneration of Shimura surfaces and a problem in coding theory….Pages 503-511
Quantifiers in combinatory PDL: Completeness, definability, incompleteness….Pages 512-519
Partial ordering derivations for CCS….Pages 520-533
Intersecting two polyhedra one of which is convex….Pages 534-542