Geodesic
Unification Problem in Nelson's Logic $\mathbf{N4}$
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 434-443.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the unification problem for formulas with coeffi-cients in the Nelson's paraconsitent logic $\mathbf{N4}$. By presence coefficients (parameters) the problem is quite not trivial and challenging (yet what makes the problem for $\mathbf{N4}$ to be peculiar is missing of replacement equivalents rule in this logic). It is shown that the unification problem in $\mathbf{N4}$ is decidable for $\sim$-free formulas. We also show that there is an algorithm which computes finite complete sets of unifiers (so to say — all best unifiers) for unifiable in $\mathbf{N4}$ $\sim$-free formulas (i.e. any unifier is equivalent to a substitutional example of a unifier from this complete set). Though the unification problem for all formulas (not $\sim$-free formulas) remains open.
Keywords: Nelson's logic, strong negation, complete sets of unifiers, decidability, Vorob'ev translation.
Mots-clés : unification 
@article{SEMR_2014_11_a13,
     author = {S. P. Odintsov and V. V. Rybakov},
     title = {Unification {Problem}  in {Nelson's} {Logic} $\mathbf{N4}$},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {434--443},
     publisher = {mathdoc},
     volume = {11},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2014_11_a13/}
}
TY  - JOUR
AU  - S. P. Odintsov
AU  - V. V. Rybakov
TI  - Unification Problem  in Nelson's Logic $\mathbf{N4}$
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2014
SP  - 434
EP  - 443
VL  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2014_11_a13/
LA  - en
ID  - SEMR_2014_11_a13
ER  - 
%0 Journal Article
%A S. P. Odintsov
%A V. V. Rybakov
%T Unification Problem  in Nelson's Logic $\mathbf{N4}$
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2014
%P 434-443
%V 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2014_11_a13/
%G en
%F SEMR_2014_11_a13
S. P. Odintsov; V. V. Rybakov. Unification Problem  in Nelson's Logic $\mathbf{N4}$. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 434-443. http://geodesic.mathdoc.fr/item/SEMR_2014_11_a13/

[1] A. Almukdad, D. Nelson, “Constructible falsity and inexact predicates”, J. Sym. Logic, 49 (1984), 231–233 | DOI | MR | Zbl

[2] F. Baader, P. Narendran, “Unification of Concept Terms in Description Logics”, J. Symb. Comput., 31:3 (2001), 277–305 | DOI | MR | Zbl

[3] F. Baader, W. Snyder, “Unification Theory”, Handbook of Automated Reasoning, v. I, eds. J. A. Robinson, A. Voronkov, Elsevier Science Publishers, 2001, 445–533 | DOI | Zbl

[4] F. Baader, R. Küsters, “Unification in a Description Logic with Transitive Closure of Roles”, LPAR, 2001, 217–232 | MR | Zbl

[5] F. Baader, B. Morawska, “Unification in the Description Logic EL”, Logical Methods in Computer Science, 6:3 (2010), 1–31 | DOI | MR

[6] F. Baader, S. Ghilardi, “Unification in modal and description logics”, Logic Journal of the IGPL, 19:6 (2011), 705–730 | DOI | MR | Zbl

[7] W. Dzik, P. Wojtylak, “Projective unification in modal logic”, Logic Journal of IGPL, 20:1 (2012), 121–153 | DOI | MR | Zbl

[8] S. Ghilardi, “Unification in Intuitionistic Logic”, J. Symb. Log., 64:2 (1999), 859–880 | DOI | MR | Zbl

[9] S. Ghilardi, “Unification Through Projectivity”, J. Log. Comput., 7:6 (1997), 733–752 | DOI | MR | Zbl

[10] S. Ghilardi, “Best Solving Modal Equations”, Ann. Pure Appl. Logic, 102:3 (2000), 183–198 | DOI | MR | Zbl

[11] S. Ghilardi, “Unification, finite duality and projectivity in varieties of Heyting algebras”, Ann. Pure Appl. Logic, 127:1–3 (2004), 99–115 | DOI | MR | Zbl

[12] D. Gabbay, U. Reyle, “N-Prolog: — An extension of Prolog with hypothetical implications”, Journal of Logic Programming, 1:4 (1984), 319–355 | DOI | MR | Zbl

[13] E. G. K. López-Escobar, “Refutability and elementary number theory”, Indag. Math., 34 (1972), 362–374 | DOI | MR

[14] D. Nelson, “Constructible falsity”, J. Symb. Logic, 14:2 (1949), 16–26 | DOI | MR | Zbl

[15] S. P. Odintsov, “Algebraic semantics for paraconsistent Nelson's logic”, J. Log. Comput., 13:4 (2003), 453–468 | DOI | MR | Zbl

[16] S. P. Odintsov, Constructive negations and paraconsistency, Springer, Dordrecht, 2008 | MR | Zbl

[17] S. P. Odintsov, V. V. Rybakov, “Unification and admissible rules for paraconsistent minimal Johannson's logic J and positive intuitionistic logic $IPC^+$”, Ann. Pure Appl. Logic, 164 (2013), 771–784 | DOI | MR | Zbl

[18] A. Oliart, W. Snyder, “Fast algorithms for uniform semi-unification”, J. Symb. Comput., 37:4 (2004), 455–484 | DOI | MR | Zbl

[19] J. Levy, M. Villaret, “Nominal Unification from a Higher-Order Perspective”, RTA, 2008, 246–260 | MR | Zbl

[20] H. Rasiowa, “$N$-lattices and constructive logic with strong negation”, Fund. Math., 46 (1958), 61–80 | MR | Zbl

[21] H. Rasiowa, An algebraic approach to non-classical logic, PWN, Warsaw; North-Holland, Amsterdam, 1974 | MR

[22] R. Routley, “Semantical analyses of propositional systems of Fitch and Nelson”, Stud. Log., 33:3 (1974), 283–298 | DOI | MR | Zbl

[23] V. V. Rybakov, “Problems of Substitution and Admissibility in the Modal System Grz and in Intuitionistic Propositional Calculus”, Ann. Pure Appl. Logic, 50:1 (1990), 71–106 | DOI | MR | Zbl

[24] V. V. Rybakov, “Rules of Inference with Parameters for Intuitionistic Logic”, J. Symb. Logic, 57:3 (1992), 912–923 | DOI | MR | Zbl

[25] V. V. Rybakov, Admissibility of Logical Inference Rules, North-Holland Publiching Co., Amsterdam, 1997 | MR

[26] V. Rybakov, “Unifiers in transitive modal logics for formulas with coefficients (meta-variables)”, Logic Journal of IGPL, 21:2 (2013), 205–215 | DOI | MR | Zbl

[27] V. Rybakov, “Writing out unifiers for formulas with coefficients in intuitionistic logic”, Logic Journal of IGPL, 21:2 (2013), 187–198 | DOI | MR | Zbl

[28] N. N. Vorob'ev, “A constructive propositional calculus with strong negation”, Doklady Akademii Nauk SSSR, 85 (1952), 465–468 | MR

[29] N. N. Vorob'ev, “The problem of deducibility in constructive propositional calculus with strong negation”, Doklady Akademii Nauk SSSR, 85 (1952), 689–692 | MR

[30] F. Wolter, M. Zakharyaschev, “Undecidability of the unification and admissibility problems for modal and description logics”, ACM Transactions of Computational Logic (TOCL), 9:4 (2008) | DOI | MR