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...

Full description

Corporate Author: SpringerLink (Online service)
Other Authors: Rovan, Branislav (Editor)
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
LEADER 05125nmm a2200433 u 4500
001 EB000657700
003 EBX01000000000000000510782
005 00000000000000.0
007 cr|||||||||||||||||||||
008 140122 ||| eng
020 |a 9783540471851 
100 1 |a Rovan, Branislav  |e [editor] 
245 0 0 |a Mathematical Foundations of Computer Science 1990  |h Elektronische Ressource  |b Banska Bystrica, Czechoslovakia, August 27-31, 1990 Proceedings  |c edited by Branislav Rovan 
250 |a 1st ed. 1990 
260 |a Berlin, Heidelberg  |b Springer Berlin Heidelberg  |c 1990, 1990 
300 |a X, 546 p  |b online resource 
505 0 |a 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 --  
505 0 |a 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 --  
505 0 |a 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 
505 0 |a 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 of higher order processes -- The membership problem for context-free chain code picture languages --  
653 |a Mathematical Logic and Formal Languages 
653 |a Computer science—Mathematics 
653 |a Theory of Computation 
653 |a Mathematical logic 
653 |a Mathematics of Computing 
653 |a Algorithms 
653 |a Computers 
653 |a Logics and Meanings of Programs 
653 |a Computation by Abstract Devices 
653 |a Algorithm Analysis and Problem Complexity 
653 |a Computer logic 
710 2 |a SpringerLink (Online service) 
041 0 7 |a eng  |2 ISO 639-2 
989 |b SBA  |a Springer Book Archives -2004 
490 0 |a Lecture Notes in Computer Science 
856 |u https://doi.org/10.1007/BFb0029591?nosfx=y  |x Verlag  |3 Volltext 
082 0 |a 004.0151 
520 |a 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 symposium is the 15th in a series of international meetings which have taken place in Czechoslovakia and Poland. The aim of these symposia is to bring together specialists in theoretical fields of computer science from various countries and to stimulate mathematical research in theoretical computer science. These proceedings consist of 10 invited papers and 52 communications selected by the international Program Committee. The papers present the latest results in key areas of computer science by authors from Europe, USA, Japan and China