Ehrenfeucht Games and Paraconsistent Annotated Logics

摘要

The Ehrenfeucht Theorem is one of the important results of classical finite model theory. Roughly speaking, this theorem is a "tool" to search for "isomorphic pieces" of two given structures. The theorem has algorithmic aspects because it is based on the Ehrenfeucht Game: one of the two players can, through a winning strategy, "build" an "isomorphic" piece in one of the two given structures in a step-by-step manner. On the other hand we have paraconsistent logics and more especifically annotated paraconsistent logics which has found many applications on AI and Robotics and which was introduced in the area of logic programming by V.S. Subrahmanian and studied by a foundational viewpoint by J.M.Abe, N.C.A. da Costa, S.Akama among others. The goal of this paper is to present an extension of the Ehrenfeucht Game for paraconsistent annotated logics.