Ebook: Mathematical Foundations of Computer Science 1977: Proceedings, 6th Symposium, Tatranská Lomnica September 5–9, 1977

---

Content:
Front Matter....Pages -
On the structure and properties of NP-complete problems and their associated optimization problems....Pages 1-16
A comparative review of some program verification methods....Pages 17-33
Classification of the context-free languages....Pages 34-43
Finite automaton from a flowchart scheme point of view....Pages 44-51
A new type of models of computation....Pages 52-58
Correctness of mixed computation in ALGOL-like programs....Pages 59-77
Algebra and logic in theoretical computer science....Pages 78-92
A survey of recent problems and results in analytic computational complexity....Pages 93-107
Tree-structures for set manipulation problems....Pages 108-121
Applied algorithmic logic....Pages 122-134
Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials....Pages 135-147
Frequency algorithms and computations....Pages 148-161
Graph-theoretic arguments in low-level complexity....Pages 162-176
Properties of complexity classes a short survey....Pages 177-191
A uniform approach to inductive posets and inductive closure....Pages 192-212
Generalized probabilistic grammars....Pages 213-221
Classes of structurally isomorphic np-optimization problems....Pages 222-230
Pushdown-automata and families of languages generating cylinders....Pages 231-239
Semantics of infinite processes using generalized trees....Pages 240-246
Characterization of recognizable families by means of regular languages....Pages 247-252
An algebraic approach to problem solution and problem semantics....Pages 253-262
Complexity and minimality of context-free grammars and languages....Pages 263-271
Comparison of the active visiting and the crossing complexities....Pages 272-281
Arithmetical complexity of some problems in computer science....Pages 282-287
Formal transformations and the development of programs....Pages 288-296
Optimal rasp programs for arbitrarily complex 0–1 valued functions....Pages 297-302
The expressive power of intensional logic in the semantics of programming languages....Pages 303-311
On the complexity of equivalent transformations in programming languages....Pages 312-314
Schematology in a MJ I/T I-language OPT imizer....Pages 315-323
Decidability (undecidability) of equivalence of Minsky machines with components consisting of at most seven (eight) instructions....Pages 324-332
A top-down no backtrack parsing of general context-free languages....Pages 333-341
A probabilistic restriction of branching plans....Pages 342-349
Reducing operators for normed general formal systems....Pages 350-358
Invariant properties of informational bulks....Pages 359-364
Two decidability results for deterministic pushdown automata....Pages 365-373
On the logic of incomplete information....Pages 374-381
Measures of ambiguity in the analysis of complex systems....Pages 382-389
Two-level meta-controlled substitution grammars....Pages 390-397
A calculus to build up correct programs....Pages 398-409
Another approach for proving program correctness....Pages 410-419
Cover results and normal forms....Pages 420-429
On a deterministic subclass of context-free languages....Pages 430-434
Exponential optimization for the LLP(k) parsing method....Pages 435-442
The medial axis of a simple polygon....Pages 443-450
Semantics and proof rules for coroutine hierarchies in block-structured programming languages....Pages 451-459
Acceptors for iteration languages....Pages 460-464
How good is the adversary lower bound ?....Pages 465-474
Total correctness for procedures....Pages 475-483
A model for retrieval systems and some mathematical problems behind....Pages 484-492
Time and tape bounded auxiliary pushdown automata....Pages 493-503
A fast non-commutative algorithm for matrix multiplication....Pages 504-512
Fixed-points and algebras with infinitely long expressions, I....Pages 513-522
On languages, accepted by machines in the category of sets....Pages 523-531
Real time computations with restrictions on tape alphabet....Pages 532-536
The bodnarchuk metric space of languages and the topology of the learning space....Pages 537-542
Complexity hierarchies of oracles....Pages 543-548
Determining processes by violations....Pages 549-559
The influence of the machine model on the time complexity of context-free language recognition....Pages 560-569
A generalized computability thesis....Pages 570-570
Identification of formal languages....Pages 571-579
Correctness of recursive flow diagram programs....Pages 580-595

---

Content:
Front Matter....Pages -
On the structure and properties of NP-complete problems and their associated optimization problems....Pages 1-16
A comparative review of some program verification methods....Pages 17-33
Classification of the context-free languages....Pages 34-43
Finite automaton from a flowchart scheme point of view....Pages 44-51
A new type of models of computation....Pages 52-58
Correctness of mixed computation in ALGOL-like programs....Pages 59-77
Algebra and logic in theoretical computer science....Pages 78-92
A survey of recent problems and results in analytic computational complexity....Pages 93-107
Tree-structures for set manipulation problems....Pages 108-121
Applied algorithmic logic....Pages 122-134
Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials....Pages 135-147
Frequency algorithms and computations....Pages 148-161
Graph-theoretic arguments in low-level complexity....Pages 162-176
Properties of complexity classes a short survey....Pages 177-191
A uniform approach to inductive posets and inductive closure....Pages 192-212
Generalized probabilistic grammars....Pages 213-221
Classes of structurally isomorphic np-optimization problems....Pages 222-230
Pushdown-automata and families of languages generating cylinders....Pages 231-239
Semantics of infinite processes using generalized trees....Pages 240-246
Characterization of recognizable families by means of regular languages....Pages 247-252
An algebraic approach to problem solution and problem semantics....Pages 253-262
Complexity and minimality of context-free grammars and languages....Pages 263-271
Comparison of the active visiting and the crossing complexities....Pages 272-281
Arithmetical complexity of some problems in computer science....Pages 282-287
Formal transformations and the development of programs....Pages 288-296
Optimal rasp programs for arbitrarily complex 0–1 valued functions....Pages 297-302
The expressive power of intensional logic in the semantics of programming languages....Pages 303-311
On the complexity of equivalent transformations in programming languages....Pages 312-314
Schematology in a MJ I/T I-language OPT imizer....Pages 315-323
Decidability (undecidability) of equivalence of Minsky machines with components consisting of at most seven (eight) instructions....Pages 324-332
A top-down no backtrack parsing of general context-free languages....Pages 333-341
A probabilistic restriction of branching plans....Pages 342-349
Reducing operators for normed general formal systems....Pages 350-358
Invariant properties of informational bulks....Pages 359-364
Two decidability results for deterministic pushdown automata....Pages 365-373
On the logic of incomplete information....Pages 374-381
Measures of ambiguity in the analysis of complex systems....Pages 382-389
Two-level meta-controlled substitution grammars....Pages 390-397
A calculus to build up correct programs....Pages 398-409
Another approach for proving program correctness....Pages 410-419
Cover results and normal forms....Pages 420-429
On a deterministic subclass of context-free languages....Pages 430-434
Exponential optimization for the LLP(k) parsing method....Pages 435-442
The medial axis of a simple polygon....Pages 443-450
Semantics and proof rules for coroutine hierarchies in block-structured programming languages....Pages 451-459
Acceptors for iteration languages....Pages 460-464
How good is the adversary lower bound ?....Pages 465-474
Total correctness for procedures....Pages 475-483
A model for retrieval systems and some mathematical problems behind....Pages 484-492
Time and tape bounded auxiliary pushdown automata....Pages 493-503
A fast non-commutative algorithm for matrix multiplication....Pages 504-512
Fixed-points and algebras with infinitely long expressions, I....Pages 513-522
On languages, accepted by machines in the category of sets....Pages 523-531
Real time computations with restrictions on tape alphabet....Pages 532-536
The bodnarchuk metric space of languages and the topology of the learning space....Pages 537-542
Complexity hierarchies of oracles....Pages 543-548
Determining processes by violations....Pages 549-559
The influence of the machine model on the time complexity of context-free language recognition....Pages 560-569
A generalized computability thesis....Pages 570-570
Identification of formal languages....Pages 571-579
Correctness of recursive flow diagram programs....Pages 580-595
....