Nerio Borges

Nerio Borges

Auto-generated profile, based on publicly available information

Nerio Borges

Departamento de Matemáticas Universidad Simón Bolívar Caracas Venezuela

Research Focus & Metrics

Academic Career Length

20Years (2007-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
4 September 2012 in arXiv
Verified
Preprint
Open access
PDF file
NBNerio Borges
Nerio Borges
We here present a sufficient condition for general arrowing problems to be non definable in first order logic, based in well known tools of finite model theory e.g. Hanf's Theorem and known concepts in finite combinatorics, like senders and determiners.

22 June 2007 in arXiv
Verified
Preprint
Open access
PDF file
NBNerio Borges
Nerio Borges
BBBlai Bonet
Blai Bonet
The class of problems complete for NP via first-order reductions is known to be characterized by existential second-order sentences of a fixed form. All such sentences are built around the so-called generalized IS-form of the sentence that defines Independent-Set. This result can also be understood as that every sentence that defines a NP-complete problem P can be decomposed in two disjuncts such that the first one characterizes a fragment of P as hard as Independent-Set and the second the rest of P. That is, a decomposition that divides every such sentence into a quotient and residue modulo Independent-Set. In this paper, we show that this result can be generalized over a wide collection of complexity classes, including the so-called nice classes. Moreover, we show that such decomposition can be done for any complete problem with respect to the given class, and that two such decompositions are non-equivalent in general. Interestingly, our results are based on simple and well-known properties of first-order reductions.ow that this result can be generalized over a wide collection of complexity classes, including the so-called nice classes. Moreover, we show that such decomposition can be done for any complete problem with respect to the given class, and that two such decompositions are non-equivalent in general. Interestingly, our results are based on simple and well-known properties of first-order reductions.

30 October 2019 in arXiv
Verified
Preprint
Open access
PDF file
NBNerio Borges
Nerio Borges
RPRamón Pino Pérez
Ramón Pino Pérez
In most classical models of belief change, epistemic states are represented by theories (AGM) or formulas (Katsuno-Mendelzon) and the new pieces of information by formulas. The Representation Theorem for revision operators says that operators are represented by total preorders. This important representation is exploited by Darwiche and Pearl to shift the notion of epistemic state to a more abstract one, where the paradigm of epistemic state is indeed that of a total preorder over interpretations. In this work, we introduce a 3-valued logic where the formulas can be identified with a generalisation of total preorders of three levels: a ranking function mapping interpretations into the truth values. Then we analyse some sort of changes in this kind of structures and give syntactical characterizations of them.