27#ifndef LIBSEMIGROUPS_DETAIL_KNUTH_BENDIX_IMPL_HPP_
28#define LIBSEMIGROUPS_DETAIL_KNUTH_BENDIX_IMPL_HPP_
43#include <unordered_map>
47#include "libsemigroups/adapters.hpp"
48#include "libsemigroups/constants.hpp"
49#include "libsemigroups/debug.hpp"
50#include "libsemigroups/obvinf.hpp"
51#include "libsemigroups/order.hpp"
52#include "libsemigroups/presentation.hpp"
53#include "libsemigroups/ranges.hpp"
54#include "libsemigroups/types.hpp"
55#include "libsemigroups/word-graph.hpp"
56#include "libsemigroups/word-range.hpp"
58#include "cong-common-class.hpp"
61#include "rewriters.hpp"
68 template <
typename KnuthBendix_>
134 template <
typename Rewriter = detail::RewriteTrie,
135 typename ReductionOrder = ShortLexCompare>
136 class KnuthBendixImpl :
public CongruenceCommon {
142 using native_word_type =
typename Rewriter::native_word_type;
143 using rule_type = std::pair<native_word_type, native_word_type>;
144 using rewriter_type = Rewriter;
151 enum class overlap { ABC = 0, AB_BC = 1, MAX_AB_BC = 2 };
160 struct OverlapMeasure {
162 operator()(detail::Rule
const*,
163 detail::Rule
const* examples,
164 typename native_word_type::const_iterator
const&)
166 virtual ~OverlapMeasure() {}
175 Settings& init() noexcept;
177 Settings(Settings const&) noexcept = default;
178 Settings(Settings&&) noexcept = default;
179 Settings& operator=(Settings const&) noexcept = default;
180 Settings& operator=(Settings&&) noexcept = default;
182 size_t max_pending_rules;
183 size_t check_confluence_interval;
186 typename options::overlap overlap_policy;
191 Stats& init() noexcept;
193 Stats(Stats const&) noexcept = default;
194 Stats(Stats&&) noexcept = default;
195 Stats& operator=(Stats const&) noexcept = default;
196 Stats& operator=(Stats&&) noexcept = default;
198 size_t prev_active_rules;
199 size_t prev_inactive_rules;
200 size_t prev_total_rules;
207 bool _gen_pairs_initted;
208 WordGraph<uint32_t> _gilman_graph;
209 std::vector<native_word_type> _gilman_graph_node_labels;
210 std::unique_ptr<OverlapMeasure> _overlap_measure;
212 mutable Rewriter _rewriter;
214 mutable Stats _stats;
215 mutable native_word_type _tmp_element1;
223 KnuthBendixImpl& init();
224 KnuthBendixImpl(KnuthBendixImpl const& that);
226 KnuthBendixImpl(KnuthBendixImpl&&);
228 KnuthBendixImpl& operator=(KnuthBendixImpl const&);
230 KnuthBendixImpl& operator=(KnuthBendixImpl&&);
249 void init_from_generating_pairs();
250 void init_from_internal_presentation();
261 template <typename Iterator1,
265 KnuthBendixImpl& add_generating_pair_no_checks(Iterator1 first1,
269 LIBSEMIGROUPS_ASSERT(!
started());
270 return CongruenceCommon::add_internal_generating_pair_no_checks<
271 KnuthBendixImpl>(first1, last1, first2, last2);
274 template <
typename Iterator1,
282 LIBSEMIGROUPS_ASSERT(!
started());
283 return CongruenceCommon::add_generating_pair<KnuthBendixImpl>(
284 first1, last1, first2, last2);
333 template <
typename Iterator1,
340 Iterator4 last2)
const;
345 template <
typename Iterator1,
349 [[nodiscard]]
tril currently_contains(Iterator1 first1,
352 Iterator4 last2)
const {
353 return CongruenceCommon::currently_contains<KnuthBendixImpl>(
354 first1, last1, first2, last2);
373 template <
typename Iterator1,
381 return CongruenceCommon::contains_no_checks<KnuthBendixImpl>(
382 first1, last1, first2, last2);
388 template <
typename Iterator1,
392 [[nodiscard]]
bool contains(Iterator1 first1,
396 return CongruenceCommon::contains<KnuthBendixImpl>(
397 first1, last1, first2, last2);
404 template <
typename OutputIterator,
405 typename InputIterator1,
406 typename InputIterator2>
407 OutputIterator reduce_no_run_no_checks(OutputIterator d_first,
408 InputIterator1 first,
409 InputIterator2 last)
const;
414 template <
typename OutputIterator,
415 typename InputIterator1,
416 typename InputIterator2>
417 OutputIterator reduce_no_run(OutputIterator d_first,
418 InputIterator1 first,
419 InputIterator2 last)
const {
420 return CongruenceCommon::reduce_no_run<KnuthBendixImpl>(
421 d_first, first, last);
424 template <
typename OutputIterator,
425 typename InputIterator1,
426 typename InputIterator2>
427 OutputIterator reduce_no_checks(OutputIterator d_first,
428 InputIterator1 first,
429 InputIterator2 last) {
430 return CongruenceCommon::reduce_no_checks<KnuthBendixImpl>(
431 d_first, first, last);
437 template <
typename OutputIterator,
438 typename InputIterator1,
439 typename InputIterator2>
440 OutputIterator
reduce(OutputIterator d_first,
441 InputIterator1 first,
442 InputIterator2 last) {
443 return CongruenceCommon::reduce<KnuthBendixImpl>(d_first, first, last);
473 _settings.max_pending_rules = val;
497 return _settings.max_pending_rules;
523 _settings.check_confluence_interval = val;
547 return _settings.check_confluence_interval;
572 _settings.max_overlap = val;
595 return _settings.max_overlap;
619 _settings.max_rules = val;
644 return _settings.max_rules;
683 return _settings.overlap_policy;
691 template <
typename Iterator1,
typename Iterator2>
692 void throw_if_letter_not_in_alphabet(Iterator1 first,
693 Iterator2 last)
const {
694 internal_presentation().throw_if_letter_not_in_alphabet(first, last);
698 internal_presentation() const noexcept {
699 return _presentation;
736 return _rewriter.number_of_inactive_rules();
760 return _rewriter.number_of_pending_rules();
782 return _rewriter.stats().total_rules;
785 Rewriter& rewriter() noexcept {
794 [[nodiscard]]
auto active_rules();
821 void rewrite_inplace(native_word_type& w);
824 [[nodiscard]] native_word_type rewrite(native_word_type w) {
881 [[nodiscard]]
std::vector<native_word_type> const&
882 gilman_graph_node_labels() {
884 return _gilman_graph_node_labels;
889 void run_impl()
override;
896 void report_presentation()
const;
897 void report_before_run();
898 void report_progress_from_thread(std::atomic_bool
const&);
899 void report_after_run();
901 void stats_check_point();
903 void add_octo(native_word_type& w)
const;
904 void rm_octo(native_word_type& w)
const;
906 void add_rule_impl(native_word_type
const& p, native_word_type
const& q);
908 void overlap(detail::Rule
const* u, detail::Rule
const* v);
910 [[nodiscard]]
size_t max_active_word_length()
const {
911 return _rewriter.max_active_word_length();
914 void run_real(std::atomic_bool&);
915 [[nodiscard]]
bool stop_running()
const;
921 bool finished_impl()
const override;
946#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
947 template <
typename Word,
typename Rewriter,
typename ReductionOrder>
950 KnuthBendix<Word, Rewriter, ReductionOrder>
const& kb);
952 template <
typename Rewriter,
typename ReductionOrder>
955 detail::KnuthBendixImpl<Rewriter, ReductionOrder>
const& kb);
976#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
977 template <
typename Word,
typename Rewriter,
typename ReductionOrder>
981 template <
typename Rewriter,
typename ReductionOrder>
988 template <
typename Result,
typename Rewriter,
typename ReductionOrder>
989 auto to(detail::KnuthBendixImpl<Rewriter, ReductionOrder>& kb)
991 std::is_same_v<Presentation<typename Result::word_type>, Result>,
996#include "knuth-bendix-impl.tpp"
For an implementation of presentations for semigroups or monoids.
Definition presentation.hpp:102
bool started() const noexcept
Check if run has been called at least once before.
Definition runner.hpp:612
Class for representing word graphs.
Definition word-graph.hpp:82
std::string to_human_readable_repr(AhoCorasick const &ac)
Return a string representation.
std::ostringstream & operator<<(std::ostringstream &os, BMat8 const &x)
Insertion operator.
void add_generating_pair(Thing &thing, typename Thing::native_word_type const &u, typename Thing::native_word_type const &v)
Helper for adding a generating pair of words.
Definition cong-common-helpers.hpp:200
Thing::native_word_type reduce(Thing const &thing, typename Thing::native_word_type const &w)
Reduce a word.
size_t number_of_active_rules() const noexcept
Return the current number of active rules in the KnuthBendix instance.
WordGraph< uint32_t > const & gilman_graph()
size_t number_of_inactive_rules() const noexcept
Definition knuth-bendix-impl.hpp:735
bool confluent_known() const noexcept
Check if the current system knows the state of confluence of the current rules.
size_t number_of_pending_rules() const noexcept
Return the number of pending rules.
Definition knuth-bendix-impl.hpp:759
bool confluent() const
Check confluence of the current rules.
size_t total_rules() const noexcept
Return the number of rules that KnuthBendix has created.
Definition knuth-bendix-impl.hpp:781
KnuthBendixImpl & process_pending_rules()
Process any pending rules.
Definition knuth-bendix-impl.hpp:814
uint64_t number_of_classes()
Compute the number of classes in the congruence.
bool contains_no_checks(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
Check containment of a pair of words via iterators.
Definition knuth-bendix-impl.hpp:377
tril currently_contains_no_checks(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
Check containment of a pair of words via iterators.
KnuthBendixImpl & check_confluence_interval(size_t val)
Definition knuth-bendix-impl.hpp:522
KnuthBendixImpl & max_pending_rules(size_t val)
Definition knuth-bendix-impl.hpp:472
KnuthBendixImpl & max_overlap(size_t val)
Definition knuth-bendix-impl.hpp:571
KnuthBendixImpl & max_rules(size_t val)
Definition knuth-bendix-impl.hpp:618
KnuthBendixImpl & overlap_policy(typename options::overlap val)
Presentation(Presentation< Word > const &) -> Presentation< Word >
Deduction guide.
tril
Enum to indicate true, false or not currently knowable.
Definition types.hpp:54
congruence_kind
Enum to indicate the sided-ness of a congruence.
Definition types.hpp:67
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
auto to(detail::KnuthBendixImpl< Rewriter, ReductionOrder > &kb) -> std::enable_if_t< std::is_same_v< Presentation< typename Result::word_type >, Result >, Result >
No doc.