



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 2731, 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, realtime tasks on one processor  Retractions in comparing prolog semantics (extended abstract)  Using inductive counting to simulate nondeterministic computation  Some properties of zerotesting bounded oneway 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, coNL 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 manysorted algebras with empty carrier sets  Semicommutation and deterministic petri nets  Internal labellings in lambdacalculus  A suppreserving 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  Bottomupheap 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 ksection 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 Ytree systolic automata  On checking versus evaluation of multiple queries  Generalized kolmogorov complexity in relativized separations  A firstorder logic for partial recursive functions  Speedup theorem without tape compression  On possibilities of oneway synchronized and alternating automata  Unrestricted resolution versus Nresolution  Quality criteria for partial order semantics of place/transitionnets  Treestack automata  Specification & verification of higher order processes  The membership problem for contextfree 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 6392

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 2731, 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
