We study definability of languages in arithmetic and the free monoid
by bounded versions of fixed-point and transitive-closure logics. In
particular we give logical characterisations of complexity classes C
by showing that a language belongs to C if and only if it is definable
in either arithmetic or the free monoid by a formula of a certain
logic. We investigate in which cases the bounds of fixed-point
operators may be omitted. Finally, a general translation of results
from descriptive complexity to the approach described in this paper
is presented.
