Farid M. Ablaev, Rūsiņš Freivalds (auth.), Jozef Gruska, Branislav Rovan, Juraj Wiedermann (eds.)3540167838, 9783540167839
Table of contents :
Why sometimes probabilistic algorithms can be more effective….Pages 1-14
Recent results in the theory of rational sets….Pages 15-28
Partial interpretations of higher order algebraic types….Pages 29-43
Kins of context-free languages….Pages 44-58
Algebraic theory of module specifications with constraints….Pages 59-77
A semantical model for integration and modularization of rules….Pages 78-92
Parallel arithmetic computations: A survey….Pages 93-112
An approach to proof checker….Pages 113-127
The promise of electronic prototyping….Pages 128-139
Systolic arrays: Characterizations and complexity….Pages 140-153
Geometric location problems and their complexity….Pages 154-167
Developing implicit data structures….Pages 168-176
Higher-order arrays and stacks in programming. An application of complexity theory to logics of programs….Pages 177-198
Deterministic simulation of idealized parallel computers on more realistic ones….Pages 199-208
Relational specifications and observational semantics….Pages 209-217
Efficient testing of optimal time adders….Pages 218-229
Properties of complexity measures for PRAMs and WARMs….Pages 230-238
Iterative systems of equations….Pages 239-246
Polynomial complexity of the Newton-Puiseux algorithm….Pages 247-255
Unique decipherability for partially commutative alphabet (extended abstract)….Pages 256-263
The equivalence of finite valued transducers (on HDTOL languages) is decidable….Pages 264-272
A fast parallel algorithm for six-colouring of planar graphs….Pages 273-282
Quicksort without a stack….Pages 283-289
Towards an efficient merging….Pages 290-298
Homomorphic realization of automata with compositions….Pages 299-307
Refined bounds on the complexity of sorting and selection in d – dimensional space….Pages 308-314
On the inherent combinatorial complexity of geometric problems in d – dimensional space….Pages 315-324
The evolution of two stacks in bounded space and random walks in a triangle….Pages 325-340
P-genericity and strong p-genericity….Pages 341-349
Fibonacci numeration systems and rational functions….Pages 350-359
Safe implementation equivalence for asynchronous nondeterministic processes….Pages 360-369
Grammars with context dependency restricted to synchronization….Pages 370-378
Some improved parallelisms for graphs….Pages 379-385
A complete inference system for an algebra of regular acceptance models….Pages 386-395
Nondeterministic Turing machines with modified acceptance….Pages 396-404
Remark on the power of compass….Pages 405-413
Regular chain code picture languages of nonlinear descriptional complexity….Pages 414-421
An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines….Pages 422-430
A new approach to defining the communication complexity for VLSI….Pages 431-439
Lower bounds on the complexity of local circuits….Pages 440-448
Optimal sorting of seven element sets….Pages 449-457
Undecidable problems concerning generalized pascal triangles of commutative algebras….Pages 458-466
Regular augmentation of automata and transducers….Pages 467-475
On some types of pseudo-random sequences….Pages 476-483
The space complexity of the accessibility problem for undirected graphs of log n bounded genus….Pages 484-492
An alternative, priority-free, solution to Post’s problem….Pages 493-500
Near optimal algorithms for finding minimum Steiner trees on random graphs….Pages 501-511
Matrix systems and principal cones of algebraic power series….Pages 512-517
Two characterizations of the logarithmic alternation hierarchy….Pages 518-526
p-Projection reducibility and the complexity classes ℒ (nonuniform) and N ℒ (nonuniform)….Pages 527-535
A proof system to derive eventuality properties under justice hypothesis….Pages 536-544
Al-Khowarizmi : A formal system for higher-order logic programming….Pages 545-553
One-sided Dyck reduction over two letter alphabet and deterministic context-free languages….Pages 554-563
Model and complexity of termination for distributed computations….Pages 564-572
Complexity of generalized graph coloring….Pages 573-581
The parallel complexity of deadlock detection….Pages 582-593
The centers of context-sensitive languages….Pages 594-601
A greedy algorithm for constructing shortest common superstrings….Pages 602-610
The OI-hierarchy is closed under control….Pages 611-619
On the degree of ambiguity of finite automata….Pages 620-629
Learning in knowledge based systems, a possibilistic approach….Pages 630-638
Proofs that Release Minimum Knowledge….Pages 639-650
Reviews
There are no reviews yet.