Ebook: Mathematical Foundations of Computer Science 1986: Proceedings of the 12th Symposium Bratislava, Czechoslovakia August 25–29, 1986

---

Content:
Front Matter....Pages -
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

---

Content:
Front Matter....Pages -
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
....