Mathematical Foundations of Computer Science 1986

Inhaltsverzeichnis

• Why sometimes probabilistic algorithms can be more effective.
• Recent results in the theory of rational sets.
• Partial interpretations of higher order algebraic types.
• Kins of context-free languages.
• Algebraic theory of module specifications with constraints.
• A semantical model for integration and modularization of rules.
• Parallel arithmetic computations: A survey.
• An approach to proof checker.
• The promise of electronic prototyping.
• Systolic arrays: Characterizations and complexity.
• Geometric location problems and their complexity.
• Developing implicit data structures.
• Higher-order arrays and stacks in programming. An application of complexity theory to logics of programs.
• Deterministic simulation of idealized parallel computers on more realistic ones.
• Relational specifications and observational semantics.
• Efficient testing of optimal time adders.
• Properties of complexity measures for PRAMs and WARMs.
• Iterative systems of equations.
• Polynomial complexity of the Newton-Puiseux algorithm.
• Unique decipherability for partially commutative alphabet (extended abstract).
• The equivalence of finite valued transducers (on HDTOL languages) is decidable.
• A fast parallel algorithm for six-colouring of planar graphs.
• Quicksort without a stack.
• Towards an efficient merging.
• Homomorphic realization of automata with compositions.
• Refined bounds on the complexity of sorting and selection in d - dimensional space.
• On the inherent combinatorial complexity of geometric problems in d - dimensional space.
• The evolution of two stacks in bounded space and random walks in a triangle.
• P-genericity and strong p-genericity.
• Fibonacci numeration systems and rational functions.
• Safe implementation equivalence for asynchronous nondeterministic processes.
• Grammars with context dependency restricted to synchronization.
• Some improved parallelisms for graphs.
• A complete inference system for an algebra of regular acceptance models.
• Nondeterministic Turing machines with modified acceptance.
• Remark on the power of compass.
• Regular chain code picture languages of nonlinear descriptional complexity.
• An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines.
• A new approach to defining the communication complexity for VLSI.
• Lower bounds on the complexity of local circuits.
• Optimal sorting of seven element sets.
• Undecidable problems concerning generalized pascal triangles of commutative algebras.
• Regular augmentation of automata and transducers.
• On some types of pseudo-random sequences.
• The space complexity of the accessibility problem for undirected graphs of log n bounded genus.
• An alternative, priority-free, solution to Post's problem.
• Near optimal algorithms for finding minimum Steiner trees on random graphs.
• Matrix systems and principal cones of algebraic power series.
• Two characterizations of the logarithmic alternation hierarchy.
• p-Projection reducibility and the complexity classes ? (nonuniform) and N? (nonuniform).
• A proof system to derive eventuality properties under justice hypothesis.
• Al-Khowarizmi : A formal system for higher-order logic programming.
• One-sided Dyck reduction over two letter alphabet and deterministic context-free languages.
• Model and complexity of termination for distributed computations.
• Complexity of generalized graph coloring.
• The parallel complexity of deadlock detection.
• The centers of context-sensitive languages.
• A greedy algorithm for constructing shortest common superstrings.
• The OI-hierarchy is closed under control.
• On the degree of ambiguity offinite automata.
• Learning in knowledge based systems, a possibilistic approach.
• Proofs that Release Minimum Knowledge.