Namespaces
Variants
Actions

Assignement

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

2020 Mathematics Subject Classification: Primary: 68P05 [MSN][ZBL]

An assignement is used for assigning specific values $a_1,\ldots,a_n$ to the free variables $X_1,\ldots,X_n\in V(t)$ of a term $t\in T(\Sigma,X)$ belonging to a signature $\Sigma=(S,F)$ and a set $X$ of variables. These values $a_1,\ldots,a_n$ are elements of a $\Sigma$-algebra $A$, whereby the sorts of $a_i$ and $X_i$ coincide in each case (i.e. $a_i\in s^A_i$ for $X_i\in X_{s_i}$ with $s_i\in S$). In this way, variables contained in the term $t$ can be eliminated and the overall 'value' of $t$ concretized. Formally, an assignement is a mapping $v\colon X\longrightarrow \bigcup_{s\in S} s^A$ with $v(x)\in s^A$ for $x\in X_s$, $s\in S$ [EM85]. The set of all assignements is typically designated as $B(A,X)$. An assignement is also called valuation.

For an assignement $v\in B(A,X)$ and for a value $a\in s^A$ the assignement changed at $x$ to $a$, designated as $v[x\leftarrow a]$, is defined as $$v[x\leftarrow a](y) := \begin{cases} a & \mathrm{ if~} y=x\\ v(y) & \mathrm{ otherwise } \end{cases}$$

It is possible, of course, to use specifically a term algebra $T(\Sigma,Y)$ with an $S$-sorted set $Y$ of variables as $\Sigma$-algebra $A$. In this case, assignements are called substitutions of terms in $T(\Sigma,Y)$ for variables. The value of a term $t\in T(\Sigma,X)$ under a substitution $B(T(\Sigma,Y),X)\ni v \colon X \longrightarrow T(\Sigma,Y)$, written $t[v]$, is just the result of substituting $v(x)$ for all occurences of $x$ in $t$ in the usual sense. For a simple substitution $$v(y) := \begin{cases} u & \mathrm{ if~} y=x\\ y & \mathrm{ otherwise } \end{cases}$$ replacing $x$ by $u\in T(\Sigma,Y)$ in $t\in T(\Sigma,X)$ one often writes $t[x \leftarrow u]$ instead of $t[v]$ [ST99].

References

[EM85] H. Ehrig, B. Mahr: "Fundamentals of Algebraic Specifications", Volume 1, Springer 1985
[EM90] H. Ehrig, B. Mahr: "Fundamentals of Algebraic Specifications", Volume 2, Springer 1990
[M89] B. Möller: "Algorithmische Sprachen und Methodik des Programmierens I", lecture notes, Technical University Munich 1989
[ST99] D. Sannella, A. Tarlecki, "Algebraic Preliminaries", in Egidio Astesiano, Hans-Joerg Kreowski, Bernd Krieg-Brueckner, "Algebraic Foundations of System Specification", Springer 1999
[W90] M. Wirsing: "Algebraic Specification", in J. van Leeuwen: "Handbook of Theoretical Computer Science", Elsevier 1990
How to Cite This Entry:
Assignement. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Assignement&oldid=29507