# Differences

This shows you the differences between two versions of the page.

action_algebras [2010/07/29 15:09]
jipsen created
action_algebras [2012/06/23 20:39] (current)
jipsen
Line 1: Line 1:
-f+=====Action algebras=====
+
+Abbreviation: **Act**
+====Definition====
+An \emph{action algebra} is a structure $\mathbf{A}=\langle A,\vee,\bot,\cdot,1,^*,\backslash,/\rangle$ of type
+$\langle 2,0,2,0,1,2,2\rangle$ such that
+
+
+$\langle A,\vee,\bot,\cdot,1,^*\rangle$ is a [[Kleene algebra]]
+
+
+$\backslash$ is the left residual of $\cdot$:  $y\leq x\backslash z\Longleftrightarrow xy\leq z$
+
+
+$/$ is the right residual of $\cdot$:  $x\leq z/y\Longleftrightarrow xy\leq z$
+
+
+Remark: These equivalences can be written equationally.
+
+
+==Morphisms==
+Let $\mathbf{A}$ and $\mathbf{B}$ be action algebras.
+A morphism from $\mathbf{A}$ to $\mathbf{B}$ is a function $h:A\rightarrow B$ that is a
+homomorphism:
+$h(x\vee y)=h(x)\vee h(y)$, $h(x\cdot y)=h(x)\cdot h(y)$, $h(x\backslash y)=h(x)\backslash h(y)$,
+$h(x/y)=h(x)/h(y)$, $h(x^*)=h(x)^*$, $h(\bot)=\bot$ and $h(1)=1$.
+
+====Examples====
+Example 1:
+
+====Basic results====
+
+
+====Properties====
+^[[Classtype]]  |variety [(Pratt1991)] |
+^[[Equational theory]]  | |
+^[[Quasiequational theory]]  |undecidable |
+^[[First-order theory]]  |undecidable |
+^[[Locally finite]]  |no |
+^[[Residual size]]  |unbounded |
+^[[Congruence distributive]]  |yes [(AltRaf2004)] |
+^[[Congruence modular]]  |yes  |
+^[[Congruence n-permutable]]  |yes, $n=4$ [(AltRaf2004)] |
+^[[Congruence regular]]  | |
+^[[Congruence uniform]]  | |
+^[[Congruence extension property]]  | |
+^[[Definable principal congruences]]  | |
+^[[Equationally def. pr. cong.]]  | |
+^[[Amalgamation property]]  | |
+^[[Strong amalgamation property]]  | |
+^[[Epimorphisms are surjective]]  | |
+
+====Finite members====
+
+$\begin{array}{lr} +f(1)= &1\\ +f(2)= &1\\ +f(3)= &3\\ +f(4)= &20\\ +f(5)= &149\\ +f(6)= &1488 +\end{array}$
+
+
+====Subclasses====
+[[Action lattices]]
+
+====Superclasses====
+[[Kleene algebras]]
+
+[[Residuated join-semilattices]]
+
+
+====References====
+
+[(Pratt1991>
+Vaughan Pratt, \emph{Action logic and pure induction},
+Logics in AI (Amsterdam, 1990)'', Lecture Notes in Comput. Sci.,
+478, 1991, 97--120, 92d:03016)]
+
+[(AltRaf2004>
+C.J. van Alten and J.G. Raftery, \emph{Embedding Theorems and Rule Separation in Logics without Weakening},
+Studia Logica, 2004, ...--..., [[preprint]]
+)]

##### Toolbox 