Mathematical Foundations of Computer Science 1976

Exercises in denotational semantics.- W-automata and their languages.- On semantic issues in the relational model of data.- The effective arrangement of logical systems.- Recursivity, sequence recursivity, stack recursivity and semantics of programs.- Descriptional complexity (of languages) a short survey.- On the branching structure of languages.- Algorithms and real numbers.- On mappings of machines.- Recent results on L systems.- Decision problems for multi-tape automata.- Recursive program schemes and computable functionals.- Some fundamentals of order-algebraic semantics.- On attribute grammars.- Formal definition of semantics of generalized control regimes.- Minimal while programs.- On specific features of recognizable families of languages.- On the termination of simple computer programs.- Reduction of Petri-nets.- On behaviour of R-fuzzy automata.- Cannonizing reducibility method in the theory of program schemata.- Strongly connected G-S-M mappings preserving conjugation.- Analysis of the non-context-free component of formal languages.- Programs, computations and temporal features.- A note on the automatic generation of inductive assertions.- On the relationship between a procedure and its data.- On the relativization of deterministic and nondeterministic complexity classes.- The metric properties on the semigroups and the languages.- A lower bound of 1/2n2 on linear search programs for the knapsack problem.- The direct product of automata and quasi-automata.- An axiomatic approach to information structures.- Parallelism of manipulations in multidimensional information structures.- On strict interpretations of grammar forms.- A hierarchy of context-sensitive languages.- On consecutive storage of records.- A remark on equivalence of Mazurkiewicz's finite — control algorithms over nets.- Microprogram — Oriented model of the controlled structure.- Relations between programs with different storage requirements.- An algebraic approach to data types, program verification, and program synthesis.- About three equational classes of languages built up by shuffle operations.- A machine independent description of complexity classes, definable by nondeterministic as well as deterministic turing machines with primitiv recursive tape or time bounds.- Schemes with recursion on higher types.- Constructing iterative version of a system of recursive procedures.- A method using a set-theoretical formalism to describe the semantics of programming languages.- The cubic search method.- Vectors of coroutines.- One — one degrees of Turing machines decision problems.- Heuristic representation of state-space by finite automaton.- Semigroup characterizations of some language varieties.- On memory requirements of Strassen's algorithms.- Determinism in concurrent systems.- Generating control mechanisms by restrictions.- On diagnosis of algorithmical processes.- On some properties of cyclic automata and their extensions.- Compiler generation using denotational semantics.- On divergence problem for program schemas.- On the parsing of LL-regular grammars.- The characteristic polynomial of a finite automaton.- Error detection using regular languages.- On a relationship between programs of address machines and Mazurkiewicz algorithms.- DIJKSTRA's predicate transformer, non-determinism, recursion, and termination.- Context-free programmed grammars and ETOL systems.- Context-free algebra: A mathematical device for compiler specification.- On the lower bound for minimum comparison selection.- Computational processes generated by programs with /recursive/ procedures and block structures.- An algebraic framework for the study of the syntactic monoids application to the group languages.- Degrees of parallelism in computations.- On adaptability of a system of programs.- A mathematical model of parallel information processing.- Powerdomains.- On the domain of iteration in iterative algebraic theories.- The influence of the data presentation on the computational power of machines.- On sequential modelling of non-sequential processes.- Equivalence and optimization of recursive program schemata.- Observability concepts in abstract data type specification.- The calculus of facts.- Multiplicity functions on ?-automata.- A complete axiomatic characterization of algorithmic properties of block-structured programs with procedures.