Admissibility in Finitely Generated Quasivarieties

Röthlisberger, Christoph; Metcalfe, George (2013). Admissibility in Finitely Generated Quasivarieties. Logical Methods in Computer Science, 9(2) International Federation for Computational Logic 10.2168/LMCS-9(2:9)2013

1305.3530.pdf - Published Version
Available under License Creative Commons: Attribution-No Derivative Works (CC-BY-ND).

Download (275kB) | Preview

Checking the admissibility of quasiequations in a finitely generated (i.e., generated by a finite set of finite algebras) quasivariety Q amounts to checking validity in a suitable finite free algebra of the quasivariety, and is therefore decidable. However, since free algebras may be large even for small sets of small algebras and very few generators, this naive method for checking admissibility in Q is not computationally feasible. In this paper, algorithms are introduced that generate a minimal (with respect to a multiset well-ordering on their cardinalities) finite set of algebras such that the validity of a quasiequation in this set corresponds to admissibility of the quasiequation in Q. In particular, structural completeness (validity and admissibility coincide) and almost structural completeness (validity and admissibility coincide for quasiequations with unifiable premises) can be checked. The algorithms are illustrated with a selection of well-known finitely generated quasivarieties, and adapted to handle also admissibility of rules in finite-valued logics.

Item Type: Journal Article (Original Article)
Division/Institute: 08 Faculty of Science > Department of Mathematics and Statistics > Institute of Mathematics
UniBE Contributor: Röthlisberger, Christoph and Metcalfe, George
Subjects: 100 Philosophy > 160 Logic
500 Science > 510 Mathematics
ISSN: 1860-5974
Publisher: International Federation for Computational Logic
Language: English
Submitter: George Metcalfe
Date Deposited: 04 Feb 2014 09:40
Last Modified: 14 Apr 2015 16:11
Publisher DOI: 10.2168/LMCS-9(2:9)2013
BORIS DOI: 10.7892/boris.40835

Actions (login required)

Edit item Edit item
Provide Feedback