A few results on the complexity of classes of identifiable recursive function sets
A lower bound for the complexity of Craig's interpolants in sentinential logic.
A new decidable Horn fragment of predicate calculus.
A note on separating the relativized polynomial time hierarchy by immune sets
A note on the computational complexity of hierarchical overlapping clustering
In this paper the computational complexity of the problem of the approximation of a given dissimilarity measure on a finite set by a -ultrametric on and by a Robinson dissimilarity measure on is investigared. It is shown that the underlying decision problems are NP-complete.
A survey of hereditary properties of graphs
In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.
A survey on real structural complexity theory.
A Turing machine oracle hierarchy. I.
A Turing machine oracle hierarchy. II.
A Turing machine space hierarchy
Algebraic caractérisations of NTIME and NTIME
Algorithmische Probleme bei Einrelatorgruppen und ihre Komplexität.
Asymptotical behaviour of some non-uniform measures
Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
Combined complexity classes for finite functions
Complexité de l'arboricité linéaire d'un graphe
Complexity of some natural problems in automatic structures.
Complexity of the decidability of one class of formulas in quantifier-free set theory with a set-union operator.
Complexity of the decidability of the unquantified set theory with a rank operator.
Computational complexity in algebraic systems.