Mathematical foundations of computer science 1990 : Banská 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...
Gespeichert in:
| Körperschaft: | |
|---|---|
| Weitere Verfasser: | |
| Format: | Livre numérique |
| Sprache: | Anglais |
| Veröffentlicht: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Schriftenreihe: | Lecture notes in computer science
452 |
| Schlagworte: | |
| Online Zugang: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Anmerkung: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • Mathematical foundations of computer science, 1990, proceedings [of the 15th Symposium], Banská Bystrica, Czechoslovakia, August 27-31, 1990, B. Rovan, ed, Berlin, Springer-Verlag, 1990, 1 vol. (VIII, 544 p.), Lecture notes in computer science, 3-540-52953-5 • Mathematical Foundations of Computer Science 1990, Texte imprimé, 9783662184639 |
Inhaltsangabe:
- 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
- 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
- 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
- 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.