The accepting power of unary string logic programs

The set of programs written in a small subset of pure Prolog called US is s hown to accept exactly the class of regular languages. The language US cont ains only unary predicates and unary function symbols. Also, a subset of US called RUS is shown to be equivalent to US in its ability in accepting the class of regular languages. Every clause in RUS contains at most one funct ion symbol in the head and at most one literal with no function symbol in t he body. The result is very close to a theorem of Matos (TCS April 1997) bu t our proof is quite different. Though US and RUS have the same accepting p ower, their conciseness of expression is dramatically different: if we try to write an RUS program equivalent to a US program, the number of predicate s in the RUS program could be O(2(2N)) where N is the sum of the number of predicates and the number of functors in the US program. (C) 2001 Elsevier Science B.V. All rights reserved.