Mathematical Foundations of Computer Science 1990 Banska Bystrica, Czechoslovakia, August 27-31, 1990 Proceedings
This volume contains papers selected for presentation at the 15th Symposium on Mathematical Foundations of Computer Science, MFCS '90, held at Banská Bystrica, Czechoslovakia, August 27-31, 1990. Previous MFCS proceedings have also been published in the Lecture Notes in Computer Science. This s...
| Other Authors: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
1990, 1990
|
| Edition: | 1st ed. 1990 |
| Series: | Lecture Notes in Computer Science
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- A logical operational semantics of full Prolog
- Syntactic theories
- On kleene algebras and closed semirings
- Interactive computations of optimal solutions
- Restricted branching programs and their computational power
- Dynamic hashing strategies
- One-way functions in complexity theory
- Type inference problems: A survey
- Counting the number of solutions
- Implementation of parallel graph reduction by explicit annotation and program transformation
- Interrogative complexity of ?-languages’ recognition
- On the power of uniform families of constant depth threshold circuits
- Separating sets of hyperrectangles
- On preemptive scheduling of periodic, real-time tasks on one processor
- Retractions in comparing prolog semantics (extended abstract)
- Using inductive counting to simulate nondeterministic computation
- Some properties of zerotesting bounded one-way multicounter machines
- On fast algorithms for two servers
- Decomposition of semi commutations
- Optimal algorithms for dissemination of information in some interconnection networks
- A hierarchy of compositional models of I/O-automata (Extended Abstract)
- Minimal nontrivial space complexity of probabilistic one- way turing machines
- On the complexity of genuinely polynomial computation
- Pumping lemmrs for tree languages generated by rewrite systems
- Vector language: Simple description of hard instances
- Separating ?L from L, NL, co-NL and AL (=P) for Oblivious turing machines of linear access time
- The use of graphs of elliptical influence in visual hierarchical clustering
- Characterizing unambiguous augmented pushdown automata by circuits
- Rational ?-transductions
- Splitsort—an adaptive sorting algorithm
- Equational calculi for many-sorted algebras with empty carrier sets
- Semi-commutation and deterministic petri nets
- Internal labellings in lambda-calculus
- A sup-preserving completion of ordered partial algebras
- Parallel construction of minimal suffix and factor automata
- Affine automata: A technique to generate complex images
- The complexity of symmetric functions in parity normal forms
- Event structures, causal trees, and refinements
- Query languages which express all PTIME queries for trees and unicyclic graphs
- Comparisons among classes of Y-tree systolic automata
- On checking versus evaluation of multiple queries
- Generalized kolmogorov complexity in relativized separations
- A first-order logic for partial recursive functions
- Speed-up theorem without tape compression
- On possibilities of one-way synchronized and alternating automata
- Unrestricted resolution versus N-resolution
- Quality criteria for partial order semantics of place/transition-nets
- Tree-stack automata
- Specification & verification ofhigher order processes
- The membership problem for context-free chain code picture languages
- ATIME(n) is closed under Counting
- Investigation of finitary calculi for the temporal logics by means of infinitary calculi
- Typed horn logic (extended abstract)
- Results on the glory of the past
- A stronger version of parikh theorem
- The parallel complexity of some constructions in combinatorial group theory (abstract)
- Gentzen type axiomatization for PAL
- Distance automata having large finite distance or finite ambiguity
- Bottom-up-heap sort, a new variant of heap sort beating on average quick sort (if n is not very small)
- Symmetric functions in AC 0 can be computed in constant depth with very small size
- The k-section of treewidth restricted graphs
- Computing large polynomial powers very fast in parallel