alogos.systems._shared._cached_calculations

Functions

is_recursive(grammar)	Calculate for each production whether it contains a recursive nonterminal.
min_depths_to_terminals(grammar)	Calculate for each production the depth required to reach only terminals.
min_expansions_to_terminals(grammar)	Calculate for each production the number of expansions required to reach only terminals.
min_nodes_to_terminals(grammar)	Calculate for each production the number of nodes required to reach only terminals.
idx_min_nodes_to_terminals(grammar)	Create a dictionary of index to number of min nodes associations.

---

Detailed object descriptions

alogos.systems._shared._cached_calculations.is_recursive(grammar)

Calculate for each production whether it contains a recursive nonterminal.

A nonterminal is considered to be recursive if it can produce itself, i.e. if starting from it some derivation can be constructed where the nonterminal appears again.

References

• PonyGE2: src/representation/grammar.py

  • def check_recursion(self, cur_symbol, seen) solves the same task in a different way with recursive function calls

Examples

• S => SS => 1S => 12 means that S is trivially recursive, because there is a rule that replaces S directly with a sequence of symbols that contains S again.

• S => A => BB => 5B => 5S => 51 means S is non-trivially recursive, because S can be replaced indirectly (via other nonterminals and their rules) with a sequence of symbols that contains S again.

alogos.systems._shared._cached_calculations.min_depths_to_terminals(grammar)

Calculate for each production the depth required to reach only terminals.

This information is used during a derivation in order to remain within a maximum depth limit.

Algorithms that utilize it:

• Initialization of an inidividual with “grow”, “pi grow” and “full” methods that are part of ramped half-and-half (rhh) population initialization.

References

• PonyGE2: src/representation/grammar.py: Sensible initialization from GE (and other systems) uses this information to select rules

  • def check_depths(self) solves the same task with other data structures

alogos.systems._shared._cached_calculations.min_expansions_to_terminals(grammar)

Calculate for each production the number of expansions required to reach only terminals.

This information is used during a derivation in order to remain within a maximum expansions limit.

Algorithms that utilize it:

• Initialization of an inidividual with “PTC2” method.

alogos.systems._shared._cached_calculations.min_nodes_to_terminals(grammar)

Calculate for each production the number of nodes required to reach only terminals.

alogos.systems._shared._cached_calculations.idx_min_nodes_to_terminals(grammar)

Create a dictionary of index to number of min nodes associations.