George Metcalfe ; Christoph Röthlisberger - Admissibility in Finitely Generated Quasivarieties

lmcs:733 - Logical Methods in Computer Science, June 25, 2013, Volume 9, Issue 2 - https://doi.org/10.2168/LMCS-9(2:9)2013
Admissibility in Finitely Generated QuasivarietiesArticle

Authors: George Metcalfe ; Christoph Röthlisberger

    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.


    Volume: Volume 9, Issue 2
    Published on: June 25, 2013
    Imported on: November 30, 2012
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic
    Funding:
      Source : OpenAIRE Graph
    • Admissible Rules: From Characterizations to Applications; Funder: Swiss National Science Foundation; Code: 146748
    • Immunologie des Typ-1 Diabetes.; Funder: Swiss National Science Foundation; Code: 20002
    • Admissible Rules in Logic and Algebra; Funder: Swiss National Science Foundation; Code: 129507

    13 Documents citing this article

    Consultation statistics

    This page has been seen 1132 times.
    This article's PDF has been downloaded 390 times.