Decidability for Residuated Lattices and Substructural Logics

<p>We present a number of results related to the decidability and undecidability of various varieties of residuated lattices and their corresponding substructural logics. The context of this analysis is the extension of residuated lattices by various simple equations, dually, the extension of substructural logics by simple structural rules, with the aim of classifying simple equations by the decidability properties shared by their extensions. We also prove a number of relationships among simple extensions by showing the equational theory of their idempotent semiring reducts coincides with simple extensions of idempotent semirings. On the decidability front, we develop both semantical and syntactical methods for establishing decidability as well as tractability of decision procedures. On the undecidability front, we develop a notion of algebraic machines for which the theory of residuated frames will allow us to encode decision problems within the theories of residuated lattices and their substructural analogues. We prove the undecidability of the word problem for a broad class of simple extensions for both commutative and non-commutative residuated lattices. Furthermore, through a deduction theorem we establish the undecidability of the equational theory for a broad class of simple extensions. Translated in terms of substructural logics, we prove that the undecidability of both provability and deducibility for a multitude of extensions of FLe by simple rules.</p>

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Year dc:date.available

2019

Author dc:creator

• St. John, Gavin

Contributors dc:contributor

• Nikolaos Galatos, Ph.D.

• Algebraic logic
• Decidability
• Residuated lattice
• Substructural logic
• Undecidability
• Algebra
• Mathematics
• Physical Sciences and Mathematics

Statement dc:rights

• <p>Copyright is held by the author. User is responsible for all copyright compliance.</p>

Language dc:language

en

Repository record dc:identifier

https://digitalcommons.du.edu/etd/1623

OAI identifier oai:identifier

oai:digitalcommons.du.edu:etd-2623