Admissibility in Finitely Generated Quasivarieties

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

Preview

Text 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.

Interest & Impact

Downloads

239 since deposited on 04 Feb 2014
18 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item