More Web Proxy on the site http://driver.im/

research-article

One-variable fragments of intermediate logics over linear frames

Authors:

Xavier Caicedo,

George Metcalfe,

Ricardo Rodríguez,

Olim TuytAuthors Info & Claims

Volume 287, Issue C

https://doi.org/10.1016/j.ic.2021.104755

Published: 01 September 2022 Publication History

Abstract

A correspondence is established between one-variable fragments of (first-order) intermediate logics defined over a fixed countable linear frame and Gödel modal logics defined over many-valued equivalence relations with values in a closed subset of the real unit interval. It is also shown that each of these logics can be interpreted in the one-variable fragment of the corresponding constant domain intermediate logic, which is equivalent to a Gödel modal logic defined over (crisp) equivalence relations. Although the latter modal logics in general lack the finite model property with respect to their frame semantics, an alternative semantics is defined that has this property and used to establish co-NP-completeness results for the one-variable fragments of the corresponding intermediate logics both with and without constant domains.

References

[1]

X. Caicedo, G. Metcalfe, R. Rodríguez, O. Tuyt, The one-variable fragment of Corsi logic, in: Proceedings of WoLLIC 2019, in: LNCS, vol. 11541, Springer, 2019, pp. 70–83.

[2]

H. Ono, N.-Y. Suzuki, Relations between intuitionistic modal logics and intermediate predicate logics, Rep. Math. Log. 22 (1988) 65–87.

[3]

N.-Y. Suzuki, Kripke bundles for intermediate predicate logics and Kripke frames for intuitionistic modal logics, Stud. Log. 49 (3) (1990) 289–306.

[4]

G. Bezhanishvili, Varieties of monadic Heyting algebras - part I, Stud. Log. 61 (3) (1998) 367–402.

[5]

P. Hájek, On fuzzy modal logics S5(C), Fuzzy Sets Syst. 161 (18) (2010) 2389–2396.

[6]

F. Wolter, M. Zakharyaschev, Intuitionistic modal logics as fragments of classical bimodal logics, in: E. Orlowska (Ed.), Logic at Work, Springer, 1999, pp. 168–186.

[7]

D. Gabbay, A. Kurucz, F. Wolter, M. Zakharyaschev, Many-Dimensional Modal Logics, Elsevier, 2003.

[8]

R. Kontchakov, A. Kurucz, M. Zakharyaschev, Undecidability of first-order intuitionistic and modal logics with two variables, Bull. Symb. Log. 11 (3) (2005) 428–438.

[9]

M. Rybakov, D. Shkatov, Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter, Stud. Log. 107 (2019) 695–717.

Digital Library

[10]

M. Takano, Ordered sets R and Q as bases of Kripke models, Stud. Log. 46 (1987) 137–148.

[11]

M. Dummett, A propositional calculus with denumerable matrix, J. Symb. Log. 24 (1959) 97–106.

[12]

X. Caicedo, R. Rodríguez, Bi-modal Gödel logic over [0, 1]-valued Kripke frames, J. Log. Comput. 25 (1) (2015) 37–55.

[13]

A. Beckmann, N. Preining, Linear Kripke frames and Gödel logics, J. Symb. Log. 72 (2007) 26–44.

[14]

X. Caicedo, R. Rodríguez, Standard Gödel modal logics, Stud. Log. 94 (2) (2010) 189–214.

[15]

G. Metcalfe, N. Olivetti, Towards a proof theory of Gödel modal logics, Log. Methods Comput. Sci. 7 (2) (2011) 1–27.

[16]

X. Caicedo, G. Metcalfe, R. Rodríguez, J. Rogger, Decidability in order-based modal logics, J. Comput. Syst. Sci. 88 (2017) 53–74.

[17]

L. Blandi, L. Godo, R. Rodríguez, A connection between similarity logic programming and Gödel modal logic, in: Proc. EUSFLAT 2005, Universidad Polytecnica de Catalunya, 2005, pp. 775–7080.

[18]

S. Schockaert, M.D. Cock, E. Kerre, Spatial reasoning in a fuzzy region connection calculus, Artif. Intell. 173 (2) (2009) 258–298.

[19]

P. Dellunde, L. Godo, E. Marchioni, Extending possibilistic logic over Gödel logic, Int. J. Approx. Reason. 52 (1) (2011) 63–75.

[20]

P. Hájek, Making fuzzy description logic more general, Fuzzy Sets Syst. 154 (1) (2005) 1–15.

[21]

F. Bobillo, M. Delgado, J. Gómez-Romero, U. Straccia, Fuzzy description logics under Gödel semantics, Int. J. Approx. Reason. 50 (3) (2009) 494–514.

[22]

S. Borgwardt, F. Distel, R. Peñaloza, The limits of decidability in fuzzy description logics with general concept inclusions, Artif. Intell. 218 (2015) 23–55.

[23]

G. Corsi, Completeness theorem for Dummett's LC quantified, Stud. Log. 51 (1992) 317–335.

[24]

S. Kripke, Semantical analysis of intuitionistic logic I, in: J. Crossley, M. Dummett (Eds.), Formal Systems and Recursive Functions, in: Studies in Logic and the Foundations of Mathematics, vol. 40, Elsevier, 1965, pp. 92–130.

[25]

S. Görnemann, A logic stronger than intuitionism, J. Symb. Log. 36 (2) (1971) 249–261.

[26]

R. Bull, MIPC as formalisation of an intuitionist concept of modality, J. Symb. Log. 31 (1966) 609–616.

[27]

H. Ono, On some intuitionistic modal logics, Publ. RIMS, Kyoto Univ. 13 (1977) 687–722.

[28]

P. Hájek, Metamathematics of Fuzzy Logic, Kluwer, Dordrecht, 1998.

[29]

A. Beckmann, M. Goldstern, N. Preining, Continuous Fraissé conjecture, Order 25 (2008) 281–298.

[30]

A. Horn, Logic with truth values in a linearly ordered Heyting algebra, J. Symb. Log. 34 (3) (1969) 395–409.

[31]

Y. Moschovakis, Descriptive Set Theory, North-Holland, 1980.

[32]

N. Preining, Characterization of Gödel Logics, PhD Thesis TU Wien, 2003.

[33]

R. Iemhoff, A note on linear Kripke models, J. Log. Comput. 15 (4) (2005) 489–506.

[34]

F. Bou, F. Esteva, L. Godo, R. Rodríguez, Possibilistic Semantics for a Modal KD45 Extension of Gödel Fuzzy Logic, Proceedings of IPMU 2016, vol. 21, Springer, 2016, pp. 123–135.

[35]

M. Baaz, N. Preining, R. Zach, First-order Gödel logics, Ann. Pure Appl. Log. 147 (2007) 23–47.

[36]

M. Baaz, A. Ciabattoni, N. Preining, First-order satisfiability in Gödel logics: an NP-complete fragment, Theor. Comput. Sci. 412 (47) (2011) 6612–6623.

[37]

P. Minari, M. Takano, H. Ono, Intermediate predicate logics determined by ordinals, J. Symb. Log. 55 (3) (1990) 1099–1124.

[38]

A. Beckmann, N. Preining, Separating intermediate predicate logics of well-founded and dually well-founded structures by monadic sentences, J. Log. Comput. 25 (3) (2014) 527–547.

Index Terms

One-variable fragments of intermediate logics over linear frames
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Probabilistic reasoning
      2. Vagueness and fuzzy logic
  2. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Theory of computation
  1. Logic
    1. Constraint and logic programming
    2. Modal and temporal logics

Index terms have been assigned to the content through auto-classification.

Recommendations

Intermediate Logics Admitting a Structural Hypersequent Calculus

We characterise the intermediate logics which admit a cut-free hypersequent calculus of the form $$\mathbf {HLJ} + \mathscr {R}$$HLJ+R, where $$\mathbf {HLJ}$$HLJ is the hypersequent counterpart of the sequent calculus $$\mathbf {LJ}$$LJ for ...
On the concurrent computational content of intermediate logics
Abstract
We provide a proofs-as-concurrent-programs interpretation for a large class of intermediate logics that can be formalized by cut-free hypersequent calculi. Obtained by adding classical disjunctive tautologies to intuitionistic logic, ...
Eliminability of cut in hypersequent calculi for some modal logics of linear frames

Hypersequent calculus HC for three modal logics of linear frames (K4.3, KD4.3 and S4.3) is presented.Adequacy of HC for these logics is shown.Eliminability of Cut is demonstrated. Hypersequent calculi, introduced independently by Pottinger and Avron, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 287, Issue C

Sep 2022

220 pages

ISSN:0890-5401

Issue’s Table of Contents

The Author(s).

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 September 2022

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents