Combinatorial systems defined over one- and two-letter alphabets.
Combined complexity classes for finite functions
Comparing sets of the Baire space by means of general recursive operators
Comparing the succinctness of monadic query languages over finite trees
We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog. Succinctness...
Comparing the succinctness of monadic query languages over finite trees
We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog. Succinctness...
Comparisons between some generalizations of recursion theory
Complete index sets of recursively enumerable families
Complexité de l'arboricité linéaire d'un graphe
Complexity of some natural problems in automatic structures.
Complexity of some natural problems on the class of computable -algebras.
Complexity of the axioms of the alternative set theory
If T is a complete theory stronger than ZF such that axiom of extensionality for classes + T + is consistent for 1 (each alone), where are normal formulae then we show AST + + scheme of choice is consistent. As a consequence we get: there is no proper -formula in AST + scheme of choice. Moreover the complexity of the axioms of AST is studied, e.gẇe show axiom of extensionality is -formula, but not -formula and furthermore prolongation axiom, axioms of choice and cardinalities are -formulae,...
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.
Complexity results for prefix grammars
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
Complexity results for prefix grammars
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
Computability in special models.
Computable categoricity versus relative computable categoricity
We study the notion of computable categoricity of computable structures, comparing it especially to the notion of relative computable categoricity and its relativizations. We show that every 1 decidable computably categorical structure is relatively Δ⁰₂ categorical. We study the complexity of various index sets associated with computable categoricity and relative computable categoricity. We also introduce and study a variation of relative computable categoricity, comparing it to both computable...
Computable families of superatomic Boolean algebras.
Computable solutions of equations over endomorphisms of negative numberings.
Computably rigid models with enumerable submodels.