Mathematical Foundations of Computer Science 1979: Proceedings, 8th Symposium, Olomouc, Czechoslovakia, September 3–7, 1979

A sound and complete proof system for partial program correctness....Pages 1-12
The problem of reachability and verification of programs....Pages 13-25
Assertion programming....Pages 26-42
Complexity classes of formal languages....Pages 43-56
Fast probabilistic algorithms....Pages 57-69
Relative succinctness of representations of languages and separation of complexity classes....Pages 70-88
On two types of loops....Pages 89-107
Full abstraction for a simple parallel programming language....Pages 108-120
On some developments in cryptography and their applications to computer science....Pages 121-130
Searching, sorting and information theory....Pages 131-145
Lcf: A way of doing proofs with a machine....Pages 146-159
Axioms or algorithms....Pages 160-169
Power from power series....Pages 170-181
Computational complexity of string and graph ident ification....Pages 182-190
A survey of grammar and l forms-1978....Pages 191-200
A theoretical study on the time analysis of programs....Pages 201-207
Completeness problems in verification of programs and program schemes....Pages 208-218
Relationships between AFDL\'s and cylinders....Pages 219-227
Computable data types....Pages 228-236
Program equivalence and provability....Pages 237-245
Interactive L systems with almost interactionless behaviour....Pages 246-257
On the simplification of constructions in degrees of unsolvability via computational complexity....Pages 258-265
An algebraic extension of the Chomsky — hierarchy....Pages 266-276
Bounds on computational complexity and approximability of initial segments of recursive sets....Pages 277-283
On the weighted path length of binary search trees for unknown access probabilities....Pages 284-291
Computational complexity of approximation algorithms for combinatorial problems....Pages 292-300
A reduct-and-closure algorithm for graphs....Pages 301-307
Small universal Minsky machines....Pages 308-316
Parallel and two-way recognizers of directed acyclic graphs....Pages 317-325
Fully effective solutions of recursive domain equations....Pages 326-336
A note on computational complexity of a statistical deducibility testing procedure....Pages 337-345
Context free normal systems....Pages 346-353
New proofs for jump dpda\'s....Pages 354-362
Synchronization and maximality for very pure subsemigroups of a free semigroup....Pages 363-371
On the sets of minimal indices of partial recursive functions....Pages 372-374
Some remarks on Boolean sums....Pages 375-380
On the propositional algorithmic logic....Pages 381-389
Ch(k) grammars: A characterization of LL(k) languages....Pages 390-397
A uniform approach to balanced binary and multiway trees....Pages 398-407
On the generative capacity of some classes of grammars with regulated rewriting....Pages 408-414
Validity test for Floyd\'s operator-precedence parsing algorithms....Pages 415-424
On the languages of bounded Petri nets....Pages 425-433
Dyck language D 2 is not absolutely parallel....Pages 434-442
Fixed points in the power-set algebra of infinite trees....Pages 443-452
On relaxation rules in algorithmic logic....Pages 453-462
L-Fuzzy functorial automata....Pages 463-473
Schematics of structural parallel programming and its applications....Pages 474-481
On axiomatization of deterministic propositional dynamic logic....Pages 482-491
Bounded recursion and complexity classes....Pages 492-498
Characterization of rational and algebraic power series....Pages 499-507
A crossing measure for 2-tape Turing machines....Pages 508-516
The complexity of lexicographic sorting and searching....Pages 517-522
An algebraic approach to concurrence....Pages 523-532
On multitape automata....Pages 533-541
A turing machine oracle hierarchy....Pages 542-551
A survey of some syntactic results in the λ-calculus....Pages 552-566
On rational expressions representing infinite rational trees : Application to the structure of flow charts....Pages 567-580