Generalized Implicit Definitions on Finite Structures

Abstract 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 ∩ 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 ∩ co-UP also over the class of all finite structures. These results shed some light on the expressive power of non-deterministic primitives.

Authors

• Stéphane Grumbach
• Zoé Lacroix
• Steven Lindell

Keywords

No keywords are indexed for this paper.