On the axiomatizability of quantitative algebras

Radu Mardare; Prakash Panangaden; Gordon Plotkin

doi:10.1109/LICS.2017.8005102

On the axiomatizability of quantitative algebras

Radu Mardare, Prakash Panangaden, Gordon Plotkin

Computer And Information Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

27 Citations (Scopus)

Abstract

Quantitative algebras (QAs) are algebras over metric spaces defined by quantitative equational theories as introduced by us in 2016. They provide the mathematical foundation for metric semantics of probabilistic, stochastic and other quantitative systems. This paper considers the issue of axiomatizability of QAs. We investigate the entire spectrum of types of quantitative equations that can be used to axiomatize theories: (i) simple quantitative equations; (ii) Horn clauses with no more than c equations between variables as hypotheses, where c is a cardinal and (iii) the most general case of Horn clauses. In each case we characterize the class of QAs and prove variety/quasivariety theorems that extend and generalize classical results from model theory for algebras and first-order structures.

Original language	English
Title of host publication	32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017
Place of Publication	Piscataway, N.J.
Publisher	IEEE
Pages	1-12
Number of pages	12
ISBN (Electronic)	9781509030187
DOIs	https://doi.org/10.1109/LICS.2017.8005102
Publication status	Published - 8 Aug 2017
Event	32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017 - Reykjavik, Iceland Duration: 20 Jun 2017 → 23 Jun 2017

Conference

Conference	32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017
Country/Territory	Iceland
City	Reykjavik
Period	20/06/17 → 23/06/17

Funding

Prakash Panangaden is supported by the Natural Science and Engineering Research Council of Canada, Radu Mardare is supported by the Project 4181-00360 of the Danish Council for Independent Research. We thank Giorgio Bacci, Florence Clerc, Robert Furber, Dexter Kozen and Kim G. Larsen for useful discussions. We thank the Simons Institute for hosting the Fall 2016 program on Logical Structures in Computation which we all attended at various times, benefitting from the stimulating atmosphere there.

Keywords

algebra
mathematical model
extraterrestrial measurements
semantics
cognition

Access to Document

10.1109/LICS.2017.8005102

https://www.research.ed.ac.uk/portal/en/publications/on-the-axiomatizability-of-quantitative-algebras(655773ac-adab-42e2-9f5c-0ab13e4bdf9e).html

Cite this

@inproceedings{f5d785dc21c346a2b3025b975a5faf3c,

title = "On the axiomatizability of quantitative algebras",

abstract = "Quantitative algebras (QAs) are algebras over metric spaces defined by quantitative equational theories as introduced by us in 2016. They provide the mathematical foundation for metric semantics of probabilistic, stochastic and other quantitative systems. This paper considers the issue of axiomatizability of QAs. We investigate the entire spectrum of types of quantitative equations that can be used to axiomatize theories: (i) simple quantitative equations; (ii) Horn clauses with no more than c equations between variables as hypotheses, where c is a cardinal and (iii) the most general case of Horn clauses. In each case we characterize the class of QAs and prove variety/quasivariety theorems that extend and generalize classical results from model theory for algebras and first-order structures.",

keywords = "algebra, mathematical model, extraterrestrial measurements, semantics, cognition",

author = "Radu Mardare and Prakash Panangaden and Gordon Plotkin",

year = "2017",

month = aug,

day = "8",

doi = "10.1109/LICS.2017.8005102",

language = "English",

pages = "1--12",

booktitle = "32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017",

publisher = "IEEE",

note = "32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017 ; Conference date: 20-06-2017 Through 23-06-2017",

}

TY - GEN

T1 - On the axiomatizability of quantitative algebras

AU - Mardare, Radu

AU - Panangaden, Prakash

AU - Plotkin, Gordon

PY - 2017/8/8

Y1 - 2017/8/8

N2 - Quantitative algebras (QAs) are algebras over metric spaces defined by quantitative equational theories as introduced by us in 2016. They provide the mathematical foundation for metric semantics of probabilistic, stochastic and other quantitative systems. This paper considers the issue of axiomatizability of QAs. We investigate the entire spectrum of types of quantitative equations that can be used to axiomatize theories: (i) simple quantitative equations; (ii) Horn clauses with no more than c equations between variables as hypotheses, where c is a cardinal and (iii) the most general case of Horn clauses. In each case we characterize the class of QAs and prove variety/quasivariety theorems that extend and generalize classical results from model theory for algebras and first-order structures.

AB - Quantitative algebras (QAs) are algebras over metric spaces defined by quantitative equational theories as introduced by us in 2016. They provide the mathematical foundation for metric semantics of probabilistic, stochastic and other quantitative systems. This paper considers the issue of axiomatizability of QAs. We investigate the entire spectrum of types of quantitative equations that can be used to axiomatize theories: (i) simple quantitative equations; (ii) Horn clauses with no more than c equations between variables as hypotheses, where c is a cardinal and (iii) the most general case of Horn clauses. In each case we characterize the class of QAs and prove variety/quasivariety theorems that extend and generalize classical results from model theory for algebras and first-order structures.

KW - algebra

KW - mathematical model

KW - extraterrestrial measurements

KW - semantics

KW - cognition

U2 - 10.1109/LICS.2017.8005102

DO - 10.1109/LICS.2017.8005102

M3 - Conference contribution book

AN - SCOPUS:85034056768

SP - 1

EP - 12

BT - 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017

PB - IEEE

CY - Piscataway, N.J.

T2 - 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017

Y2 - 20 June 2017 through 23 June 2017

ER -

On the axiomatizability of quantitative algebras

Abstract

Conference

Funding

Keywords

Access to Document

Fingerprint

Cite this