# Kleene Algebra With Tests for Weighted Programs††thanks: This work was
supported by the grant GA22-16111S of the Czech Science Foundation. The author
is grateful to the reviewers for useful comments.

Igor Sedlár  The Czech Academy of Sciences, Institute of Computer Science
Prague, The Czech Republic
<EMAIL_ADDRESS>
###### Abstract

Weighted programs generalize probabilistic programs and offer a framework for
specifying and encoding mathematical models by means of an algorithmic
representation. Kleene algebra with tests is an algebraic formalism based on
regular expressions with applications in proving program equivalence. We
extend the language of Kleene algebra with tests so that it is sufficient to
formalize reasoning about a simplified version weighted programs. We introduce
relational semantics for the extended language, and we generalize the
relational semantics to an appropriate extension of Kleene algebra with tests,
called Kleene algebra with weights and tests. We demonstrate by means of an
example that Kleene algebra with weights and tests offers a simple algebraic
framework for reasoning about equivalence and optimal runs of weighted
programs.

###### Index Terms:

Kleene algebra with tests, program equivalence, program semantics, regular
programs, weighted programs

##  I Introduction

_Weighted programs_ [3] add two features to standard while programs [1]: (i)
nondeterministic branching, and (ii) the ability to weight the current
execution trace. As such, they generalize probabilistic programs [2], in which
execution can branch based on the outcome of a random coin flip.

Batz et al. [3] argue that, in addition to being an interesting
generalization, weighted programs offer a useful programming paradigm for
specifying and encoding mathematical models, such as optimization problems or
probability distributions, by means of an algorithmic representation. They
introduce structural operational semantics and a Dijkstra-style weakest
precondition calculus for weighted programs, and they use this calculus to
determine competitive ratios of weighted programs.

Kleene algebra with tests [10], KAT, is an extension of the algebraic theory
of regular languages that provides a simple algebraic formalism for equational
specification and verification of while programs, and for proving equivalence
of programs. In this note we extend the language of KAT so that it is
sufficient to formalize reasoning about a propositional abstraction of
weighted programs where assignments are replaced by unstructured atomic
actions. We introduce relational semantics for the extended language, and we
generalize the relational semantics to an appropriate extension of Kleene
algebra with tests, called Kleene algebra with weights and tests, or KAWT. We
demonstrate by means of an example that KAWT offers a simple algebraic
framework for reasoning about equivalence and optimal runs of weighted
programs.

The note is structured as follows. Section II introduces _weighted regular
programs_ , an expansion of regular programs with weights, and shows that
weighted regular programs can express a propositional abstraction of weighted
programs where assignments are replaced by unstructured atomic actions.
Section III introduces a relational semantics for weighted regular programs
using weighted transition systems where weights are elements of an arbitrary
semiring. Section IV recalls the basics of Kleene algebra and Section V
introduces an expansion of Kleene algebra with tests that generalizes the
relational semantics of weighted regular programs. The expansion is called
_Kleene algebra with weights and tests_ , and it adds a semiring subalgebra
(representing weights) to Kleene algebra with tests. Section VI demonstrates
by means of an example how Kleene algebra with weights and tests can be used
to reason about equivalence and optimal runs of regular while programs.

##  II Weighted programs

It is well-known that while programs can be represented using the syntax of
_regular programs_ [13, 5]. The latter contains nondeterministic branching (or
choice) as one of the basic operations, so it is natural to extend regular
programs with weights to capture weighted programs. For the sake of
simplicity, we will work with a propositional abstraction of weighted programs
where assignments $\mathtt{x}:=E$ are replaced by unstructured “atomic
programs” in the style of [5, 10]. We will see that even in this simpler
setting we are able to carry out a significant amount of reasoning about
weighted programs.

######  Definition 1.

A _signature_ is $\Sigma=(\mathsf{P},\mathsf{B},\mathsf{F})$, a triple of
disjoint sets of variables, intuitively representing atomic programs, Boolean
tests, and weighted tests, respectively. The set of _weighted regular programs
over $\Sigma$_, $\mathsf{WRP}_{\Sigma}$, consists of expressions of the
following sorts:

Boolean expressions | $b,c:=$ | $\mathtt{b}\mid\mathtt{0}\mid\mathtt{1}\mid b\cdot c\mid b+c\mid\neg b$
---|---|---
Weightings | $f,g:=$ | $\mathtt{f}\mid\mathtt{0}\mid\mathtt{1}\mid f\cdot g\mid f+g$
Programs | $p,q:=$ | $\mathtt{p}\mid b\mid f\mid p+q\mid p\cdot q\mid p^{*}$

(It is assumed that $\mathtt{b}\in\mathsf{B}$, $\mathtt{f}\in\mathsf{F}$, and
$\mathtt{p}\in\mathsf{P}$.) We will sometimes write $\bar{b}$ instead of $\neg
b$ and $pq$ instead of $p\cdot q$.

The language of weighted regular programs extends the language of Kleene
algebra with tests [10] corresponding to regular programs by adding the sort
of “weightings”, that is, semiring terms representing assignments of weights
to computation paths. Weights are represented by elements of an abstract
semiring [4, 12]. Recall how the language of KAT expresses standard control
flow commands of while programs:

  * •

skip $:=\mathtt{1}$ and abort $:=\mathtt{0}$

  * •

sequential composition $p\,;\,q:=pq$

  * •

if $b$ then $p$ else $q$ $:=(bp)+(\neg bq)$

  * •

while $b$ do $p$ $:=(bp)^{*}\neg b$

Note that nondeterministic branching (choice) is represented in the language
of regular programs by the $+$ operator.

######  Example 1.

Recall the “ski rental program”, the main motivating example of a weighted
program in [3]:111The ski rental problem is an optimization problem regarding
a situation where one goes for a skying trip for $n$ days and has the choice
of renting a pair of skis for $1$ Euro per day vs. buying a pair of skis for
$y$ Euros.

1: while $n>0$ do

2: $n:=n-1$ ;

3: $\big{\\{}$ $\odot 1$

4: $\oplus$

5: $\odot y\,;\,n:=0$ $\big{\\}}$

6: end while

The operator $\oplus$ in line 4 expresses nondeterministic branching between
computation sequences, one of which executes the “weighting” $\odot 1$, or
“add one unit of weight” and returns to the beginning of the while loop, and
the other executes $\odot y$, or “add $y$ units of weight”, then assigns
$n:=0$, and then returns to the beginning of the loop, after which the Boolean
test $n>0$ is evaluated as False and the computation halts.

The structure of the ski rental program can be represented by the following
weighted regular program (for the sake of readability, we use descriptive
variable names, bold font for weighting variables, and we enclose Boolean
expressions in curly brackets):

$\Big{(}\\{\texttt{neq0}\\}\big{(}\texttt{sub1}(\texttt{one}+\texttt{skis}\,\texttt{end})\big{)}\Big{)}^{*}\,\\{\neg\texttt{neq0}\\}\,.$
(1)

In this program, $\texttt{neq0}\in\mathsf{B}$ represents the test $n>0$,
$\texttt{sub1}\in\mathsf{P}$ represents the instruction $n:=n-1$ to subtract
$1$ from the value of $n$, $\texttt{end}\in\mathsf{P}$ represents the
assignment $n:=0$ that ends the loop, and
$\texttt{one},\texttt{skis}\in\mathsf{F}$ represent the weightings $\odot 1$
(adding one unit of weight) and $\odot y$ (adding the price of the skis),
respectively.

##  III Relational semantics

In this section we introduce relational semantics for weighted regular
programs, based on semiring-valued transition systems.

######  Definition 2.

A _semiring_ is $\mathbf{S}=(S,+,\cdot,1,0)$ where

  * •

$(S,+,0)$ is a commutative monoid;

  * •

$(S,\cdot,1)$ is a monoid;

  * •

$x\cdot(y+z)=(x\cdot y)+(x\cdot z)$ and $(x+y)\cdot z=(x\cdot z)+(y\cdot z)$;

  * •

$0\cdot x=0=x\cdot 0$.

A semiring is _idempotent_ iff $x+x=x$ for all $x\in S$. A semiring is
_complete_ iff $(S,+,0)$ is a complete monoid and the following distributivity
laws hold:

$\sum_{i\in I}(x\cdot x_{i})=x\cdot\left(\sum_{i\in
I}x_{i}\right)\qquad\sum_{i\in I}(x_{i}\cdot x)=\left(\sum_{i\in
I}x_{i}\right)\cdot x$

(Complete idempotent semirings are also known as _quantales_.) We define the
_natural order_ $\preceq$ on a semiring as follows:

$x\preceq y\iff\exists z(x+z=y)\,.$

We note that in idempotent semirings the natural order coincides with the
semilattice order $\leq$ defined by $x\leq y\iff x+y=y$.

######  Example 2.

(1) An example of a complete idempotent semiring that is well known especially
from shortest path algorithms is the _tropical semiring_ over extended natural
numbers

$\mathbf{T}=(\mathbb{N}^{\infty},\mathrm{min},+,0^{\mathbb{N}},\infty)$

where

  * •

$\mathbb{N}^{\infty}=\mathbb{N}\cup\\{\infty\\}$, where
$\infty\notin\mathbb{N}$;

  * •

$\mathrm{min}$ is the minimum operation extended to $\mathbb{N}^{\infty}$ by
defining $\mathrm{min}(n,\infty)=\mathrm{min}(\infty,n)=n$ for all $n$;
$\mathrm{min}$ is seen as semiring addition (hence, $\infty$ is the minimal
element in the ordering $\leq$ defined by $x\leq y$ iff
$\mathrm{min}(x,y)=y$);

  * •

$+$, representing semiring multiplication, is addition on $\mathbb{N}$ and
$n+\infty=\infty=\infty+n$ for all $n$ (hence, $\infty$ is the annihilator
element);

  * •

$0^{\mathbb{N}}$, the natural number zero, is the neutral element with respect
to $+$.

(2) Another example well-known from the theory of fuzzy logic is the
_Łukasiewicz semiring_ $\textbf{{\L}}=([0,1],\mathrm{max},\otimes,1,0)$ where
$[0,1]$ is the real unit interval and $\otimes$ is the Łukasiewicz t-norm
$x\otimes y=\mathrm{max}\\{0,x+y-1\\}$.

Intuitively, semirings can be seen as representing a set of _weights_ together
with an operation of weight addition (semiring multiplication $\cdot$), a
weight comparison relation $\preceq$ induced by semiring addition $+$, and two
designated weights, namely, “no weight” $1$ and the “absolute” weight $0$.

######  Definition 3.

Let $\mathbf{S}$ be a semiring. An _$\mathbf{S}^{\Sigma}$ -transition system_
is $(X,L)$ where $X\neq\emptyset$ and $L$ is a function such that

$L(\mathtt{p})\subseteq X\times X$ $L(\mathtt{b})\subseteq X$
$L(\mathtt{f})\in\mathbf{S}\,.$

Intuitively, $(s,t)\in L(\mathtt{p})$ means that the atomic program
$\mathtt{p}$ may terminate in state $t$ when executed in state $s$; $s\in
L(\mathtt{b})$ means that the atomic Boolean expression $\mathtt{b}$ is
evaluated to True in $s$; and $L(\mathtt{f})\in\mathbf{S}$ is the weight
assigned to the atomic weighting expression $\mathtt{f}$.

Equivalently, $L$ in an $\mathbf{S}^{\Sigma}$-transition system can be seen as
a function from $\bigcup\Sigma$ to $\mathbf{S}^{X\times X}$ such that

  * •

$L(\mathtt{p}),L(\mathtt{b})\in\\{0,1\\}^{X\times X}$;

  * •

$L(\mathtt{b})(s,t)=0$ and $L(\mathtt{f})(s,t)=0$ if $s\neq t$;

  * •

$L(\mathtt{f})(s,t)=L(\mathtt{f})(s^{\prime},t^{\prime})$ for all
$s,s^{\prime},t,t^{\prime}\in X$.

(In effect, $L(\mathtt{b})$ and $L(\mathtt{f})$ are functions from the
identity relation on $S$ which in turn represents $S$.)

In a given $\mathbf{S}^{\Sigma}$-semiring, $L$ can be extended to a function
$\mathsf{WRP}_{\Sigma}\to\mathbf{2}^{X\times X}$ specifying the interpretation
of each weighted regular program by lifting the weighted regular program
operations to the set of functions $X\times X\to\mathbf{S}$ :

######  Definition 4.

Let $\lambda,\lambda^{\prime}\in\mathbf{S}^{X\times X}$ and let
$\theta\in\\{0,1\\}^{X\times X}$

  * •

$\mathbf{1}=\mathrm{id}_{X}$ (the identity relation on $X$);

  * •

$\mathbf{0}(s,t)=0$;

  * •

$(\lambda+\lambda^{\prime})(s,t)=\lambda(s,t)+\lambda^{\prime}(s,t)$;

  * •

$(\lambda\cdot\lambda^{\prime})(s,t)=\sum\\{\lambda(s,u)\cdot\lambda^{\prime}(u,t)\mid
u\in X\\}$;

  * •

$(\neg\theta)(s,t)=\begin{cases}1&\text{if }s=t\text{ and }\theta(s,t)=0\\\
0&\text{otherwise;}\end{cases}$

  * •

$\lambda^{0}=\mathbf{1}$ and $\lambda^{n+1}=\lambda^{n}\cdot\lambda$.

If $\mathbf{S}$ is a complete semiring, then we define:

  * •

$\lambda^{*}=\sum_{n\geq 0}\lambda^{n}$.

It is easily checked that $(\mathbf{S}^{X\times
X},\cdot,+,\mathbf{1},\mathbf{0})$ is a semiring; see Lemma 1 below. We denote
$\\{0,1\\}^{X\times X}$ as $2^{X\times X}$.

##  IV Kleene algebra

Kleene algebras [8, 9] are structures that arise naturally in the study of
regular languages, finite automata and shortest path algorithms, for instance.
Kleene algebra offers an elegant framework for equational reasoning about
regular programs [10]. In this section we recall the basic preliminaries on
Kleene algebra.

######  Definition 5.

A _Kleene algebra_ is an idempotent semiring with a unary operation ∗ that
satisfies the following (quasi)equations:

$\displaystyle 1+xx^{*}\leq x^{*}\qquad 1+x^{*}x\leq x^{*}$ $\displaystyle
y+xz\leq z\to x^{*}y\leq z\qquad y+zx\leq y\to yx^{*}\leq z$

A Kleene algebra is _∗ -continuous_ iff it satisfies

$xy^{*}z=\sum_{n\geq 0}xy^{n}z\,.$

######  Example 3.

(1) The Kleene algebra of binary relations on a non-empty set $X$ is

$\mathbf{Rel}_{X}=(\mathbf{2}^{X\times
X},\cup,\circ,\,^{*},\mathrm{id}_{X},\emptyset)\,,$

where $\mathbf{2}^{X\times X}$ is the set of all binary relations on $X$,
$\cup$ is union, $\circ$ is relational composition, $\,{}^{*}$ is reflexive
transitive closure, and $\mathrm{id}_{X}$ is the identity relation on $X$.

(2) Take a finite set of symbols $\Delta$ and let $\Delta^{*}$ be the set of
finite sequences over $\Delta$, including the empty sequence $\epsilon$. Let
$\mathrm{Reg}_{\Delta}$ be the smallest subset of $\mathbf{2}^{\Delta^{*}}$
(i.e. the set of all languages over $\Delta$) that contains the empty set
$\emptyset$, the set $\\{\epsilon\\}$, and $\\{\mathtt{x}\\}$ for all
$\mathtt{x}\in\Delta$ that is closed under finite unions and the following
operations:

  * •

$X\cdot Y=\\{xy\mid x\in X\And y\in Y\\}$, i.e. the set of concatenations of
strings from $X$ with strings from $Y$;

  * •

$X^{*}=\bigcup_{n\geq 0}X^{n}$, where $X^{0}=\\{\epsilon\\}$ and
$X^{n+1}=X^{n}\cdot X$, i.e. the set of all strings that can be parsed as
concatenations of a finite number of strings in $X$ (Kleene iteration).

The set $\mathrm{Reg}_{\Delta}$ is called the set of regular languages over
$\Delta$. The Kleene algebra of regular languages over $\Delta$ is

$\mathbf{Reg}_{\Delta}=(\mathrm{Reg}_{\Delta},\cup,\cdot,\,^{*},\\{\epsilon\\},\emptyset)\,.$

######  Definition 6.

A _Kleene algebra with tests_ [10] is a structure of the form

$\mathbf{K}=(K,B,\cdot,+,\,^{*},\,^{-},1,0)$

where

  * •

$(K,\cdot,+,\,^{*},1,0)$ is a Kleene algebra;

  * •

$B\subseteq K$, and $(B,\cdot,+,\,^{-},1,0)$ is a Boolean algebra.

A Kleene algebra with tests is ∗-continuous iff its underlying Kleene algebra
is ∗-continuous.

In a Kleene algebra with tests, elements of $B$ are seen as “tests” of
statements formulated in a Boolean language, while elements of $K$ in general
represent “structured actions”.

######  Example 4.

(1) Every Kleene algebra is a Kleene algebra with tests. Take $B=\\{1,0\\}$
and define $\,{}^{-}$ as Boolean complementation on $B$.

(2) A relational Kleene algebra with tests over some set $X$ is the expansion
of $\mathbf{Rel}_{X}$ with the set of subsets of $\mathrm{id}_{X}$ (seen as
$B$), and the complementation operation on the set of subsets of
$\mathrm{id}_{X}$ (seen as $\,{}^{-}$).

(3) Take two finite sets $\mathsf{A}$ and $\mathsf{T}$ of program and Boolean
variables, respectively. We assume that
$\mathsf{A}=\\{\mathtt{b}_{1},\ldots,\mathtt{b}_{n}\\}$ is ordered in some
fixed but arbitrary way. An _atom_ over $\mathsf{A}$ is a sequence
$\mathtt{b}_{1}^{\pm}\ldots\mathtt{b}_{n}^{\pm}$, where
$\mathtt{b}_{i}^{\pm}\in\\{\mathtt{b}_{i},\bar{\mathtt{b}}_{i}\\}$. Let
$1_{\mathsf{A}}$ be the set of all atoms over $\mathsf{A}$. A _guarded string_
over $\mathsf{A},\mathsf{T}$ is any sequence of the form (for $k\geq 0$)

$A_{0}p_{1}A_{1}p_{2}A_{2}\ldots p_{k}A_{k}$

where each $A_{i}$ is an atom over $\mathsf{A}$ and each $p_{i}\in\mathsf{T}$.
Guarded strings can be seen as representations of execution traces of programs
(abstract states are replaced by atoms). Let $2^{GS_{\mathsf{A},\mathsf{T}}}$
be the set of all sets of guarded strings over $\mathsf{A},\mathsf{T}$.
Obviously $1_{\mathsf{A}}\subseteq 2^{GS_{\mathsf{A},\mathsf{T}}}$. The
_coalesced product_ operation $\diamond$ is a partial binary function on
$GS_{\mathsf{A},\mathsf{T}}$ defined as follows:

$xA\diamond A^{\prime}y=\begin{cases}xAy&\text{if }A=A^{\prime}\\\
\text{undefined}&\text{otherwise}.\end{cases}$

The coalesced product operation is lifted to sets of guarded strings in an
obvious way. Note that the coalesced product operation on sets of guarded
strings is a total function. The _algebra of guarded languages_ over
$\mathsf{A},\mathsf{T}$ [11],

$\mathbf{G}_{\mathsf{A},\mathsf{T}}=(2^{GS_{\mathsf{A},\mathsf{T}}},2^{1_{\mathsf{A}}},\cup,\diamond,\,^{*},\,^{-},1_{\mathsf{A}},\emptyset)\,,$

is a ∗-continuous Kleene algebra with tests ($X^{*}=\bigcup_{n\geq 0}X^{n}$,
where exponentiation is defined using $\diamond$).

######  Lemma 1.

Let $X$ be a non-empty set and $\mathbf{S}$ a semiring. Then

  1. 1.

$\mathbf{S}(X)=(\mathbf{S}^{X\times X},\cdot,+,\mathbf{1},\mathbf{0})$ is a
semiring;

  2. 2.

if $\mathbf{S}$ is idempotent (complete), then $\mathbf{S}(X)$ is idempotent
(complete);

  3. 3.

if $\mathbf{S}$ is idempotent and complete, then
$\mathbf{S^{*}}(X)=(\mathbf{S}(X),\,^{*})$ is a ∗-continuous Kleene algebra;

  4. 4.

if $\mathbf{S}$ is idempotent and complete, then
$\mathbf{S^{*}_{2}}(X)=(\mathbf{S^{*}}(X),\mathbf{2}^{\mathrm{id}_{X}},\neg)$
is a ∗-continuous Kleene algebra with tests.

(We note that $\mathbf{S^{*}_{2}}(X)$ provides a natural example of a Kleene
algebra with tests where the set of tests, that is
$\mathbf{2}^{\mathrm{id}_{X}}$, is not identical to the set of elements under
$\mathbf{1}=\mathrm{id}_{X}$, where $\lambda\leq\lambda^{\prime}$ iff
$\lambda(s,t)\leq\lambda^{\prime}(s,t)$ for all $s,t\in X\times X$.)

######  Lemma 2.

The subalgebra of $\mathbf{S}(X)$ consisting of all constant functions is
isomorphic to $\mathbf{S}$.

##  V Kleene algebra with weights and tests

Given the applications of Kleene algebra in reasoning about regular and while
programs, it is natural to consider a Kleene-algebraic perspective on weighted
programs. Gomes et al. [6] formulate a generalization of KAT called _graded_
KAT (or GKAT) where the Boolean algebra of tests is replaced by a more general
algebraic structure. Batz et al. [3] point out that a deeper study of the
applicability of GKAT to reasoning about weighted programs is an interesting
problem to look at. Weighted programs in the sense of [3] combine Boolean
tests and weightings (weighted tests), and so it seems natural to consider a
generalization of the GKAT approach.

######  Definition 7.

A _Kleene algebra with weights and tests_ is a structure

$\mathbf{K}=(K,B,S,\cdot,+,\,^{*},\,^{-},1,0)$

where

  * •

$(K,\cdot,+,\,^{*},1,0)$ is a Kleene algebra;

  * •

$B\subseteq K$ and $S\subseteq K$;

  * •

$(B,\cdot,+,\,^{-},1,0)$ is a Boolean algebra;

  * •

$(S,\cdot,+,1,0)$ is a semiring.

A _valuation in $\mathbf{K}$_ is any homomorphism $v$ from
$\mathsf{WRP}_{\Sigma}$ to $\mathbf{K}$ such that $v(\mathtt{b})\in B$ and
$v(\mathtt{f})\in S$. Two programs $p,q\in\mathsf{WRP}_{\Sigma}$ are
_equivalent_ in a class $\mathcal{K}$ of Kleene algebras with weights and
tests iff $v(p)=v(q)$ for all valuations $v$ in all $\mathbf{K}\in\mathcal{K}$
.

Clearly each KAT is a KAWT; just take any subuniverse $S$ of $K$. However,
there are more interesting examples.

######  Example 5.

(1) Our first example combines a Kleene algebra of guarded languages with the
tropical semiring. Take the set of guarded strings over some fixed
$\mathsf{A}$ and $\mathsf{T}$, and denote it as $GS$. A function
$\lambda:GS\to\mathbb{N}^{\infty}$, assigning a weight to each guarded string,
can be seen as specifying the weights of execution traces of a program (if
$\lambda(s)=\infty$, then either $s$ is not a trace that can be generated by
the program corresponding to $\lambda$ or the trace carries an “absolute
weight”). Note that functions $\lambda:GS\to\mathbb{N}^{\infty}$ generalize
sets of guarded strings ($GS\to\\{0^{\mathbb{N}},\infty\\}$), i.e. elements of
the Kleene algebra $\mathbf{G}$. Take

$\mathbf{T^{G}}=((\mathbb{N}^{\infty})^{GS},B,S,\cdot,+,\,^{*},\,^{-},1,0)$

where $(\mathbb{N}^{\infty})^{GS}$ is the set of all functions from $GS$ to
$\mathbb{N}^{\infty}$ and

  * •

$1(s)=\begin{cases}0^{\mathbb{N}}&\text{if }s\in 1_{\mathsf{A}}\\\
\infty&\text{otherwise;}\end{cases}$

  * •

$0(s)=\infty$ for all $s$;

  * •

$\lambda\in B$ iff $\lambda(s)\in\\{0^{\mathbb{N}},\infty\\}$ for all $s\in
GT$ and $\lambda(s)=0^{\mathbb{N}}$ only if $s\in 1_{\mathsf{A}}$;

  * •

$S=\\{\lambda\mid\lambda(s)=\infty$ if $s\not\in 1_{\mathsf{A}}$ and
$\lambda(A_{i})=\lambda(A_{j})$ for all $A_{i},A_{j}\in 1_{\mathsf{A}}\\}$;

  * •

$(\lambda\cdot\lambda^{\prime})(s)=\mathrm{min}\\{\lambda(t)+^{\mathbb{N}^{\infty}}\lambda^{\prime}(u)\mid
s=t\diamond u\\}$;

  * •

$(\lambda+\lambda^{\prime})(s)=\mathrm{min}\\{\lambda(s),\lambda^{\prime}(s)\\}$;

  * •

$(\lambda^{*})(s)=\mathrm{min}_{n\geq 0}\big{(}\lambda^{n}(s)\big{)}$ where
$\lambda^{n}$ is defined using $\cdot\,;$

  * •

$\,{}^{-}:B\to B$ such that $(\bar{\lambda})(s)=\infty$ iff
$\lambda(s)\neq\infty$.

It can be shown that $\mathbf{T^{G}}$ is a (∗-continuous) Kleene algebra with
weights and tests where $(S,\cdot,+,1,0)\cong\mathbf{T}$. $\mathbf{T^{G}}$
also contains a (proper) subalgebra isomorphic to $\mathbf{G}$, namely,
$(\\{0^{\mathbb{N}},\infty\\}^{G},B,\cdot,+,\,^{*},\,^{-},1,0)$.

(2) A similar construction can be carried out using $\mathbf{T}$ and
$\mathbf{Rel}_{X}$. We leave the details to the reader, noting just that the
coalesced product operation $\diamond$ can be defined on $X\times X$ by
stipulating that $(s,t)\diamond(u,v)$ is $(s,v)$ if $t=u$ and is undefined
otherwise.

The construction encountered in the previous example can obviously be carried
out in a more general setting. In fact, we can use a slight generalization of
the well known notion of _formal power series_ coming up for instance in the
study of weighted automata [4, 12]. Formal power series are functions from a
monoid to a semiring; we will build on functions from certain partial
semigroups.

######  Definition 8.

A _partial semigroup with identity_ is $(G,D,\diamond,I)$ where
$G\neq\emptyset$, $D$ is a binary relation on $G$, $\diamond:D\to G$, and
$I\subseteq G$ such that

  * •

$D(x,y)\And D(x\diamond y,z)$ iff $D(y,z)\And D(x,y\diamond z)$;

  * •

$D(x,y)\And D(x\diamond y,z)$ only if $(x\diamond y)\diamond
z=x\diamond(y\diamond z)$;

  * •

for all $x$ there is $y$: $I(y)$ and $D(x,y)$;

  * •

for all $x$ there is $y$: $I(y)$ and $D(y,x)$;

  * •

$D(x,y)$ and $I(y)$ only if $x=x\diamond y$;

  * •

$D(y,x)$ and $I(y)$ only if $x=y\diamond x$.

We note that the first two conditions above are stronger than the standard
definition of a partial semigroup [7]. We’ll often write $xy$ instead of
$x\diamond y$.

######  Example 6.

(1) An example of a partial semigroup with identity is
$\mathbf{Cart}_{X}=(X\times X,D,\diamond,\mathrm{id}_{X})$ where $X\times X$
is the Cartesian product on a non-empty set $X$,
$((x_{1},y_{1}),(x_{2},y_{2}))\in D$ iff $y_{1}=x_{2}$,
$(x,y)\diamond(y,z)=(x,z)$, and $\mathrm{id}_{X}=\\{(x,x)\mid x\in X\\}$ is
the identity relation on $X$.

(2) $\mathbf{Gu}_{\mathsf{A,T}}=(GS,D,\diamond,1_{\mathsf{A}})$ where $GS$ is
the set of guarded strings over some $\mathsf{A}$ and $\mathsf{T}$, $\diamond$
is the coalesced product operation, $D$ is the set of pairs $(s,t)$ such that
$s\diamond t$ is defined, and $1_{\mathsf{A}}$ is the set of atoms over
$\mathsf{A}$.

(3) $\mathbf{Str}_{\Delta}=(\Delta^{*},D,\,^{\frown},\epsilon)$ where
$\Delta^{*}$ is the set of finite sequences (strings) over a finite alphabet
$\Delta$ (including the empty string $\epsilon$), $D$ is the universal
relation on $\Delta^{*}$ and $\,{}^{\frown}$ is the concatenation operation
(which is actually a total operation on $\Delta^{*}$).

Many well-known examples of Kleene algebras (with tests) are in fact algebras
of functions from specific (regular) partial semigroups to the two-element
Boolean semiring $\mathbf{Bo}=(\\{1,0\\},\land,\lor,1,0)$; the reader can
easily verify this by considering some of the previous examples.

######  Definition 9.

Let $\mathbf{P}=(G,D,\diamond,I)$ be a partial semigroup with identity, and
let
$\mathbf{S}=(S,\cdot^{\mathbf{S}},+^{\mathbf{S}},1^{\mathbf{S}},0^{\mathbf{S}})$
be a complete idempotent semiring. We define

$\mathbf{S^{P}}=(S^{G},B,W,\cdot,+,\,^{*},\,^{-},1,0)$

where $S^{G}$ is the set of all functions form $G$ to $S$ and

  * •

$1(x)=\begin{cases}1^{\mathbf{S}}&\text{if }x\in I\\\
0^{\mathbf{S}}&\text{otherwise;}\end{cases}$

  * •

$0(x)=0^{\mathbf{S}}$ for all $s$;

  * •

$\lambda\in B$ iff $\lambda(x)\in\\{1^{\mathbf{S}},0^{\mathbf{S}}\\}$ for all
$x\in G$ and $\lambda(x)=1^{\mathbf{S}}$ only if $x\in I$;

  * •

$W=\\{\lambda\mid\lambda(x)=0^{\mathbf{S}}$ if $x\not\in I$ and
$\lambda(y)=\lambda(z)$ for all $y,z\in I\\}$;

  * •

$(\lambda\cdot\lambda^{\prime})(x)=\sum\\{\lambda(y)\cdot^{\mathbf{S}}\lambda^{\prime}(z)\mid(y,z)\in
D\And y\diamond z=x\\}$ (the sum uses $+^{\mathbf{S}}$);

  * •

$(\lambda+\lambda^{\prime})(x)=\lambda(x)+^{\mathbf{S}}\lambda^{\prime}(x)$;

  * •

$(\lambda^{*})(x)=\sum_{n\geq 0}\big{(}\lambda^{n}(x)\big{)}$ where
$\lambda^{n}$ is defined using $\cdot\,;$

  * •

$\,{}^{-}:B\to B$ such that $(\bar{\lambda})(x)=1^{\mathbf{S}}$ iff
$\lambda(x)\neq 1^{\mathbf{S}}$.

######  Theorem 1.

If $\mathbf{P}$ is a partial semigroup with identity and $\mathbf{S}$ is a
complete idempotent semiring, then $\mathbf{S^{P}}$ is a ∗-continuous Kleene
algebra with weights and tests where

$(W,\cdot,+,1,0)\cong\mathbf{S}\,.$

Given the relation of Kleene algebra to the algebra of regular languages [9],
and the relation of Kleene algebra with tests to the algebra of regular
guarded languages [11], it is natural to ask if, for any given class of
semirings $\mathcal{S}$ (closed under isomorphisms) there is a Kleene algebra
with weights and tests whose elements are sets of strings over some alphabet
(a “language-theoretic” algebra, to use the terminology of [11]) which is free
in the class of Kleene algebras with weights and tests whose semiring of
weights belongs to $\mathcal{S}$. (That is, if the equational theory of the
given class of Kleene algebras with weights and tests is complete with respect
to a class language-theoretic algebras.)

We will not answer this question here, but we will note that $\mathbf{T^{G}}$
over any $\mathsf{A},\mathsf{T}$ (the algebra of functions from guarded
strings over $\mathsf{A},\mathsf{T}$ to extended natural numbers) is
isomorphic to a language-theoretic algebra.

Let $\Phi=(\mathsf{A},\mathsf{T})$ where $\mathsf{A}\subseteq\mathsf{B}$ is a
finite set of Boolean variables and $\mathsf{T}\subseteq\mathsf{P}$ is a
finite set of program variables. We assume that
$\mathsf{A}=\\{\mathtt{b}_{1},\ldots,\mathtt{b}_{n}\\}$ is ordered in some
fixed but arbitrary way. Let $\Box$ be a new symbol (i.e.
$\Box\notin\bigcup\Sigma$). A _weighted guarded string_ over $\Phi$ is a
string of the form

$A_{0}p_{1}A_{1}\ldots p_{n}A_{n}\Box^{m}\,,$

where all $A_{i}$ are atoms over $\mathsf{A}$ and all $p_{i}\in\mathsf{T}$.
That is, weighted guarded strings over $\Phi$ are a guarded strings over
$\Phi$ followed by a string of $m$ copies of $\Box$. We’ll write just $s(m)$,
where $s\in GS$ and $m\in\mathbb{N}$. A weighted atom is $s(m)$ where $s\in
1_{\mathsf{A}}$.

Intuitively, a guarded string represents an execution trace of a program and
the weight $\Box^{m}$ represents the weight of the trace. Hence, (some) sets
of weighted guarded strings can be seen as representing the possible execution
traces of weighted regular programs. If a set $X$ represents a program and
$s(m)\notin X$ for all $m$, then $s$ is not a possible execution trace of the
program, i.e. it has “infinite weight”.

A set $X$ of weighted guarded strings is _unambiguous_ iff $s(n)\in X$ and
$s(m)\in X$ only if $n=m$; moreover, $X$ is _crisp_ iff $s(m)\in X$ only if
$m=0$, and $X$ is _uniform_ only if $s(n),t(m)\in X$ only if $n=m$. A set $X$
of weighted atoms is _universal_ iff for all $A$ there is $n$ such that
$A(n)\in X$. Note that a crisp set of weighted guarded strings is just a set
of guarded strings, and that uniform sets are unambiguous.

The _unambiguous union_ of two sets of weighted guarded strings $X,Y$ is

$X\Cup Y:=\\{s(\mathrm{min}(U))\mid U=\\{n\mid s(n)\in X\cup Y\\}\\}\,.$

Note that $\Cup$ is not necessarily idempotent, but it is a semilattice join
operation on the set of all unambiguous sets of weighted guarded strings. We
denote $X\Cup X$ as $X^{\Cup}$.

Coalesced product of weighted guarded strings is defined as follows:

$xA(n)\diamond A^{\prime}y(m)=\begin{cases}xAy(n+m)&\text{if }A=A^{\prime}\\\
\text{undefined}&\text{otherwise.}\end{cases}$

######  Definition 10.

Fix a $\Phi$. Let

$\mathbf{GT}=(K,B,S,\,\cdot,\Cup,\,^{*},\,^{-},1_{\mathsf{A}},\emptyset)$

be an algebra such that:

  * •

$K$ is the set of all unambiguous sets of weighted guarded strings over
$\Phi$;

  * •

$B$ is the set of crisp sets of weighted atoms (i.e. the set of all sets of
atoms);

  * •

$S$ is the set of uniform universal sets of weighted atoms;

  * •

$X\cdot Y=(X\diamond Y)^{\Cup}$;

  * •

$X^{*}=\text{\Large{$\Cup$}}_{n\geq 0}X^{n}$ (where $X^{n}$ is defined using
$\cdot$);

  * •

$\,{}^{-}$ is complementation on $1_{\mathsf{A}}$.

(The ordinary lifting of $\diamond$ to sets of weighted guarded strings is not
necessarily an unambiguous set.)

######  Theorem 2.

$\mathbf{T^{G}}\cong\mathbf{GT}$.

######  Definition 11.

A valuation in $\mathbf{GT}$ is called _canonical_ iff

  * •

if $\mathtt{p}\in\mathsf{T}$, then $v(\mathtt{p})=\\{A\mathtt{\,p\,}B\mid
A,B\in 1_{\mathsf{A}}\\}$;

  * •

if $\mathtt{b}\in\mathsf{A}$, then $v(\mathtt{b})=\\{A\mid\neg\mathtt{b}\text{
does not occur in }A\\}$.

##  VI Using Kleene algebra to reason about weighted programs

Using the (quasi)equational theory of Kleene algebra with weights and tests,
we can reason about equivalence of weighted programs in a simple algebraic
setting.

######  Example 7.

Recall the ski rental program and Example 1. Using Kleene algebra (see [9],
Proposition 2.7), we can show that (1) is equivalent to

$\begin{gathered}(\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{one})^{*}\\\
\big{(}\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{skis}\,\texttt{end}\,(\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{one})^{*}\
\big{)}^{*}\\\ \\{\neg\texttt{neq0}\\}\end{gathered}$ (2)

Now consider the following equations:

$\displaystyle\texttt{sub1}^{n}\,\\{\texttt{neq0}\\}=\mathtt{0}$ (3)
$\displaystyle\texttt{end}\,\\{\texttt{neq0}\\}=\mathtt{0}$ (4)

Both correspond to reasonable assumptions in the version of the ski rental
scenario where the length of the trip in $n$ days, given the intended
interpretation of the variables occurring in the equations: if you do subtract
$1$ from $n$ $n$-times, then the test $n>0$ evaluates to False (3); and if you
assign $n:=0$, then then the test $n>0$ evaluates to False (4).

Let us define $\gamma^{+n}:=1+\gamma+\gamma^{2}+\ldots+\gamma^{n}$. It is
possible to show that, in each ∗-continuous KAWT where (3) and (4) hold, and
where $1$ is the top element of $S$ (such as algebras where $S$ is isomorphic
to the tropical semiring, for example), the program (2) is equivalent to

$\begin{gathered}(\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{one})^{+n}\\\
\big{(}\mathtt{1}+\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{skis}\,\texttt{end}\big{)}\\{\neg\texttt{neq0}\\}\end{gathered}$
(5)

Hence, it is possible to show using Kleene algebra with weights and tests
that, on each input $n$, the program (2) is equivalent to a simpler program
(5) that does not involve ∗. Hence, in a sense, (5) is _finite_.

######  Example 8.

Take $\mathbf{GT}$ over $\Phi=(\mathsf{A},\mathsf{T})$ where
$\mathsf{A}=\\{\\{\texttt{neq0}\\},\\{\neg\texttt{neq0}\\}\\}$ and
$\mathsf{T}=\\{\texttt{sub1},\texttt{end}\\}$. Take any canonical valuation
where $v(\texttt{one})=\\{A(1)\mid A\in
1_{\mathsf{A}}\\}=\\{\\{\texttt{neq0}\\}\Box,\\{\neg\texttt{neq0}\\}\Box\\}$
and $v(\texttt{skis})=\\{A(y)\mid A\in
1_{\mathsf{A}}\\}=\\{\\{\texttt{neq0}\\}\Box^{y},\\{\neg\texttt{neq0}\\}\Box^{y}\\}\\}$.
Then $v$ maps the program (5) to the set $X$ of weighted guarded strings
containing:

$\displaystyle\\{\neg\texttt{neq0}\\}\big{(}0\big{)},\quad\\{\texttt{neq0}\\}\texttt{sub1}\\{\texttt{neq0}\\}\texttt{end}\\{\neg\texttt{neq0}\\}\big{(}y\big{)}\,,$
$\displaystyle\\{\texttt{neq0}\\}\texttt{sub1}\\{\neg\texttt{neq0}\\}\texttt{end}\\{\neg\texttt{neq0}\\}\big{(}y\big{)}\,,$
$\displaystyle\\{\texttt{neq0}\\}\texttt{sub1}\\{\neg\texttt{neq0}\\}\big{(}1\big{)}\,,$
$\displaystyle\\{\texttt{neq0}\\}\texttt{sub1}\\{\texttt{neq0}\\}\texttt{sub1}\\{\texttt{neq0}\\}\texttt{end}\\{\neg\texttt{neq0}\\}\big{(}1+y\big{)}\,,$
$\displaystyle\\{\texttt{neq0}\\}\texttt{sub1}\\{\texttt{neq0}\\}\texttt{sub1}\\{\neg\texttt{neq0}\\}\texttt{end}\\{\neg\texttt{neq0}\\}\big{(}1+y\big{)}\,,$
$\displaystyle{\small\vdots}$
$\displaystyle\Big{(}\\{\texttt{neq0}\\}\texttt{sub1}\Big{)}^{n}\\{\neg\texttt{neq0}\\}\big{(}n\big{)}\,,$
$\displaystyle\Big{(}\\{\texttt{neq0}\\}\texttt{sub1}\Big{)}^{n}\\{\texttt{neq0}\\}\texttt{sub1}\\{\texttt{neq0}\\}\texttt{end}\\{\neg\texttt{neq0}\\}\big{(}n+y\big{)}\,,$
$\displaystyle\Big{(}\\{\texttt{neq0}\\}\texttt{sub1}\Big{)}^{n}\\{\texttt{neq0}\\}\texttt{sub1}\\{\neg\texttt{neq0}\\}\texttt{end}\\{\neg\texttt{neq0}\\}\big{(}n+y\big{)}$

Every set $G$ of weighted guarded strings in $\mathbf{GT}$ gives a function
$\vartheta_{G}$ from $1_{\mathsf{A}}$ to the set of sets of weighted atoms
defined by

$\vartheta_{G}(Y)=\\{A(n)\mid\exists x(xA(n)\in Y\diamond G)\\}^{\Cup}\,.$

Hence, $\vartheta_{G}(Y)$ is the set weighted atoms representing the _optimal_
execution traces from $G$ starting in an atom in $Y$. If $G$ is finite, then
$\vartheta_{G}$ is obviously computable.

For example,
$\vartheta_{X}(\\{\neg\texttt{neq0}\\})=\\{\\{\neg\texttt{neq0}\\}\\}$ (if the
ski rental program is run in a state where $n=0$, then it halts immediately
without accumulating any weight), and

$\vartheta_{X}(\\{\texttt{neq0}\\})=\\{\\{\neg\texttt{neq0}\\}\big{(}\mathrm{min}(n,y)\big{)}\\}\,.$

That is, an optimal run of (5) from a state where $n\neq 0$ will have weight
$\mathrm{min}(n,y)$. This result agrees with intuition and the calculation in
[3] using the weakest preweighting operator.

##  VII Conclusion

We introduced Kleene algebra with weights and tests, an expansion of Kleene
algebra with tests suitable for formalizing reasoning about a simplified
version of weighted programs discussed in [3]. We described constructions of
some “concrete” KAWT, and we demonstrated by means of an example that KAWT can
be used for reasoning about equivalence and optimal runs of weighted programs.

Many interesting topics need to be left to future research, including a study
of free Kleene algebras with weights and tests, questions of decidability and
computational complexity, and a systematic accommodation of the weakest
preweighting operator of [3] into our framework.

## References

  * [1] K. R. Apt, F. S. de Boer, and E.-R. Olderog.  Verification of Sequential and Concurrent Programs.  Texts in Computer Science. Springer, 3rd edition, 2009.
  * [2] G. Barthe, J.-P. Katoen, and A. Silva.  Foundations of Probabilistic Programming.  Cambridge University Press, 2020.
  * [3] K. Batz, A. Gallus, B. L. Kaminski, J.-P. Katoen, and T. Winkler.  Weighted programming: A programming paradigm for specifying mathematical models.  Proc. ACM Program. Lang., 6(OOPSLA1), apr 2022.
  * [4] M. Droste, W. Kuich, and H. Vogler, editors.  Handbook of Weighted Automata.  Springer, 2009.
  * [5] M. J. Fischer and R. E. Ladner.  Propositional dynamic logic of regular programs.  J. Comput. Syst. Sci., 18:194–211, 1979.
  * [6] L. Gomes, A. Madeira, and L. S. Barbosa.  Generalising KAT to verify weighted computations.  Sci. Annals Comput. Sci., 29(2):141–184, 2019.
  * [7] S. P. Gudder and R. H. Schelp.  Coordinatization of orthocomplemented and orthomodular posets.  Proc. Am. Math. Soc., 25(2):229–237, 1970.
  * [8] D. Kozen.  On Kleene algebras and closed semirings.  In B. Rovan, editor, Int. Symp. on Mathematical Foundations of Comp. Sci., pages 26–47. Springer, 1990.
  * [9] D. Kozen.  A completeness theorem for Kleene algebras and the algebra of regular events.  Inf. Comput., 110(2):366 – 390, 1994.
  * [10] D. Kozen.  Kleene algebra with tests.  ACM Trans. Program. Lang. Syst., 19(3):427–443, May 1997.
  * [11] D. Kozen and F. Smith.  Kleene algebra with tests: Completeness and decidability.  In D. van Dalen and M. Bezem, editors, Computer Science Logic, pages 244–259, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg.
  * [12] W. Kuich and A. Salomaa.  Semirings, Automata, Languages.  EATCS Monographs on Theoretical Computer Science 5. Springer, 1986.
  * [13] V. Pratt.  Semantical considerations on Floyd-Hoare logic.  In 7th Annual Symp. on Foundations of Comp. Sci., pages 109–121. IEEE Computing Society, 1976.

This appendix contains proofs of some of the technical results stated in the
main text, and a lemma that will be used in the proof of Theorem 1.

######  Lemma 3.

The following hold in each partial semigroup with identity:

  1. 1.

$I(x)$ only if $D(x,x)$ and $x=xx$;

  2. 2.

$I(x)$, $I(y)$ and $D(x,y)$ only if $I(xy)$.

###### Proof.

1) For all $x$ there is $y$ such that $D(x,y)$ and $I(y)$. Then $x=xy$. But if
also $I(x)$, then $y=xy$. Hence, $x=y$ and so $D(x,x)$ and $x=xx$.

2) If $D(x,y)$ and $I(y)$, then $x=xy$. If also $I(x)$, then $I(xy)$. ∎

Theorem 1. If $\mathbf{P}$ is a partial semigroup with identity and
$\mathbf{S}$ is a complete idempotent semiring, then $\mathbf{S^{P}}$ is a
∗-continuous Kleene algebra with weights and tests where

$(W,\cdot,+,1,0)\cong\mathbf{S}\,.$

Proof. $(S^{G},+,0)$ is clearly a commutative monoid. $(S^{G},\cdot,1)$ is a
monoid:

  * (i)

$(\lambda_{0}\cdot(\lambda_{1}\cdot\lambda_{2}))(x)=\sum_{y,u}\Big{\\{}\lambda_{0}(y)\cdot^{\mathbf{S}}\sum_{z,w}\big{\\{}\lambda_{1}(z)\cdot\lambda_{2}(w)\mid
u=zw\And D(z,w)\big{\\}}\>\big{|}\>x=yu\And D(y,u)\Big{\\}}=$
$=\sum_{y,z,w}\big{\\{}\lambda_{0}(y)\cdot^{\mathbf{S}}\big{(}\lambda_{1}(z)\cdot^{\mathbf{S}}\lambda_{2}(w)\big{)}\mid
D(y,zw)\And D(z,w)\And x=y(zw)\big{\\}}$
$=\sum_{y,z,w}\big{\\{}\big{(}\lambda_{0}(y)\cdot^{\mathbf{S}}\lambda_{1}(z)\big{)}\cdot^{\mathbf{S}}\lambda_{2}(w)\mid
D(y,zw)\And D(z,w)\And x=y(zw)\big{\\}}$
$=\sum_{y,z,w}\big{\\{}\big{(}\lambda_{0}(y)\cdot^{\mathbf{S}}\lambda_{1}(z)\big{)}\cdot^{\mathbf{S}}\lambda_{2}(w)\mid
D(y,z)\And D(yz,w)\And x=(yz)w\big{\\}}$
$=\sum_{y,z,v,w}\Big{\\{}\sum\big{\\{}\lambda_{0}(y)\cdot^{\mathbf{S}}\lambda_{1}(z)\>\big{|}\>v=yz\And
D(y,z)\big{\\}}\cdot^{\mathbf{S}}\lambda_{2}(w)\>\big{|}\>D(v,w)\And
x=vw\Big{\\}}$
$=((\lambda_{0}\cdot\lambda_{1})\cdot\lambda_{2})(x)$.

  * (ii)

$(\lambda\cdot 1)(x)=\sum_{y,z}\\{\lambda(y)\cdot^{\mathbf{S}}1(z)\mid
D(y,z)\And x=yz\\}$
$=\sum_{y,z}\\{\lambda(y)\mid D(y,z)\And x=yz\And I(z)\\}$
$=\sum_{y}\\{\lambda(y)\mid x=y\\}=\lambda(x)$.

  * ($(1\cdot\lambda)(x)=\lambda(x)$ is established similarly.)

The fourth equality in (i) follows from the definition of a partial semigroup
with identity (the first two conditions).222We note that the equality cannot
be established using the weaker definition of a partial semigroup of [7];
hence our strengthening.The third equality in (ii) is established using the
definition of a partial semigroup with identity as follows. Left to right: If
$D(y,z)$ and $I(z)$, then $yz=y$; so if also $x=yz$, then $x=y$. Right to
left: for all $y$ there is $z$ such that $D(y,z)$ and $I(z)$, which means that
there is $z$ such that $D(y,z)$ and $I(z)$ and $yz=y$. Hence, if $x=y$, then
there is $z$ such that $D(y,z)$, $I(z)$ and $x=yz$.

Next we show that $\cdot$ distributes over $+$:

  * (iii)

$\big{(}\lambda_{0}\cdot(\lambda_{1}+\lambda_{2})\big{)}(x)$
$=\sum_{y,z}\big{\\{}\lambda_{0}(y)\cdot^{\mathbf{S}}(\lambda_{1}+\lambda_{2})(z)\>\big{|}\>D(y,z)\And
x=yz\big{\\}}$
$=\sum_{y,z}\big{\\{}\lambda_{0}(y)\cdot^{\mathbf{S}}(\lambda_{1}(z)+^{\mathbf{S}}\lambda_{2}(z))\>\big{|}\>D(y,z)\And
x=yz\big{\\}}$
$=\sum_{y,z}\big{\\{}\big{(}\lambda_{0}(y)\cdot^{\mathbf{S}}\lambda_{1}(z)\big{)}+^{\mathbf{S}}\big{(}\lambda_{0}(y)\cdot^{\mathbf{S}}\lambda_{2}(z)\big{)}\>\big{|}\>D(y,z)\And
x=yz\big{\\}}$
$=\sum_{y,z}\\{\lambda_{0}(y)\cdot^{\mathbf{S}}\lambda_{1}(z)\mid D(y,z)\And
x=yz\\}+^{\mathbf{S}}$
$\sum_{y,z}\\{\lambda_{0}(y)\cdot^{\mathbf{S}}\lambda_{2}(z)\mid D(y,z)\And
x=yz\\}$
$=(\lambda_{0}\cdot\lambda_{1})(x)+^{\mathbf{S}}(\lambda_{0}\cdot\lambda_{2})(x)$
$=\big{(}(\lambda_{0}\cdot\lambda_{1})+(\lambda_{0}\cdot\lambda_{2})\big{)}(x)$

  * ($\big{(}(\lambda_{0}+\lambda_{1})\cdot\lambda_{2}\big{)}(x)=\big{(}(\lambda_{0}\cdot\lambda_{2})+(\lambda_{1}\cdot\lambda_{2})\big{)}(x)$ is established similarly.)

To prove that $0$ is the annihilator element it is sufficient to show that
$(\lambda\cdot 0)(x)=0^{\mathbf{S}}=(0\cdot\lambda)(x)$ for all $x\in G$:

  * (iv)

$(\lambda\cdot 0)(x)=\sum_{y,z}\\{\lambda(y)\cdot^{\mathbf{S}}0(z)\mid
D(y,z)\And x=yz\\}$
$=0^{\mathbf{S}}=$
$\sum_{y,z}\\{0(y)\cdot^{\mathbf{S}}\lambda(z)\mid D(y,z)\And
x=yz\\}=(0\cdot\lambda)(x)$.

This proves that $\mathbf{S^{P}}$ is an idempotent semiring. To prove that it
is also a ∗-continuous Kleene algebra, it is sufficient to show that it
satisfies the ∗-continuity condition:

$\delta\lambda^{*}\theta=\sum_{n\geq 0}\delta\lambda^{n}\theta$ (6)

for all $\delta,\lambda,\theta\in S^{G}$. It is an easy exercise to show that
the Kleene star (quasi)equations follow from ∗-continuity. We reason as
follows:

$\displaystyle(\delta\lambda^{*}\theta)(x)=\sum_{y,z}\Big{\\{}\delta(y)\cdot^{\mathbf{S}}(\lambda^{*}\theta)(z)\>\big{|}\>D(y,z)\And
yz=x\Big{\\}}$
$\displaystyle=\sum_{y,z,u,v}\Big{\\{}\delta(y)\cdot^{\mathbf{S}}\big{(}\lambda^{*}(u)\cdot^{\mathbf{S}}\theta(v)\big{)}\>\big{|}\>$
$\displaystyle D(y,z)\And yz=x\And D(u,v)\And uv=z\Big{\\}}$
$\displaystyle=\sum_{y,z,u,v}\Big{\\{}\delta(y)\cdot^{\mathbf{S}}\Big{(}\big{(}\sum_{n\geq
0}\lambda^{n}(u)\big{)}\cdot^{\mathbf{S}}\theta(v)\Big{)}\>\big{|}\>$
$\displaystyle D(y,z)\And yz=x\And D(u,v)\And uv=z\Big{\\}}$
$\displaystyle=\sum_{n\geq
0}\sum_{y,z,u,v}\Big{\\{}\delta(y)\cdot^{\mathbf{S}}\Big{(}\lambda^{n}(u)\cdot^{\mathbf{S}}\theta(v)\Big{)}\>\big{|}\>$
$\displaystyle D(y,z)\And yz=x\And D(u,v)\And uv=z\Big{\\}}$
$\displaystyle=\sum_{n\geq
0}\sum_{y,z,u,v}\Big{\\{}\Big{(}\delta(y)\cdot^{\mathbf{S}}\lambda^{n}(u)\Big{)}\cdot^{\mathbf{S}}\theta(v)\>\big{|}\>$
$\displaystyle D(y,u)\And yu=w\And D(w,v)\And wv=x\Big{\\}}$
$\displaystyle=\sum_{n\geq
0}\sum_{w,v}\Big{\\{}\big{(}\delta\lambda^{n}\big{)}(w)\cdot^{\mathbf{S}}\theta(v)\>\big{|}\>D(w,v)\And
wv=x\Big{\\}}$ $\displaystyle=\sum_{n\geq
0}\Big{\\{}\big{(}\delta\lambda^{n}\theta\big{)}(x)\Big{\\}}=\Big{(}\sum_{n\geq
0}\delta\lambda^{n}\theta\Big{)}(x)$

The fourth equality holds since $\mathbf{S}$ is a complete semiring. The fifth
equality holds thanks to the definition of a partial semigroup with identity
(first two conditions).

Hence, $\mathbf{S^{P}}$ is a ∗-continuous Kleene algebra. To show that it is a
∗-continuous Kleene algebra with tests, we have to show that $B$ is a Boolean
algebra and $\,{}^{-}$ is complementation on $B$. But this follows easily from
the definition: $B$ can be equivalently seen as the power set of $I$ (hence
clearly a Boolean algebra), and $\,{}^{-}$ is obviously defined as
complementation on $B$.

In order to show that $\mathbf{S^{P}}$ is a Kleene algebra with weights and
tests, we have to show that $W$ is closed under the semiring operations
$\cdot$ and $+$, and that $0,1\in W$. $W$ is the set of functions that assign
$0^{\mathbf{S}}$ to elements outside $I$, and that are constant on $I$. Let us
denote the set of such functions as $C$. Both $1$ and $0$ are in $C$, and $C$
is clearly closed under $+$. To show that $C$ is are closed under $\cdot$ as
well, we reason as follows. Assume that $\lambda,\lambda^{\prime}\in C$. First
we prove that if $x\in I$, then

$(\lambda\cdot\lambda^{\prime})(x)=\lambda(x)\cdot^{\mathbf{S}}\lambda^{\prime}(x)$
(7)

Indeed,

$\displaystyle\sum_{y,z}\big{\\{}\lambda(y)\cdot^{\mathbf{S}}\lambda^{\prime}(z)\mid
D(y,z)\And x=yz\big{\\}}$
$\displaystyle=\lambda(x)\cdot^{\mathbf{S}}\lambda^{\prime}(x)$

since

$\displaystyle\sum_{y,z}\big{\\{}\lambda(y)\cdot^{\mathbf{S}}\lambda^{\prime}(z)\mid
D(y,z)\And x=yz\big{\\}}$
$\displaystyle=\sum_{y,z}\big{\\{}\lambda(y)\cdot^{\mathbf{S}}\lambda^{\prime}(z)\mid
D(y,z)\And x=yz\And I(y)\And I(z)\big{\\}}$

(we may forget about $y,z\not\in I$ since $\lambda,\lambda^{\prime}$ map them
to $0^{\mathbf{S}}$) and

$\displaystyle\sum_{y,z}\big{\\{}\lambda(y)\cdot^{\mathbf{S}}\lambda^{\prime}(z)\mid
D(y,z)\And x=yz\And I(y)\And I(z)\big{\\}}$
$\displaystyle=\lambda(x)\cdot^{\mathbf{S}}\lambda^{\prime}(x)\,.$

The latter holds since the set over which the sum is formed contains at least
$\lambda(x)\cdot^{\mathbf{S}}\lambda^{\prime}(x)$ (Lemma 3, part 1) and it
contains at most $\lambda(x)\cdot^{\mathbf{S}}\lambda^{\prime}(x)$ since
$\lambda,\lambda^{\prime}$ are constant on $I$. It follows from (7) that
$\lambda\cdot\lambda^{\prime}$ is constant on $I$ since both $\lambda$ and
$\lambda^{\prime}$ are constant on $I$.

Second, we show that $(\lambda\cdot\lambda^{\prime})(x)=0^{\mathbf{S}}$ if
$x\notin I$. This follows from Lemma 3, part 2: if $x\not\in I$, then $x=yz$
and $D(y,z)$ only if $y\notin I$ or $z\notin I$. Hence, if $x\notin I$, then
$(\lambda\cdot^{\mathbf{S}}\lambda^{\prime})(x)=0^{\mathbf{S}}$. Hence,
$(\lambda\cdot\lambda^{\prime})\in C$ if $\lambda,\lambda^{\prime}\in C$.

It remains to establish that $(W,\cdot,+,1,0)$ is isomorphic to $\mathbf{S}$.
Fix and arbitrary $i\in I$ (note that $I\neq\emptyset$ in all partial
semigroups with identity) and define $\phi:W\to\mathbf{S}$:

$\phi(\lambda)=\lambda(i)$

The mapping $\phi$ is a bijective homomorphism. Homomorphism:
$\phi(1)=1(i)=1^{\mathbf{S}}$; $\phi(0)=0(i)=0^{\mathbf{S}}$;
$\phi(\lambda+\lambda^{\prime})=(\lambda+\lambda^{\prime})(i)=\lambda(i)+^{\mathbf{S}}\lambda^{\prime}(i)=\phi(\lambda)+^{\mathbf{S}}\phi(\lambda^{\prime})$;
$\phi(\lambda\cdot\lambda^{\prime})=(\lambda\cdot\lambda^{\prime})(i)=\lambda(i)\cdot^{\mathbf{S}}\lambda^{\prime}(i)$
by (7) $=\phi(\lambda)\cdot^{\mathbf{S}}\phi(\lambda^{\prime})$. Surjective:
$W$ is the set of _all_ functions that are constant on $I$ and assign
$0^{\mathbf{S}}$ to elements $x\notin I$. Injective: if
$\phi(\lambda)=\phi(\lambda^{\prime})$, then $\lambda(i)=\lambda^{\prime}(i)$,
and then $\lambda=\lambda^{\prime}$ since $\lambda$ and $\lambda^{\prime}$ are
assumed constant on $I$. ∎

Theorem 2. $\mathbf{T^{G}}\cong\mathbf{GT}$.

Proof. Define $\tau:(\mathbb{N}^{\infty})^{GS}\to K^{\mathbf{GT}}$ such that

$\tau(\lambda)=\\{s(n)\mid\lambda(s)=n\And n\neq\infty\\}\,.$

The function $\tau$ is clearly a bijection between
$(\mathbb{N}^{\infty})^{GS}$ and $K^{\mathbf{GT}}$. Moreover,

  * (i)

$B^{\mathbf{GT}}=\\{\tau(\lambda)\mid\lambda\in B\\}$ since $\lambda\in B$ iff
$\lambda:GT\to\\{0^{\mathbb{N}},\infty\\}$ and $\lambda(s)=0^{\mathbb{N}}$
only if $s\in 1_{\mathsf{A}}$ iff $\tau(\lambda)$ is a crisp set of weighted
atoms;

  * (ii)

$S^{\mathbf{GT}}=\\{\tau(\lambda)\mid\lambda\in S\\}$ since $\lambda\in S$ iff
$\lambda(s)=\infty$ for $s\notin 1_{\mathsf{A}}$ and $\lambda$ is constant on
$1_{\mathsf{A}}$ iff $\tau(\lambda)$ is an uniform set of weighted atoms.

Next we need to show that $\tau$ is a homomorphism:

  * (iii)

$\tau(1)=\\{s(0)\mid s\in 1_{\mathsf{A}}\\}=1^{\mathbf{GT}}$;

  * (iv)

$\tau(0)=\emptyset=0^{\mathbf{GT}}$;

  * (v)

$s(n)\in\tau(\lambda\cdot\lambda^{\prime})$ $\iff$
$(\lambda\cdot\lambda^{\prime})(s)=n\neq\infty$
$\iff$ $n\neq\infty$ and
$n=\mathrm{min}\\{\lambda(t)+^{\mathbb{N}^{\infty}}\lambda^{\prime}(u)\\}$ for
$t,u\in GS$ such that $t\diamond u=s$
$\iff$ $\exists t,u\in GS:s=t\diamond u$ and
$n=\lambda(t)+^{\mathbb{N}^{\infty}}\lambda^{\prime}(u)$ and
$\lambda(t)\neq\infty$ and $\lambda^{\prime}(u)\neq\infty$ and
$\forall t^{\prime},u^{\prime}\in GS(s=t^{\prime}\diamond u^{\prime}\to
n\leq^{\mathbb{N}^{\infty}}\lambda(t^{\prime})+\lambda^{\prime}(u^{\prime}))$
$\iff$ $s(n)\in\tau(\lambda)\diamond\tau(\lambda^{\prime})$ and
$\forall t^{\prime},u^{\prime}\in GS(s=t^{\prime}\diamond u^{\prime}\to
n\leq^{\mathbb{N}^{\infty}}\lambda(t^{\prime})+\lambda^{\prime}(u^{\prime}))$
$\iff$ $s(n)\in\tau(\lambda)\cdot^{\mathbf{GT}}\tau(\lambda^{\prime})$;

  * (vi)

$s(n)\in\tau(\lambda+\lambda^{\prime})$ $\iff$
$(\lambda+\lambda^{\prime})(s)=n\neq\infty$
$\iff$ $n=\mathrm{min}\\{\lambda(s),\lambda^{\prime}(s)\\}$ and $n\neq\infty$
$\iff$ $s(n)\in\tau(\lambda)\cup\tau(\lambda^{\prime})$ and
$\forall m\in\mathbb{N}(s(m)\in\tau(\lambda)\cup\tau(\lambda^{\prime})\to
n\leq^{\mathbb{N}^{\infty}}m)$
$\iff$ $s(n)\in\tau(\lambda)\Cup\tau(\lambda^{\prime})$

  * (vii)

$s(n)\in\tau(\lambda^{*})$ $\iff$
$n=\mathrm{min}_{m\in\mathbb{N}}\\{\lambda^{m}(s)\\}$
$\iff$ $\exists
m\in\mathbb{N}:n=\underbrace{(\lambda\cdot\ldots\cdot\lambda)}_{m\text{-times}}(s)$
and
$\forall
k\big{(}n\leq^{\mathbf{\mathbb{N}}}\underbrace{(\lambda\cdot\ldots\cdot\lambda)}_{k\text{-times}}(s)\big{)}$
$\iff$ $s(n)\in\bigcup_{m\in\mathbb{N}}\tau(\lambda)^{m}$ and
$n=\mathrm{min}\big{\\{}n^{\prime}\>\big{|}\>s(n^{\prime})\in\bigcup_{k\in\mathbb{N}}\tau(\lambda)^{k}\big{\\}}$
$\iff$
$s(n)\in\Big{(}\bigcup_{m\in\mathbb{N}}\tau(\lambda)^{m}\Big{)}^{\Cup}=\text{\Large{$\Cup$}}_{m\in\mathbb{N}}\tau(\lambda)^{m}$
$\iff$ $s(n)\in\big{(}\tau(\lambda)\big{)}^{*^{\mathbf{GT}}}$;

  * (viii)

for $\lambda\in B$: $s(0^{\mathbb{N}})\in\tau(\overline{\lambda})$
$\iff$ $\overline{\lambda}(s)=0^{\mathbb{N}}$ $\iff$ $\lambda(s)=\infty$
$\iff$ $s(0^{\mathbb{N}})\notin\tau(\lambda)$ $\iff$
$s(0^{\mathbb{N}})\in\overline{\tau(\lambda)}$.

∎

Note that we didn’t need to assume in the proof that
$\mathbf{GT}\in\mathsf{KAWT}$, but this follows from Theorem 2.

Example 7. If $\mathbf{K}\in\mathsf{KAWT}$ such that (3) and (4) holds in
$\mathbf{K}$, and $\mathtt{1}$ is the top element of $S^{\mathbf{K}}$, then
(2) is equivalent to (5).

Proof. By ∗-continuity and (4),

$\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{skis}\,\texttt{end}\,(\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{one})^{*}$

is equivalent to

$\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{skis}\,\texttt{end}$

and so the second line of (2) is equivalent to

$\mathtt{1}+\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{skis}\,\texttt{end}\,.$

By ∗-continuity,

$(\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{one})^{*}$

is equivalent to

$\sum_{n\geq
0}\big{(}\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{one}\big{)}^{n}$ (8)

However, since $\\{\texttt{neq0}\\},\texttt{one}\leq\mathtt{1}$,

$\big{(}\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{one}\big{)}^{n+1}$

is less or equal to

$\texttt{sub1}^{n}\big{(}\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{one}\big{)}\,,$

which equals $\mathtt{0}$ by (3). Hence, (8) is equivalent to

$\big{(}\\{\texttt{neq0}\\}\,\texttt{sub1}\,\texttt{one}\big{)}^{+n}\,.$

∎


Manuscript

# A characterization of the relative entropies

Eszter Gselmann  Department of Analysis
Institute of Mathematics
University of Debrecen
P. O. Box: 12.
Debrecen
H–4010
Hungary<EMAIL_ADDRESS>and  Gyula Maksa  Department of Analysis
Institute of Mathematics
University of Debrecen
P. O. Box: 12.
Debrecen
H–4010
Hungary<EMAIL_ADDRESS>Dedicated to Professor Antal Járai on his sixtieth
birthday

###### Abstract.

In this note we give a characterization of a family of relative entropies on
open domain depending on a real parameter $\alpha$ based on recursivity and
symmetry. In the cases $\alpha=1$ and $\alpha=0$ we use additionally a weak
regularity assumption while in the other cases no regularity assumptions are
made at all.

###### Key words and phrases:

Shannon relative entropy, Tsallis relative entropy, relative information
measure.

###### 1991 Mathematics Subject Classification:

94A17, 39B82, 39B72

This research has been supported by the Hungarian Scientific Research Fund
(OTKA) grants NK 68040 and K 62316.

##  1\. Introduction and preliminaries

Throughout this paper $\mathbb{N}$, $\mathbb{R}$, and $\mathbb{R}_{+}$ will
denote the sets of all positive integers, real numbers, and positive real
numbers, respectively. For all $2\leq n\in\mathbb{N}$ let

$\Gamma_{n}^{\circ}=\left\\{(p_{1},\ldots,p_{n})\in\mathbb{R}^{n}|p_{i}\in\mathbb{R}_{+},i=1,\ldots,n,\sum_{i=1}^{n}p_{i}=1\right\\}$

and

$\Gamma_{n}=\left\\{(p_{1},\ldots,p_{n})\in\mathbb{R}^{n}|p_{i}\geq
0,i=1,\ldots,n,\sum_{i=1}^{n}p_{i}=1\right\\}.$

Furthermore, for a fixed $\alpha\in\mathbb{R},$ define the function
$D_{n}^{\alpha}(\cdot|\cdot):\Gamma_{n}^{\circ}\times\Gamma_{n}^{\circ}\rightarrow\mathbb{R}$
by

(1.1)
$D_{n}^{\alpha}(p_{1},\ldots,p_{n}|q_{1},\ldots,q_{n})=-\sum_{i=1}^{n}p_{i}\ln_{\alpha}\left(\frac{q_{i}}{p_{i}}\right)$

where

$\mathrm{ln}_{\alpha}(x)=\left\\{\begin{array}[]{lcl}\frac{x^{1-\alpha}-1}{1-\alpha},&\text{if}&\alpha\neq
1\\\ \ln(x),&\text{if}&\alpha=1.\end{array}\right.$

The sequence $(D_{n}^{\alpha})$ is called the Shannon relative entropy (or
Kullback-Leibler entropy or Kullback’s directed divergence) if $\alpha=1$, and
the Tsallis relative entropy if $\alpha\neq 1$, respectively. $(D_{n}^{1})$ is
introduced and extensively discussed in Kullback [12] and Aczél–Daróczy [2],
respectively. For $0\leq\alpha\neq 1$, $(D_{n}^{\alpha})$ was introduced and
discussed in Shiino [15], Tsallis [17], and Rajagopal–Abe [14] from physical
point of view, and in Furuichi–Yanagi–Kuriyama [8] and Furuichi [7] from
mathematical point of view, respectively. In [7] and also in Hobson [9],
several fundamental properties of $(D_{n}^{\alpha})$ are listed and it is
proved that some of them together determine $(D_{n}^{\alpha})$, up to a
constant factor.

In this note, we follow the method of the basic references [2] and
Ebanks–Sahoo–Sander [6] of investigating characterization problems of
information measures. We prove a characterization theorem similar to that of
[9] and [7], and we point out that the regularity conditions (say, continuity)
can be avoided if $\alpha\notin\\{0,1\\}$, and can essentially be weakened if
$\alpha\in\\{0,1\\}$.

In what follows, a sequence $(I_{n})$ of real-valued functions $I_{n},(n\geq
2)$ on $\Gamma_{n}^{\circ}\times\Gamma_{n}^{\circ}$ or on
$\Gamma_{n}\times\Gamma_{n}$ is called a _relative information measure_ on the
open or closed domain, respectively. Our characterization theorem for the
Shannon and the Tsallis relative entropies will be based on the following two
properties.

######  Definition 1.1.

Let $\alpha\in\mathbb{R}$. The relative information measure $(I_{n})$ is
_$\alpha$ –recursive_ on the open or closed domain, if for any $n\geq 3$ and
$(p_{1},\ldots,p_{n}),(q_{1},\ldots,q_{n})\in\Gamma_{n}^{\circ}$ or
$\Gamma_{n}$, respectively, the identity

$I_{n}\left(p_{1},\ldots,p_{n}|q_{1},\ldots,q_{n}\right)\\\
=I_{n-1}\left(p_{1}+p_{2},p_{3},\ldots,p_{n}|q_{1}+q_{2},q_{3},\ldots,q_{n}\right)\\\
+(p_{1}+p_{2})^{\alpha}(q_{1}+q_{2})^{1-\alpha}I_{2}\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{p_{2}}{p_{1}+p_{2}}|\frac{q_{1}}{q_{1}+q_{2}},\frac{q_{2}}{q_{1}+q_{2}}\right)$

holds. We say that $(I_{n})$ is _3-semisymmetric_ on the open or closed
domain, if

$I_{3}\left(p_{1},p_{2},p_{3}|q_{1},q_{2},q_{3}\right)=I_{3}\left(p_{1},p_{3},p_{2}|q_{1},q_{3},q_{2}\right)$

is fulfilled for all
$(p_{1},p_{2},p_{3}),(q_{1},q_{2},q_{3})\in\Gamma_{3}^{\circ}\,\,\text{or}\,\,\Gamma_{3}$,
respectively.

The following lemma shows how the initial element of an $\alpha$–recursive
relative information measure $(I_{n})$ determines $(I_{n})$ itself.

######  Lemma 1.2.

Let $\alpha\in\mathbb{R}$ and assume that the relative information measure
$(I_{n})$ is $\alpha$–recursive on the open domain and define the function
$f:]0,1[^{2}\to\mathbb{R}$ by

$f(x,y)=I_{2}(1-x,x|1-y,y).\qquad(x,y\in]0,1[)$

Then, for all $n\geq 3$ and for arbitrary,
$(p_{1},\ldots,p_{n}),(q_{1},\ldots,q_{n})\in\Gamma_{n}^{\circ}$

$I_{n}(p_{1},\ldots,p_{n}|q_{1},\ldots,q_{n})\\\
=\sum_{i=2}^{n}(p_{1}+p_{2}+\ldots+p_{i})^{\alpha}(q_{1}+q_{2}+\ldots+q_{i})^{1-\alpha}f\left(\frac{p_{i}}{p_{1}+p_{2}+\ldots+p_{i}},\frac{q_{i}}{q_{1}+q_{2}+\ldots+q_{i}}\right)$

holds.

###### Proof.

The proof runs by induction on $n$. If we use the $\alpha$–recursivity of
$(I_{n})$ and the definition of the function $f$, we obtain that

$I_{3}(p_{1},p_{2},p_{3}|q_{1},q_{2},q_{3})\\\
=I_{2}(p_{1}+p_{2},p_{3}|q_{1}+q_{2},q_{3})+(p_{1}+p_{2})^{\alpha}(q_{1}+q_{2})^{1-\alpha}I_{2}\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{p_{2}}{p_{1}+p_{2}}\bigg{|}\frac{q_{1}}{q_{1}+q_{2}},\frac{q_{2}}{q_{1}+q_{2}}\right)\\\
=\sum_{i=2}^{3}(p_{1}+\ldots+p_{i})^{\alpha}(q_{1}+\ldots+q_{i})^{1-\alpha}f\left(\frac{p_{i}}{p_{1}+\ldots
p_{i}},\frac{q_{i}}{q_{1}+\ldots+q_{i}}\right)$

is fulfilled for all
$(p_{1},p_{2},p_{3}),(q_{1},q_{2},q_{3})\in\Gamma^{\circ}_{3}$, that is, the
statement is true for $n=3$. Assume now that the statement holds for some
$3<n\in\mathbb{N}$. We will prove that in this case the proposition holds also
for $n+1$. Let
$(p_{1},\ldots,p_{n+1}),(q_{1},\ldots,q_{n+1})\in\Gamma_{n}^{\circ}$ be
arbitrary. Then, the $\alpha$–recursivity and the induction hypothesis
together imply that

$I_{n+1}(p_{1},\ldots,p_{n+1}|q_{1},\ldots,q_{n+1})\\\
=I_{n}(p_{1}+p_{2},\ldots,p_{n+1}|q_{1}+q_{2},\ldots,q_{n+1})+(p_{1}+p_{2})^{\alpha}(q_{1}+q_{2})^{1-\alpha}I_{2}\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{p_{2}}{p_{1}+p_{2}}\bigg{|}\frac{q_{1}}{q_{1}+q_{2}},\frac{q_{2}}{q_{1}+q_{2}}\right)\\\
=\sum_{n=3}^{n+1}((p_{1}+p_{2})+p_{3}\ldots+p_{i})^{\alpha}((q_{1}+q_{2})+p_{3}+\ldots+q_{i})^{1-\alpha}f\left(\frac{p_{i}}{(p_{1}+p_{2})+\ldots+p_{i}},\frac{q_{i}}{(q_{1}+q_{2})+\ldots+q_{i}}\right)\\\
+(p_{1}+p_{2})^{\alpha}(q_{1}+q_{2})^{1-\alpha}I_{2}\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{p_{2}}{p_{1}+p_{2}}\bigg{|}\frac{q_{1}}{q_{1}+q_{2}},\frac{q_{2}}{q_{1}+q_{2}}\right)\\\
=\sum_{i=2}^{n+1}(p_{1}+p_{2}+\ldots+p_{i})^{\alpha}(q_{1}+q_{2}+\ldots+q_{i})^{1-\alpha}f\left(\frac{p_{i}}{p_{1}+p_{2}+\ldots+p_{i}},\frac{q_{i}}{q_{1}+q_{2}+\ldots+q_{i}}\right),$

that is, the statement holds for $n+1$ instead of $n$, which ends the proof. ∎

##  2\. The characterization

We begin with the following

######  Theorem 2.1.

For any $\alpha\in\mathbb{R}$ the relative entropy $(D_{n}^{\alpha})$ is an
$\alpha$–recursive relative information measure.

###### Proof.

In the proof, we will use several times the identities

$\displaystyle\ln_{\alpha}(xy)$ $\displaystyle=$
$\displaystyle\ln_{\alpha}(x)+\ln_{\alpha}(y)+(1-\alpha)\ln_{\alpha}(x)\ln_{\alpha}(y)$
$\displaystyle\ln_{\alpha}\left(\frac{1}{x}\right)$ $\displaystyle=$
$\displaystyle-x^{\alpha-1}\ln_{\alpha}(x).$

which hold for all $\alpha\in\mathbb{R}$ and $x,y\in\mathbb{R}_{+}$. Let
$n\geq 3$ and $(p_{1},\ldots,p_{n}),(q_{1},\ldots,q_{n})\in\Gamma_{n}^{\circ}$
be arbitrary. Then

$(p_{1}+p_{2})^{\alpha}(q_{1}+q_{2})^{1-\alpha}D_{2}\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{p_{2}}{p_{1}+p_{2}}\bigg{|}\frac{q_{1}}{q_{1}+q_{2}},\frac{q_{2}}{q_{1}+q_{2}}\right)\\\
=(p_{1}+p_{2})^{\alpha}(q_{1}+q_{2})^{1-\alpha}\left(-\frac{p_{1}}{p_{1}+p_{2}}\ln_{\alpha}\left(\frac{p_{1}+p_{2}}{q_{1}+p_{2}}\frac{q_{1}}{p_{1}}\right)-\frac{p_{2}}{p_{1}+p_{2}}\ln_{\alpha}\left(\frac{p_{1}+p_{2}}{q_{1}+q_{2}}\frac{q_{2}}{p_{2}}\right)\right)\\\
=(p_{1}+p_{2})^{\alpha}(q_{1}+q_{2})^{1-\alpha}\left(-\ln_{\alpha}\left(\frac{p_{1}+p_{2}}{q_{1}+q_{2}}\right)+\left(1+(1-\alpha)\ln_{\alpha}\left(\frac{p_{1}+p_{2}}{q_{1}+q_{2}}\right)\right)\right.\times\\\
\times\left.\left(-\frac{p_{1}}{p_{1}+p_{2}}\ln_{\alpha}\left(\frac{q_{1}}{p_{1}}\right)-\frac{p_{2}}{p_{1}+p_{2}}\ln_{\alpha}\left(\frac{q_{2}}{p_{2}}\right)\right)\right)\\\
=(p_{1}+p_{2})\ln_{\alpha}\left(\frac{q_{1}+q_{2}}{p_{1}+p_{2}}\right)+\left[\left(\frac{q_{1}+q_{2}}{p_{1}+p_{2}}\right)^{1-\alpha}-(1-\alpha)\ln_{\alpha}\left(\frac{q_{1}+q_{2}}{p_{1}+p_{2}}\right)\right]\left[-p_{1}\ln_{\alpha}\frac{q_{1}}{p_{1}}-p_{2}\ln_{\alpha}\frac{q_{2}}{p_{2}}\right]\\\
=(p_{1}+p_{2})\ln_{\alpha}\left(\frac{q_{1}+q_{2}}{p_{1}+p_{2}}\right)-p_{1}\ln_{\alpha}\left(\frac{q_{1}}{p_{1}}\right)-p_{2}\ln_{\alpha}\left(\frac{q_{2}}{p_{2}}\right)\\\
=D_{n}(p_{1},\ldots,p_{n}|q_{1},\ldots,q_{n})-D_{n-1}(p_{1}+p_{2},\ldots,p_{n}|q_{1}+q_{2}+\ldots,q_{n}).$

Therefore the relative entropy $(D_{n}^{\alpha})$ is $\alpha$–recursive,
indeed. ∎

Obviously $(D_{n}^{\alpha})$ is 3-semisymmetric, and for arbitrary
$\gamma\in\mathbb{R},\,\,$ $(\gamma D_{n}^{\alpha})$ is $\alpha$–recursive and
3-semisymmetric, as well. Before dealing with the converse we need two lemmas
about _logarithmic_ functions. A function $\ell:\mathbb{R}_{+}\to\mathbb{R}$
is logarithmic if $\ell(xy)=\ell(x)+\ell(y)$ for all $x,y\in\mathbb{R}_{+}.$
If a logarithmic function $\ell$ is bounded above or below on a set of
positive Lebesgue measure then $\ell(x)=c\ln(x)$ for all $x\in\mathbb{R}_{+}$
with some $c\in\mathbb{R}$ (see [11], Theorem 5 and Theorem 8 on pages 311,
312). The concept of _real derivation_ will also be needed. The function
$d:\mathbb{R}\to\mathbb{R}$ is a real derivation if it is both _additive_ ,
i.e. $d(x+y)=d(x)+d(y)$ for all $x,y\in\mathbb{R}$, and satisfies the
functional equation $d(xy)=xd(y)+yd(x)$ for all $x,y\in\mathbb{R}$. It is
somewhat surprising that there are non-identically zero real derivations (see
[11], Theorem 2 on page 352). If $d$ is a real derivation then the function
$x\mapsto\frac{d(x)}{x},x\in\mathbb{R}_{+}$ is logarithmic. Therefore it is
easy to see that the real derivation is identically zero if it is bounded
above or below on a set of positive Lebesgue measure.

######  Lemma 2.2.

Suppose that the logarithmic function $\ell:\mathbb{R}_{+}\to\mathbb{R}$
satisfies the equality

(2.1) $x\ell(x)+(1-x)\ell(1-x)=0.\qquad(x\in]0,1[)$

Then there exists a real derivation $d:\mathbb{R}\to\mathbb{R}$ such that

(2.2) $x\ell(x)=d(x).\qquad(x\in\mathbb{R}_{+})$

###### Proof.

Let $x,y\in\mathbb{R}_{+}.$ Then, by (2.1) and by using the properties of the
logarithmic function, we have that

$0=\frac{x}{x+y}\ell\left(\frac{x}{x+y}\right)+\frac{y}{x+y}\ell\left(\frac{y}{x+y}\right)\\\
=\frac{x}{x+y}\left(\ell(x)-\ell(x+y)\right)+\frac{y}{x+y}\left(\ell(y)-\ell(x+y)\right)\\\
=\frac{1}{x+y}\left(x\ell(x)+y\ell(y)-(x+y)\ell(x+y)\right).$

This shows that the function $x\mapsto x\ell(x),x\in\mathbb{R}_{+}$ is
additive on $\mathbb{R}_{+}$. Hence, by the well-known extension theorem (see
e.g. [11], Theorem 1 on page 471), there exists an additive function
$d:\mathbb{R}\to\mathbb{R}$ such that (2.2) holds. Since $\ell$ is
logarithmic, this implies that $d(xy)=xd(y)+yd(x)$ holds for all
$x,y\in\mathbb{R}_{+}$. On the other hand, $d$ is odd thus this equation holds
also for all $x,y\in\mathbb{R}$, that is, $d$ is a real derivation. ∎

######  Lemma 2.3.

Suppose that $\ell:\mathbb{R}_{+}\to\mathbb{R}$ is a logarithmic function and
the function $g_{0}$ defined on the interval $]0,1[$ by

$g_{0}(x)=x\ell(x)+(1-x)\ell(1-x)$

is bounded on a set of positive Lebesque measure. Then there exist a real
number $\beta$ and a real derivation $d:\mathbb{R}\to\mathbb{R}$ such that

(2.3) $x\ell(x)+\beta x\ln(x)=d(x).\qquad(x\in\mathbb{R}_{+})$

###### Proof.

Define the function $g$ on the interval $[0,1]$ by $g(0)=g(1)=0$ and, for
$x\in]0,1[$, by

$g(x)=-\frac{g_{0}(x)}{\ell(2)}\,\,\text{if}\,\,\ell(2)\neq
0\,\,\text{and}\,\,g(x)=g_{0}(x)-x\log_{2}(x)-(1-x)\log_{2}(1-x)\,\,\text{if}\,\,\ell(2)=0.$

Then $g$ is a symmetric information function (see [2], (3.5.33) Theorem on
page 100) which, by our assumption, is bounded on a set of positive Lebesque
measure. Therefore, applying a theorem of Diderrich [5], we obtain that

$g(x)=-x\log_{2}(x)-(1-x)\log_{2}(1-x).\qquad(x\in]0,1[)$

For a short proof of Diderrich’s theorem see also [13] in which an idea of
Járai [10] proved to be very efficient. Taking into consideration the
definition of $g$ and applying Lemma 2.2, we get (2.3) with suitable
$\beta\in\mathbb{R}$. ∎

Now we are ready to prove our main result.

######  Theorem 2.4.

Let $\alpha\in\mathbb{R},\,\,(I_{n})$ be an $\alpha$-recursive and
$3$-semisymmetric relative information measure on the open domain, and
$f(x,y)=I_{2}(1-x,x|1-y,y),\,\,x,y\in]0,1[$. Furthermore, suppose that

(2.4) $I_{2}(p_{1},p_{2}|p_{1},p_{2})=0.\qquad((p_{1},p_{2})\in\Gamma_{2})$

If $\alpha\notin\\{0,1\\}$ then $(I_{n})=(\gamma D_{n}^{\alpha})$ for some
$\gamma\in\mathbb{R}$.
If $\alpha=1$ and there exists a point $(u,v)\in]0,1[^{2}$ such that the
function $f(\cdot,v)$ is bounded on a set of positive Lebesgue measure and the
function $f(u,\cdot)$ is bounded above or below on a set of positive Lebesgue
measure then $(I_{n})=(\gamma D_{n}^{1})$ for some $\gamma\in\mathbb{R}$.
And finally, if $\alpha=0$ and there exists a point $(u,v)\in]0,1[^{2}$ such
that the function $f(\cdot,v)$ is bounded above or below on a set of positive
Lebesgue measure and the function $f(u,\cdot)$ is bounded on a set of positive
Lebesgue measure then $(I_{n})=(\gamma D_{n}^{0})$ for some
$\gamma\in\mathbb{R}$.

###### Proof.

Applying Theorem 4.2.3. on page 87 of [6] with
$M(x,y)=x^{\alpha}y^{1-\alpha},\,\,x,y\in\mathbb{R}_{+}$ and taking into
consideration Lemma 1.2.12. on page 16 of [6], (see also [1]), we have that

(2.5)
$I_{n}\left(p_{1},\ldots,p_{n}|q_{1},\ldots,q_{n}\right)=bp_{1}^{\alpha}q_{1}^{1-\alpha}+c\sum_{i=2}^{n}p_{i}^{\alpha}q_{i}^{1-\alpha}-b$

in case $\alpha\notin\\{0,1\\}$,

(2.6)
$I_{n}\left(p_{1},\ldots,p_{n}|q_{1},\ldots,q_{n}\right)=\sum_{i=1}^{n}p_{i}(\ell_{1}(p_{i})+\ell_{2}(q_{i}))+c(1-p_{1})$

in case $\alpha=1$, and

(2.7)
$I_{n}\left(p_{1},\ldots,p_{n}|q_{1},\ldots,q_{n}\right)=\sum_{i=1}^{n}q_{i}(\ell_{1}(p_{i})+\ell_{2}(q_{i}))+c(1-q_{1})$

in case $\alpha=0$ for all $n\geq
2,(p_{1},\ldots,p_{n}),(q_{1},\ldots,q_{n})\in\Gamma_{n}^{\circ}$ with some
$b,c\in\mathbb{R}$ and logarithmic functions
$\ell_{1},\ell_{2}:\mathbb{R}_{+}\to\mathbb{R}$.

Now we utilize our further conditions on $(I_{n})$. In case
$\alpha\notin\\{0,1\\}$, (2.5) with $n=2$ and (2.4) imply that
$0=bp_{1}+cp_{2}-b$ for all $(p_{1},p_{2})\in\Gamma_{2}$ whence $b=c$ follows.
Thus, by (2.5), we obtain that $(I_{n})=(\gamma D_{n}^{\alpha})$ with
$\gamma=(\alpha-1)^{-1}$. In case $\alpha=1$, (2.6) with $n=2$ and (2.4) imply
that

$0=p_{1}\ell(p_{1})+p_{2}\ell(p_{2})+c(1-p_{1}).\qquad((p_{1},p_{2})\in\Gamma_{2})$

where $\ell=\ell_{1}+\ell_{2}$. Therefore $c=0$, and, by Lemma 2.2, we get
that $x\ell_{2}(x)=-x\ell_{1}(x)+d_{1}(x)$ for all $x\in\mathbb{R}_{+}$ and
for some real derivation $d_{1}:\mathbb{R}\to\mathbb{R}$. Thus

$f(x,y)=x\ell_{1}\left(\frac{x}{y}\right)+(1-x)\ell_{1}\left(\frac{1-x}{1-y}\right)+\left(\frac{x}{y}-\frac{1-x}{1-y}\right)d_{1}(y).\qquad(x,y\in]0,1[)$

Since the function $f(\cdot,v)$ is bounded on a set of positive Lebesque
measure, we get that the function $x\mapsto
x\ell_{1}(x)+(1-x)\ell_{1}(1-x),\,x\in]0,1[$ has the same property. Thus, by
Lemma 2.3,

$x\ell_{1}(x)+\beta x\ln(x)=d_{2}(x),\qquad(x\in\mathbb{R}_{+})$

for some $\beta\in\mathbb{R}$ and derivation $d_{2}:\mathbb{R}\to\mathbb{R}$.
Hence

$f(x,y)=-\beta
x\ln\left(\frac{x}{y}\right)-\beta(1-x)\ln\left(\frac{1-x}{1-y}\right)-\left(\frac{x}{y}-\frac{1-x}{1-y}\right)(d_{2}(y)-d_{1}(y)).\qquad(x,y\in]0,1[)$

However, $f(u,\cdot)$ is bounded above or below on a set of positive Lebesgue
measure for some $u\in]0,1[$ thus the derivation $d_{2}-d_{1}$ has the same
property, so $d_{2}-d_{1}=0$. Therefore

$f(x,y)=-\beta
x\ln\left(\frac{x}{y}\right)-\beta(1-x)\ln\left(\frac{1-x}{1-y}\right)\qquad(x,y\in]0,1[)$

and the statement follows from Lemma 1.2 with a suitable
$\gamma\in\mathbb{R}$. The case $\alpha=0$ can be handled similarly by
interchanging the role of the distributions $(p_{1},\ldots,p_{n})$ and
$(q_{1},\ldots,q_{n})$ and of the logarithmic functions $\ell_{1}$ and
$\ell_{2},$ respectively. ∎

##  3\. Connections to known characterizations

In this section we will point out some connections between our
characterization theorem and other statements. Here we deal especially with
the results of Hobson [9] and Furuichi [7]. They considered the relative
information measure on the closed domain. In this case, however the
expressions $\frac{0}{0+0},\frac{0}{0+\ldots+0},0^{\alpha},0^{1-\alpha}$ can
appear. Therefore, in the remaining part of the paper the conventions
$\frac{0}{0+0}=\frac{0}{0+\ldots+0}=0^{\alpha}=0^{1-\alpha}=0$ are always
adapted (see also [3]).

We begin with several definitions.

######  Definition 3.1.

The relative information measure $(I_{n})$ on the closed domain is said to be
_expansible_ , if

$I_{n+1}\left(p_{1},\ldots,p_{n},0|q_{1},\ldots,q_{n},0\right)=I_{n}\left(p_{1},\ldots,p_{n}|q_{1},\ldots,q_{n}\right)$

is satisfied for all $n\geq 2$ and
$(p_{1},\ldots,p_{n}),(q_{1},\ldots,q_{n})\in\Gamma_{n}$.
The relative information measure is called _decisive_ , if

$I_{2}(1,0|1,0)=0$

holds.
Let $\alpha\in\mathbb{R}$ be arbitrarily fixed, we say that the relative
information measure $(I_{n})$ satisfies the _generalized additivity_ , if for
all $n,m\geq 2$ and for arbitrary
$(p_{1,1},\ldots,p_{1,m},\ldots,\ldots,p_{n,1},\ldots,p_{n,m}),\allowbreak(q_{1,1},\ldots,q_{1,m},\ldots,\ldots,q_{n,1},\ldots,q_{n,m})\in\Gamma_{nm}$
(or $\Gamma_{nm}^{\circ}$)

$I_{nm}\left(p_{1,1},\ldots,p_{1,m},\ldots,\ldots,p_{n,1},\ldots,p_{n,m}|q_{1,1},\ldots,q_{1,m},\ldots,\ldots,q_{n,1},\ldots,q_{n,m}\right)\\\
=I_{n}(P_{1},\ldots,P_{n}|Q_{1},\ldots
Q_{n})+\sum_{i=1}^{n}P_{i}^{\alpha}Q_{i}^{1-\alpha}I_{m}\left(\frac{p_{i,1}}{P_{i}},\ldots,\frac{p_{i,m}}{P_{i}}|\frac{q_{i,1}}{Q_{i}},\ldots,\frac{q_{i,m}}{Q_{i}}\right)$

is fulfilled, where $P_{i}=\sum_{j=1}^{m}p_{i,j}$ and
$Q_{i}=\sum_{j=1}^{m}q_{i,j}$, $i=1,\ldots,n$.

A lengthy but simple calculation shows that the relative information measure
$(D_{n}^{\alpha})$ fulfills all of the above listed criteria. As well as
Hobson [9] and Furuichi [7], we would like to investigate the converse
direction. More precisely, the question is whether the generalized additivity
property determines $(D_{n}^{\alpha})$ up to a multiplicative constant. In
general this is not true. Since let us observe that in case we consider the
generalized additivity on the open domain $\Gamma_{n}^{\circ}$ then this
property is insignificant for $I_{n}$ if $n$ is a prime. Nevertheless, on the
closed domain this property is well–treatable. In this case we can prove the
following.

######  Lemma 3.2.

If the relative information measure $(I_{n})$ on the closed domain is
expansible and satisfies the general additivity property with a certain
$\alpha\in\mathbb{R}$, then it is also decisive and $\alpha$–recursive.

###### Proof.

Firstly, we will show, that the generalized additivity and the expansibility
implies that the relative information measure $(I_{n})$ is decisive. Indeed,
if we use the generalized additivity with the choice $n=m=2$ and
$(p_{1},p_{2},p_{3},p_{4})=(q_{1},q_{2},q_{3},q_{4})=(1,0,0,0)$, then we get
that

$I_{4}(1,0,0,0|1,0,0,0)=I_{2}(1,0|1,0)+I_{2}(1,0)$

holds. On the other hand, $(I_{n})$ is expansible, therefore
$I_{4}(1,0,0,0|1,0,0,0)=I_{2}(1,0|1,0)$. Thus $I_{2}(1,0|1,0)=0$ follows, so
$(I_{n})$ is decisive.

Now we will prove the $\alpha$–recursivity of $(I_{n})$. Let
$(r_{1},\ldots,r_{n}),(s_{1},\ldots,s_{n})\in\Gamma_{n}$ and use the
generalized additivity with the following substitution

$p_{1,1}=r_{1},\quad p_{1,2}=r_{2},\quad p_{i,1}=r_{i+1},i=2,\ldots,n-1,\quad
p_{i,j}=0\quad\text{otherwise}$

and

$q_{1,1}=s_{1},\quad q_{1,2}=s_{2},\quad q_{i,1}=s_{i+1},i=2,\ldots,n-1,\quad
q_{i,j}=0\quad\text{otherwise}$

to derive

$I_{nm}(r_{1},r_{2},0,\ldots,0,r_{3},0,\ldots,0,r_{n},0,\ldots,0|s_{1},s_{2},0,\ldots,0,s_{3},0,\ldots,0,s_{n},0,\ldots,0)\\\
=I_{n}(r_{1}+r_{2},r_{3},\ldots,r_{n},0|s_{1}+s_{2},s_{3},\ldots,s_{n},0)\\\
+(r_{1}+r_{2})^{\alpha}(s_{1}+s_{2})^{1-\alpha}I_{2}\left(\frac{r_{1}}{r_{1}+r_{2}},\frac{r_{2}}{r_{1}+r_{2}}\bigg{|}\frac{s_{1}}{s_{1}+s_{2}},\frac{s_{2}}{s_{1}+s_{2}}\right)\\\
+\sum_{j=3}^{n}r_{j}^{\alpha}q_{j}^{1-\alpha}I_{m}(1,0,\ldots,0|1,0,\ldots,0).$

After using that $(I_{n})$ is expansible and decisive, we obtain the
$\alpha$–recursivity. ∎

In view of Theorem 2.4. and Lemma 3.2. the following characterization theorem
follows easily.

######  Theorem 3.3.

Let $\alpha\in\mathbb{R},\,\,(I_{n})$ be an expansible and $3$-semisymmetric
relative information measure which also satisfies the generalized additivity
property on $\Gamma_{n}$ with the parameter $\alpha$ and let
$f(x,y)=I_{2}(1-x,x|1-y,y),\,\,x,y\in]0,1[$. Additionally, suppose that

(3.1) $I_{2}(p_{1},p_{2}|p_{1},p_{2})=0.\qquad((p_{1},p_{2})\in\Gamma_{2})$

If $\alpha\notin\\{0,1\\}$ then $(I_{n})=(\gamma D_{n}^{\alpha})$ for some
$\gamma\in\mathbb{R}$.
If $\alpha=1$ and there exists a point $(u,v)\in]0,1[^{2}$ such that the
function $f(\cdot,v)$ is bounded on a set of positive Lebesgue measure and the
function $f(u,\cdot)$ is bounded above or below on a set of positive Lebesgue
measure then $(I_{n})=(\gamma D_{n}^{1})$ for some $\gamma\in\mathbb{R}$.
And finally, if $\alpha=0$ and there exists a point $(u,v)\in]0,1[^{2}$ such
that the function $f(\cdot,v)$ is bounded above or below on a set of positive
Lebesgue measure and the function $f(u,\cdot)$ is bounded on a set of positive
Lebesgue measure then $(I_{n})=(\gamma D_{n}^{0})$ for some
$\gamma\in\mathbb{R}$.

Finally, we remark that the essence of Theorems 2.4. and 3.3. is that, in case
$\alpha\notin\left\\{0,1\right\\}$, the algebraic properties listed in
Theorems 2.4. and 3.3., respectively, determine the information measure
$(D_{n}^{\alpha})$ up to a multiplicative constant _without any regularity
assumption_. Moreover, if $\alpha\in\left\\{0,1\right\\}$, then the mentioned
algebraic properties with a really mild regularity condition determine
$(D_{n}^{\alpha})$ up to a multiplicative constant.

## References

  * [1] J. Aczél, _26\. Remark. Solution of Problem 17 (1)_ , Proceedings of the $18^{th}$ International Symposium on Functional Equations, University of Waterloo, Centre for Information Theory, Faculty of Mathematics, Waterloo, Ontario, Canada, N2L 3G1, 1981, 14–15.
  * [2] J. Aczél, Z. Daróczy, _On measures of information and their characterizations_ , Mathematics in Science and Engineering, vol. 115., Academic Press, New York–London, 1975\.
  * [3] J. Aczél, Pl. Kannappan, _General two-place information functions_ , Resultate der Mathematik, 5 (1982), 99–106.
  * [4] Z. Daróczy, _Generalized information functions_ , Information and Control, 16 (1970), 36–51.
  * [5] G.T. Diderrich, _Boundedness on a set of positive measure and th fundamental equation of information_ , Publ. Math. Debrecen, 33 (1986), 1–7.
  * [6] B. Ebanks, P. Sahoo, W. Sander, _Characterizations of information measures_ , World Scientific Publishing Co., Inc., River Edge, NJ, 1998.
  * [7] S. Furuichi, _On uniqueness theorems for Tsallis entropy and Tsallis relative entropy_ , IEEE Trans. Inform. Theory 51 (2005), No. 10, 3638–3645.
  * [8] S. Furuichi, K. Yanagi, K. Kuriyama, _Fundamental propertis of Tsallis relative entropy_ , J. Math. Psys, 45 (2004), No. 12, 4868–4877.
  * [9] A. Hobson, _A new theorem of information theory_ , J. Statist. Phys. 1 (1969), 383–391.
  * [10] A. Járai, _Remark P1179S1_ , Aequationes Math., 19 (1979), 286–288.
  * [11] M. Kuczma, _An Introduction to the Theory of Functional Equations and Inequalities_ , Prace Naukowe Uniwersytetu Śla̧skiego w Katowicach, vol. 489., Państwowe Wydawnictwo Naukowe — Uniwersytet Śla̧ski, Warszawa–Kraków–Katowice, 1985\.
  * [12] J. Kullback, _Information theory and Statistics_ , New York: Wiley–London: Chapman and Hall, 1959\.
  * [13] Gy. Maksa, _Bounded symmetric information functions_ , C.R. Math. Rep. Acad. Sci. Canada, 2 (1980), No. 5, 247–252.
  * [14] A.K. Rajagopal, S. Abe, _Implications of form invariance to the structure of nonextensive entropies_ , Psys. Rev. Lett., 83 (1999) 1711–1714.
  * [15] M. Shiino, _H-theorem with generalized relative entropies and the Tsallis statistics_ , J. Phys. Soc. Japan, 67 (1998), 3658–3660.
  * [16] C. Tsallis, _Possible generalization of Boltzmann-Gibbs statistics_ , J. Statist. Phys., 52 (1988), no. 1-2, 479–487.
  * [17] C. Tsallis, _Generalized entropy-based criterion for consistent testing_ , Phys. Rev. E., 58 (1998), 1442–1445.