Generation system

In mathematics, a generation system (not: generating system ) is understood to be a formal system that consists of an initial set and one or more generation rules. The elements of the initial set are also called axioms . By applying the generation rules, new elements can be obtained from the initial set and added to the initial set. The rules can be applied again to this expanded set. This process is repeated iteratively until a desired quantity, the product , has been derived.

Generation systems serve the constructive definition of quantities in very different contexts. These sets can be ranges of numbers , trees , terms , formulas or languages . A simple example shows how the set of natural numbers can be constructed using a generation system: ${\displaystyle \mathbb {N} }$

• Let the initial set A be ${\displaystyle \{0\}\subseteq \mathbb {N} }$
• Generation rule: x + 1 may be generated from each x and added to the initial set.

Another well-known example of generation systems are the formal grammars of the Chomsky hierarchy - the products in this case are formal languages . Furthermore, logical calculi form an important class of generation systems, which are also referred to as proof systems . Due to their constructive and therefore application-oriented character, different generation systems play an important role in computer science .