José Luis Balcázar (auth.), M. P. Chytil, V. Koubek (eds.)3540133720, 9783540133728
Table of contents :
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
Reviews
There are no reviews yet.