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.
","abstract_html":"<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>","abstract_has_math":false,"creators":["St. John, Gavin"],"institution":null,"degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Nikolaos Galatos, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-01-01T08:00:00Z","date_published":"2019-01-01T08:00:00Z","updated_at":"2026-07-24T02:02:30Z","subjects":["Algebraic logic","Decidability","Residuated lattice","Substructural logic","Undecidability","Algebra","Mathematics","Physical Sciences and Mathematics"],"languages":["en"],"rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.du.edu/etd/1623","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Nikolaos Galatos, Ph.D."]},{"key":"dc:creator","label":"Author","values":["St. John, Gavin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2019-08-02T07:00:00Z"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Algebraic logic","Decidability","Residuated lattice","Substructural logic","Undecidability","Algebra","Mathematics","Physical Sciences and Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright is held by the author. User is responsible for all copyright compliance.
"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.du.edu/etd/1623"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Decidability for Residuated Lattices and Substructural Logics"]}]}],"canonical_facts":{"dc:contributor":["Nikolaos Galatos, Ph.D."],"dc:creator":["St. John, Gavin"],"dc:date.available":["2019-08-02T07:00:00Z"],"dc:description.abstract":["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.
"],"dc:format":["application/pdf"],"dc:identifier":["https://digitalcommons.du.edu/etd/1623"],"dc:language":["en"],"dc:rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"dc:subject":["Algebraic logic","Decidability","Residuated lattice","Substructural logic","Undecidability","Algebra","Mathematics","Physical Sciences and Mathematics"],"dc:title":["Decidability for Residuated Lattices and Substructural Logics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."]},"updated_at":"2026-07-24T02:02:30Z"}