Mathematical Foundations of Computer Science 1984: Proceedings, 11th Symposium Praha, Czechoslovakia September 3–7, 1984

Separating, strongly separating, and collapsing relativized complexity classes....Pages 1-16
Complexity of quantifier elimination in the theory of algebraically closed fields....Pages 17-31
Systolic automata — power, characterizations, nonhomogeneity....Pages 32-49
A note on unique decipherability....Pages 50-63
Outline of an algebraic language theory....Pages 64-79
Thue systems and the Church-Rosser property....Pages 80-95
Limits, higher type computability and type-free languages....Pages 96-114
Traces, histories, graphs: Instances of a process monoid....Pages 115-133
Recent results on automata and infinite words....Pages 134-148
VLSI algorithms and architectures....Pages 149-161
Decidability of monadic theories....Pages 162-175
On the Ehrenfeucht conjecture on test sets and its dual version....Pages 176-184
Sparse oracles, lowness, and highness....Pages 185-193
Computability of probabilistic parameters for some classes of formal languages....Pages 194-204
A truely morphic characterization of recursively enumerable sets....Pages 205-213
On the Herbrand Kleene universe for nondeterministic computations....Pages 214-222
An investigation of controls for concurrent systems by abstract control languages....Pages 223-231
On generalized words of Thue-Morse....Pages 232-239
Nondeterminism is essential for two-way counter machines....Pages 240-244
Weak and strong fairness in CCS....Pages 245-254
On the complexity of inductive inference....Pages 255-264
Monotone edge sequences in line arrangements and applications....Pages 265-272
Many-sorted temporal logic for multi-processes systems....Pages 273-281
Process logics : two decidability results....Pages 282-290
On searching of special classes of mazes and finite embedded graphs....Pages 291-300
The power of the future perfect in program logics....Pages 301-311
Hierarchy of reversal and zerotesting bounded multicounter machines....Pages 312-321
On the power of alternation in finite automata....Pages 322-329
The equivalence problem and correctness formulas for a simple class of programs....Pages 330-338
Lower bounds for polygon simplicity testing and other problems....Pages 339-347
A uniform independence of invariant sentences....Pages 348-354
On the equivalence of compositions of morphisms and inverse morphisms on regular languages....Pages 355-363
Some connections between presentability of complexity classes and the power of formal systems of reasoning....Pages 364-369
Finding a maximum flow in /s,t/-planar network in linear expected time....Pages 370-377
Nondeterministic logspace reductions....Pages 378-388
Factoring multivariate polynomials over algebraic number fields....Pages 389-396
Gödel numberings, principal morphisms, combinatory algebras....Pages 397-406
Representations of integers and language theory....Pages 407-415
New lower bound for polyhedral membership problem with an application to linear programming....Pages 416-424
Decidability of the equivalence problem for synchronous deterministic pushdown automata....Pages 425-432
Models and operators for nondeterministic processes....Pages 433-442
Algorithms for string editing which permit arbitrarily complex edit constraints....Pages 443-451
The structure of polynomial complexity cores....Pages 452-458
Solving visibility problems by using skeleton structures....Pages 459-470
Another look at parameterization using algebras with subsorts....Pages 471-479
A lower bound on complexity of branching programs....Pages 480-489
From dynamic algebras to test algebras....Pages 490-497
Combinatorial games with exponential space complete decision problems....Pages 498-506
Fast recognitions of pushdown automaton and context-free languages....Pages 507-515
Multiprocessor systems and their concurrency....Pages 516-525
Free constructions in algebraic institutions....Pages 526-534
Remarks on comparing expressive power of logics of programs....Pages 535-543
The complexity of problems concerning graphs with regularities....Pages 544-552
On the complexity of slice functions....Pages 553-561
An exponential lower bound for one-time-only branching programs....Pages 562-566
A topological view of some problems in complexity theory....Pages 567-572
Propositional dynamic logic with strong loop predicate....Pages 573-581