Generalized implicit definitions on finite structures

Zoe Lacroix

(Universite de Paris-Sud and INRIA)

We propose a natural generalization of the concept of implicit definitions over finite structures, allowing non-determinism at an intermediate level of a (deterministic) definition. These generalized implicit definitions offer more expressive power than classical implicit definitions. Moreover, their expressive power can be characterized over unordered finite structures in terms of the complexity class NP $\cap$ co-NP. Finally, we investigate a subclass of these where the non-determinism is restricted to the choice of a unique relation with respect to an implicit linear order, and prove that it captures UP $\cap$ co-UP also over the class of all finite structures. These results shed some light on the expressive power of non-deterministic primitives.
Thursday 25th May 1995, 14:30
Seminar Room 322
Department of Computer Science