MONADIC LOGIC PROGRAMS AND FUNCTIONAL COMPLEXITY

Problems related to the complexity and to the decidability of several languages weaker than Prolog are studied in this paper. In particular, monadic logic programs, that is, programs containing only monadic fun ctions and monadic predicates, are considered in detail. The functiona l complexity of a monadic logic program is the language of all words f (1)...f(k) such that the literal p(f(1)(...(f(k)(a))...)) is a logical consequence of the program. The relationship between several subclass es of monadic programs, their functional complexities and the correspo nding automata is studied. It is proved that the class of monadic prog rams corresponds exactly to the class of regular languages. As a conse quence, the ''SUCCESS'' problem is decidable for that class. It is als o proved that the success set of a specific subclass of monadic progra ms (''simple'' programs) corresponds exactly to regular languages with star-height not exceeding 1.