-
Notifications
You must be signed in to change notification settings - Fork 19
Open
Labels
For:libraryThe issue is related to library (c++ implementation)The issue is related to library (c++ implementation)Module:nftThe issue is related to Nondeterministic Finite TransducersThe issue is related to Nondeterministic Finite TransducersType:optimizationThis issue is related to a possible optimization of an algorithm, improving the performance of Mata.This issue is related to a possible optimization of an algorithm, improving the performance of Mata.
Description
The function mata::applications::strings::replace::replace_reluctant_regex
often constructs nft_reluctant_replace
with
- unnecessary isolated states, and
- multiple consecutive epsilon transitions between two zero-level states.
This does not affect the correctness of the algorithm. However, the redundant epsilon transitions can significantly increase the number of transitions in the composition.
For example, when running the following code:
mata::EnumAlphabet alphabet{ 'a', 'f' };
Nft nft{ mata::applications::strings::replace::replace_reluctant_regex("a", { 'f' }, &alphabet) };
the nft_reluctant_replace
inside the mata::applications::strings::replace::replace_reluctant_regex
function looks like:
Here, you can see that states 2 and 5 are isolated. Additionally, there is an unnecessary sequence of epsilon transitions: 12--->11--->13--->14--->6
Ideally, states 2 and 5 should not be present, and the epsilon chain should be replaced with a direct transition 10 ---f---> 6.
Metadata
Metadata
Assignees
Labels
For:libraryThe issue is related to library (c++ implementation)The issue is related to library (c++ implementation)Module:nftThe issue is related to Nondeterministic Finite TransducersThe issue is related to Nondeterministic Finite TransducersType:optimizationThis issue is related to a possible optimization of an algorithm, improving the performance of Mata.This issue is related to a possible optimization of an algorithm, improving the performance of Mata.