Misc Language Operators

Project

Natural projection of marked and generated language.

Signature:

Project(+In+ Generator G, +In+ EventSet Sigma0, +Out+ Generator GRes)

Detailed description:

Given two alphabets Sigma and Sigma0, Sigma0  Sigma, the natural projection P0:Sigma*Sigma0* maps strings  Sigma* to strings  Sigma0* by cancelling any symbols  Sigma0:

P0(epsilon) = epsilon
P0(so) = P0(s)     if o  Sigma0
P0(so) = P0(s)o     if o  Sigma0

The function Project constructs a generator GRes that realises the projection of the marked and generated languages specified by the argument G:

L(GRes) = P0(L(G))
Lm(GRes) = P0(Lm(G))

The implementation iteratively replaces transitions with labels  Sigma0 by transitions to the next successor states. In general, this will lead to a non-deterministic generator. The function Project therefore subsequently calls Deterministic and StateMin to construct a deterministic realisation of the result.

As of libFAUDES 2.23f, alternative implementations are provided via the C++ API. Please let us know, if you experience performance issues with the default algorithm.

Example:
G GRes with Project(G, {a, c, g, e}, GRes)
Parameter Conditions:

The specified generator does not need to be deterministic. The resulting generator is deterministic.

InvProject

Inverse projection of marked and generated language.

Signature:

InvProject(+InOut+ Generator G0, +In+ EventSet Sigma)

InvProject(+In+ Generator G0, +In+ EventSet Sigma, +Out+ Generator GRes)

Detailed description:

Given two alphabets Sigma and Sigma0, Sigma0  Sigma, the set-valued inverse of the natural projection Pinv0 maps strings  Sigma0* to sets of strings Pinv0(r)  Sigma* by inserting arbitrary symbols  Sigma0:

Pinv0(r) = {s  Sigma*| P0(s) = r}    for r  Sigma0*,

see also Project.

The function InvProject constructs a generator GRes that realises the inverse projection of the marked and generated languages specified by the argument G0:

L(GRes) = Pinv0(L(G0))
Lm(GRes) = Pinv0(Lm(G0))

This implementation realises the inverse projection by inserting self-loop transitions at every state for all events that are in the target alphabet Sigma but not in the generators alphabet Sigma0.

Parameter Conditions:

The target alphabet Sigma must be a superset of the generators alphabet. Provided the specified generator is deterministic, so is the resulting generator.

SelfLoop

Self loop with specified alphabet.

Signature:

SelfLoop(+InOut+ Generator G, +In+ EventSet Sigma)

Detailed description:

This function self-loops all states of the provide generator G with the events from the alphabet Sigma: for each state  G and each event  Sigma, a transition (q,o,q) is inserted, irrespective of whether this event was already active in q before.

Parameter Conditions:

The provided generator may be non-deterministic. When a deterministic generator is provided, the result can still become non-deterministic in the case that Sigma shares events with the original alphabet.

libFAUDES 2.32b --- 2024.03.08 --- with "synthesis-observer-diagnosis-iosystem-hiosys-multitasking-coordinationcontrol-timed-iodevice-simulator-luabindings"