Mathematical Foundations of Computer Science 1977: 6th Symposium, Tatranska Lomnica September 5-9, 1977. ProceedingsJ. Gruska |
Contents
ON THE STRUCTURE AND PROPERTIES OF NPCOMPLETE PROBLEMS AND THEIR ASSOCIATED OPTIMIZATION PROBLEMS | 1 |
A COMPARATIVE REVIEW OF SOME PROGRAM VERIFICATION METHODS | 16 |
CLASSIFICATION OF THE CONTEXTFREE LANGUAGES | 32 |
FINITE AUTOMATON FROM A FLOWCHART SCHEME POINT OF VIEW | 42 |
A NEW TYPE OF MODELS OF COMPUTATION | 50 |
CORRECTNESS OP MIXED COMPUTATION IN ALGOLLIKE PROGRAMS | 57 |
ALGEBRA AND LOGIC IN THEORETICAL COMPUTER SCIENCE | 76 |
A SURVEY OF RECENT PROBLEMS AND RESULTS IN ANALYTIC COMPUTATIONAL COMPLEXITY | 89 |
A PROBABILISTIC RESTRICTION OF BRANCHING PLANS | 338 |
REDUCING OPERATORS FOR NORMED GENERAL FORMAL SYSTEMS | 346 |
INVARIANT PROPERTIES OF INFORMATIONAL BULKS | 355 |
TWO DECIDABILITY RESULTS FOR DETERMINISTIC PUSHDOWN AUTOMATA | 361 |
OH THE LOGIC OF INCOMPLETE INFORMATION | 370 |
MEASURES OF AMBIGUITY IN THE ANALYSIS OF COMPLEX SYSTEMS | 378 |
TWOLEVEL METACONTROLLED SUBSTITUTION GRAMMARS | 386 |
A CALCULUS TO BUILD UP CORRECT PROGRAMS | 394 |
TREESTRUCTURES FOR SET MANIPULATION PROBLEMS | 104 |
APPLIED ALGORITHMIC LOGIC | 118 |
IMPROVED LOWER BOUNDS ON THE NUMBER OF MULTIPLICATIONSDIVISIONS WHICH ARE NECESSARY TO EVALUATE POLYNO... | 131 |
FREQUENCY ALGORITHMS AND COMPUTATIONS | 144 |
GRAPHTHEORETIC ARGUMENTS IN LOWLEVEL COMPLEXITY | 158 |
PROPERTIES OF COMPLEXITY CLASSES A SHORT SURVEY | 173 |
A UNIFORM APPROACH TO INDUCTIVE POSETS AND INDUCTIVE CLOSURE | 188 |
GENERALIZED PROBABILISTIC GRAMMARS | 209 |
CLASSES OF STRUCTURALLY ISOMORPHIC NPOPTIMIZATION PROBLEMS | 218 |
PUSHDOWNAUTOMATA AND FAMILIES OF LANGUAGES GENERATING CYLINDERS | 227 |
SEMANTICS OF INFINITE PROCESSES USING GENERALIZED TREES | 236 |
CHARACTERIZATION OF RECOGNIZABLE FAMILIES BY MEANS OF REGULAR LANGUAGES | 243 |
AN ALGEBRAIC APPROACH TO PROBLEM SOLUTION AND PROBLEM SEMANTICS | 249 |
COMPLEXITY AND MINIMALITY OF CONTEXTFREE GRAMMARS AND LANGUAGES | 259 |
COMPARISON OF THE ACTIVE VISITING AND THE CROSSING COMPLEXITIES | 268 |
ARITHMETICAL COMPLEXITY OF SOME PROBLEMS IN COMPUTER SCIENCE | 278 |
FORMAL TRANSFORMATIONS AND THE DEVELOPMENT OF PROGRAMS | 284 |
OPTIMAL RASP PROGRAMS FOR ARBITRARILY COMPLEX 01 VALUED FUNCTIONS | 293 |
THE EXPRESSIVE POWER OF INTENSIONAL LOGIC IN THE SEMANTICS OF PROGRAMMING LANGUAGES | 299 |
ON THE COMPLEXITY OF EQUIVALENT TRANSFORMATIONS IN PROGRAMMING LANGUAGES | 308 |
SCHEMATOLOGY IS A MULTILANGUAGE OPTIMIZER | 311 |
DECIDABILITY UNDECIDABILITY OF EQUIVALENCE OF MINSKY MACHINES WITH COMPONENTS CONSISTING OF AT MOST SEVEN... | 320 |
A TOPDOWN NO BACKTRACK PARSING OF GENERAL CONTEXTFREE LANGUAGES | 329 |
ANOTHER APPROACH FOR PROVING PROGRAM CORRECTNESS | 406 |
COVER RESULTS AND NORMAL FORMS | 416 |
ON A DETERMINISTIC SUBCLASS OF CONTEXTFREE LANGUAGES | 426 |
EXPONENTIAL OPTIMIZATION FOE THE LLPk PARSING METHOD | 431 |
THE MEDIAL AXIS OF A SIMPLE POLYGON | 439 |
SEMANTICS AND PROOF RULES FOR COROUTINE HIERARCHIES IN BLOCKSTRUCTURED PROGRAMMING LANGUAGES | 447 |
ACCEPTORS FOR ITERATION LANGUAGES | 454 |
HOW GOOD IS THE ADVERSARY LOWER BOUND? | 459 |
TOTAL CORRECTNESS FOR PROCEDURES | 469 |
A MODEL FOR RETRIEVAL SYSTEMS AND SOME MATHEMATICAL PROBLEMS BEHIND | 478 |
TIME AND TAPE BOUNDED AUXILIARY PUSHDOWN AUTOMATA | 487 |
A FAST NONCOMMUTATIVE ALGORITHM FOR MATRIX MULTIPLICATION | 498 |
FIXEDPOINTS AND ALGEBRAS WITH INFINITELY LONG EXPRESSIONS I | 507 |
ON LANGUAGES ACCEPTED BY MACHINES IN THE CATEGORY OF SETS | 517 |
REAL TIME COMPUTATIONS WITH RESTRICTIONS ON TAPE ALPHABET | 524 |
THE BODNARCHUK METRIC SPACE OF LANGUAGES AND THE TOPOLOGY OF THE LEARNING SPACE | 529 |
COMPLEXITY HIERARCHIES OF ORACLES | 535 |
DETERMINING PROCESSES BY VIOLATIONS | 541 |
THE INFLUENCE OF THE MACHINE MODEL ON THE TIME COMPLEXITY OF CONTEXTFREE LANGUAGE RECOGNITION | 552 |
A GENERALIZED COMPUTABILITY THESIS | 560 |
IDENTIFICATION OF FORMAL LANGUAGES | 561 |
CORRECTNESS OF RECURSIVE FLOW DIAGRAM PROGRAMS | 570 |
Common terms and phrases
algebra ALGOL 68 algorithm approximation algorithms arbitrary assignment automata automaton binary called computational complexity Computer Science consider construction context-free grammars context-free languages Core[P Corollary coroutine corresponding decision problems defined definition denote deterministic elements equivalent example exists family of languages finite formal formula function functor given grammar G graph HB-trees homomorphism inductive infinite input integer isomorphic iteration labelled Lemma linear lower bounds LR(k mapping Mathematical matrix medial axis morphisms NGFS nodes nondeterministic notation notion NP-complete obtained operations optimization problem output pair paper parsable parse partial partial functions path polynomial poset predicate probabilistic Proc programming languages proof properties prove pushdown pushdown automata queue recursive reduced relation respect semantics semilinear sequence structure symbols tape Theorem tion transformation tree Turing machine upper bound variables vector vertex Z-inductive Z-set