Mathematical Definitions and Notations

In the realm of Michael Heilmann's Arcadia, understanding the mathematical definitions and notations is crucial for grasping the underlying concepts. This document covers fundamental definitions and notations used in mathematical contexts relevant to Michael Heilmann's Arcadia.

1 Lists

This document is the specification of the Data Definition Language Schema, or DDLS for short. DDLS is a declarative language for defining the structure and constraints for data described by a DDL programs.

1.1 List

A list is an ordered list of mathematical objects. A list is written starting with an opening square bracket $[$, followd by the elements where two consecutive elments are separated by a comma $,$, followed by a closing square bracket $]$. For example, $\left[1,2,3\right]$ is the list with three elements, the first one being $1$, the second one being $2$, and the third one being $3$. The empty list is denoted by $\ListEmpty$. The length of the list is usually denoted by $\ListLength{a}$. Elements of a list can be referenced in terms of their 1-based position. If $a$ is a list then the i-th element of that list is usually denoted by $\ListAt{a}{i}$. The set of lists is denoted by $\ListType$.

1.2 Identity of Lists

The general for for the identity of two lists $a, b \in \ListType$ is defined by:

\[ a = b \Leftrightarrow \ListLength{a} = \ListLength{b} \wedge \forall 1 \leq i \leq \ListLength{a} : a_i = b_i \]

1.3 Concatenation of Lists

The concatenation of two lists $a,b \in \ListType$ is defined indictutively:

Fist, the special cases in which at least one of $a$ and $b$ is an empty list:

If $b = \ListEmpty$, then $a \circ b = a$.
If $a = \ListEmpty$, then $a \circ b = b$.

Otherwise both $a$ and $b$ each have at least one element. Their concatenation $c$ is then defined by $c = a \circ b$ such that \[ \forall 1 \leq i \leq \ListLength{a} : \ListAt{c}{i} = \ListAt{a}{i} \wedge \forall 1 \leq j \leq \ListLength{b} : \ListAt{c}{\ListLength{a} + j} = \ListAt{b}{j} \]

2 Context-Free Grammars

A context-free grammar $G$ is a 4-tuple $G = (V,\Sigma,P,S)$, where

$V$ is a finite set; each element $v \in V$ is called a nonterminal element.
$\Sigma$ is a finite set of terminals, disjoint vom $V$.
$P$ is a finite relation in $V \times (V \cup T)^*$, where the asterisk represents the Kleene star operation. The members of $R$ are called productions of the grammar.
$S$ is the start element. $S$ must be an element of $V$.

A production rule in $P$ is an ordered pair $(\alpha,\beta)\in P$, where $a \in V$ is a nonterminal and $\beta \in (V \cup \Sigma)^*$ is a string of nonterminals and/or terminals; rather than using an ordered pair notation, production rules are usually written using an arrow operator with $\alpha$ as its left hand side and $\beta$ as its right hand side $\alpha \rightarrow \beta$.

It is allow for $\beta$ to be the empty string and in this case it is denoted by it by $\epsilon$. The form $\alpha \rightarrow \epsilon$ is called an $\epsilon$-production.

2.1 Direct derivation

The operation of a context-free grammar is defined in terms of the relation of two strings. For any two strings $u,v \in \left(V \cup \Sigma\right)^*$, we say $v$ directly derives from $u$, written as $u \Rightarrow v$ if there exists a production $(\alpha \rightarrow \beta) \in P$ with $\alpha \in V$ and $u_1, u_2 \in \left(V \cup \Sigma\right)^*$ such that $u = u_1 \alpha u_2$ and $v = u_1 \beta u_2$. Thus, $v$ is a result of applying the rule $\alpha \rightarrow \beta$ to $u$.

2.2 Indirect derivation

For any two string $u,v\in (V \cup \Sigma)^*$, we say $v$ indirectly drives from $u$ if there is a positive integer $k$ and string $u_1, \ldots, u_k \in \left(V \cup \Sigma\right)^*$ such that $u = u_1 \Rightarrow u_2 \Rightarrow \ldots \Rightarrow u_k = v$, that is, the $\Rightarrow$ operator is applied $k-1$ times.

To express that the operator is applied zero or more times to derive $v$ from $u$ one writes $u \stackrel{*}{\Rightarrow} v$.

To express that the operator is applied zero or one times to derive $v$ from $u$ one writes $u \stackrel{?}{\Rightarrow} v$.

To express that the operator is applied one or more times to derive $v$ from $u$ one writes $u \stackrel{+}{\Rightarrow} v$.

The language $L(G)$ of a grammar $G = \left(V,\Sigma,P,S\right)$ is the set \[ L(G) = \left\{ w \in \Sigma^* : S \stackrel{*}{\Rightarrow} w \right\} \]

2.3 Notational convenience

One may use a colon instead of the rightarrows such that $\alpha \rightarrow \beta$ becomes $\alpha$ : $\beta$.

Terminals which are Unicode code points may be written starting with a shebang # followed by a hexadecimal number denoting the code point.

The following productions define non-terminals for the Unicode code symbols "PLUS SIGN" and "MINUS SIGN":

\[\begin{aligned} &\text{/* \#2b is also known as "PLUS SIGN" */}\\ &\text{PlusSign} : \text{\#2b}\\ &\text{/* \#2d is also known as "MINUS SIGN" */}\\ &\text{MinusSign} : \text{\#2b}\\ \end{aligned}\]

The syntax {x} on the right-hand side of a production denotes zero or more occurrences of x.

The following production defines a possibly empty sequence of digits:

\[\begin{aligned} &\text{ZeroOrMoreDigits}:\left\{\text{Digit}\right\} \end{aligned}\]

The syntax [x] on the right-hand side of a production denotes zero or one occurrences of x.

The following productions denotes a possible definition of an integer numeral. It consists of an optional sign followed by a digit followed by zero or more digits:

\[\begin{aligned} &\text{Integer}:\left[\text{Sign}\right]\;\text{Digit}\;\text{ZeroOrMoreDigits} \end{aligned}\]