libsemigroups  v3.1.2
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
knuth-bendix-impl.hpp
1//
2// libsemigroups - C++ library for semigroups and monoids
3// Copyright (C) 2019-2025 James D. Mitchell + Joseph Edwards
4//
5// This program is free software: you can redistribute it and/or modify
6// it under the terms of the GNU General Public License as published by
7// the Free Software Foundation, either version 3 of the License, or
8// (at your option) any later version.
9//
10// This program is distributed in the hope that it will be useful,
11// but WITHOUT ANY WARRANTY; without even the implied warranty of
12// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13// GNU General Public License for more details.
14//
15// You should have received a copy of the GNU General Public License
16// along with this program. If not, see <http://www.gnu.org/licenses/>.
17//
18
19// This file contains a class KnuthBendixImpl which implements the Knuth-Bendix
20// algorithm for finitely presented monoids.
21
22// TODO(1)
23// * noexcept
24// * separate rule container from Rules
25// * nodiscard
26
27#ifndef LIBSEMIGROUPS_DETAIL_KNUTH_BENDIX_IMPL_HPP_
28#define LIBSEMIGROUPS_DETAIL_KNUTH_BENDIX_IMPL_HPP_
29
30#include <algorithm> // for max, min, copy
31#include <atomic> // for atomic_bool
32#include <cctype> // for isprint
33#include <chrono> // for duration_cast
34#include <cmath> // for pow
35#include <cstddef> // for size_t
36#include <cstdint> // for int64_t, uint32_t
37#include <iterator> // for back_inserter
38#include <memory> // for allocator, uni...
39#include <ostream> // for ostream
40#include <string> // for basic_string
41#include <string_view> // for basic_string_view
42#include <type_traits> // for is_same_v
43#include <unordered_map> // for unordered_map
44#include <utility> // for move, make_pair
45#include <vector> // for vector
46
47#include "libsemigroups/adapters.hpp" // for Hash
48#include "libsemigroups/constants.hpp" // for POSITIVE_INFINITY
49#include "libsemigroups/debug.hpp" // for LIBSEMIGROUPS_...
50#include "libsemigroups/obvinf.hpp" // for is_obviously_infinite
51#include "libsemigroups/order.hpp" // for ShortLexCompare
52#include "libsemigroups/presentation.hpp" // for operator!=
53#include "libsemigroups/ranges.hpp" // for count, iterato...
54#include "libsemigroups/types.hpp" // for congruence_kind
55#include "libsemigroups/word-graph.hpp" // for WordGraph, to_...
56#include "libsemigroups/word-range.hpp" // for to_human_reada...
57
58#include "cong-common-class.hpp" // for CongruenceInte...
59#include "fmt.hpp" // for format, print
60#include "report.hpp" // for report_no_prefix
61#include "rewriters.hpp" // for Rule, internal...
62#include "string.hpp" // for group_digits
63#include "timer.hpp" // for string_time
64
65namespace libsemigroups {
66 // Forward declarations
67 namespace detail {
68 template <typename KnuthBendix_>
69 class KBE;
77
92
108
119
133
134 template <typename Rewriter = detail::RewriteTrie,
135 typename ReductionOrder = ShortLexCompare>
136 class KnuthBendixImpl : public CongruenceCommon {
137 public:
139 // Aliases
141
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;
145
147 // Nested classes - public
149
150 struct options {
151 enum class overlap { ABC = 0, AB_BC = 1, MAX_AB_BC = 2 };
152 };
153
154 private:
156 // Nested classes - private
158
159 // Overlap measures
160 struct OverlapMeasure {
161 virtual size_t
162 operator()(detail::Rule const*,
163 detail::Rule const* examples,
164 typename native_word_type::const_iterator const&)
165 = 0;
166 virtual ~OverlapMeasure() {}
167 };
168
169 struct ABC;
170 struct AB_BC;
171 struct MAX_AB_BC;
172
173 struct Settings {
174 Settings() noexcept;
175 Settings& init() noexcept;
176
177 Settings(Settings const&) noexcept = default;
178 Settings(Settings&&) noexcept = default;
179 Settings& operator=(Settings const&) noexcept = default;
180 Settings& operator=(Settings&&) noexcept = default;
181
182 size_t max_pending_rules;
183 size_t check_confluence_interval;
184 size_t max_overlap;
185 size_t max_rules;
186 typename options::overlap overlap_policy;
187 };
188
189 struct Stats {
190 Stats() noexcept;
191 Stats& init() noexcept;
192
193 Stats(Stats const&) noexcept = default;
194 Stats(Stats&&) noexcept = default;
195 Stats& operator=(Stats const&) noexcept = default;
196 Stats& operator=(Stats&&) noexcept = default;
197
198 size_t prev_active_rules;
199 size_t prev_inactive_rules;
200 size_t prev_total_rules;
201 };
202
204 // KnuthBendixImpl - data - private
206
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;
211 Presentation<native_word_type> _presentation;
212 mutable Rewriter _rewriter;
213 Settings _settings;
214 mutable Stats _stats;
215 mutable native_word_type _tmp_element1;
216
217 public:
219 // KnuthBendixImpl - constructors and destructor - public
221
222 KnuthBendixImpl();
223 KnuthBendixImpl& init();
224 KnuthBendixImpl(KnuthBendixImpl const& that);
225
226 KnuthBendixImpl(KnuthBendixImpl&&);
227
228 KnuthBendixImpl& operator=(KnuthBendixImpl const&);
229
230 KnuthBendixImpl& operator=(KnuthBendixImpl&&);
231
232 ~KnuthBendixImpl();
233
234 KnuthBendixImpl(congruence_kind knd,
235 Presentation<native_word_type> const& p);
236
237 KnuthBendixImpl& init(congruence_kind knd,
238 Presentation<native_word_type> const& p);
239
240 KnuthBendixImpl(congruence_kind knd, Presentation<native_word_type>&& p);
241
242 KnuthBendixImpl& init(congruence_kind knd,
243 Presentation<native_word_type>&& p);
244
245 // TODO(1) construct/init from kind and KnuthBendixImpl const&, for
246 // consistency with ToddCoxeterImpl
247
248 private:
249 void init_from_generating_pairs();
250 void init_from_internal_presentation();
251
253 // KnuthBendixImpl - interface requirements - add_generating_pair
255
256 public:
257 // NOTE THAT this is not the same as in ToddCoxeterImpl, because the
258 // generating pairs contained in CongruenceCommon are word_types, and
259 // so we don't require any conversion here (since chars can be converted
260 // implicitly to letter_types)
261 template <typename Iterator1,
262 typename Iterator2,
263 typename Iterator3,
264 typename Iterator4>
265 KnuthBendixImpl& add_generating_pair_no_checks(Iterator1 first1,
266 Iterator2 last1,
267 Iterator3 first2,
268 Iterator4 last2) {
269 LIBSEMIGROUPS_ASSERT(!started());
270 return CongruenceCommon::add_internal_generating_pair_no_checks<
271 KnuthBendixImpl>(first1, last1, first2, last2);
272 }
273
274 template <typename Iterator1,
275 typename Iterator2,
276 typename Iterator3,
277 typename Iterator4>
278 KnuthBendixImpl& add_generating_pair(Iterator1 first1,
279 Iterator2 last1,
280 Iterator3 first2,
281 Iterator4 last2) {
282 LIBSEMIGROUPS_ASSERT(!started());
283 return CongruenceCommon::add_generating_pair<KnuthBendixImpl>(
284 first1, last1, first2, last2);
285 }
286
288 // KnuthBendixImpl - interface requirements - number_of_classes
290
309 [[nodiscard]] uint64_t number_of_classes();
310
312 // KnuthBendixImpl - interface requirements - contains
314
333 template <typename Iterator1,
334 typename Iterator2,
335 typename Iterator3,
336 typename Iterator4>
337 [[nodiscard]] tril currently_contains_no_checks(Iterator1 first1,
338 Iterator2 last1,
339 Iterator3 first2,
340 Iterator4 last2) const;
341
342 // Documented in KnuthBendix (because it appears there because we call
343 // CongruenceCommon::currently_contains directly so that bounds checks are
344 // done in KnuthBendix)
345 template <typename Iterator1,
346 typename Iterator2,
347 typename Iterator3,
348 typename Iterator4>
349 [[nodiscard]] tril currently_contains(Iterator1 first1,
350 Iterator2 last1,
351 Iterator3 first2,
352 Iterator4 last2) const {
353 return CongruenceCommon::currently_contains<KnuthBendixImpl>(
354 first1, last1, first2, last2);
355 }
356
373 template <typename Iterator1,
374 typename Iterator2,
375 typename Iterator3,
376 typename Iterator4>
377 [[nodiscard]] bool contains_no_checks(Iterator1 first1,
378 Iterator2 last1,
379 Iterator3 first2,
380 Iterator4 last2) {
381 return CongruenceCommon::contains_no_checks<KnuthBendixImpl>(
382 first1, last1, first2, last2);
383 }
384
385 // Documented in KnuthBendix (because it appears there because we call
386 // CongruenceCommon::contains directly so that bounds checks are
387 // done in KnuthBendix)
388 template <typename Iterator1,
389 typename Iterator2,
390 typename Iterator3,
391 typename Iterator4>
392 [[nodiscard]] bool contains(Iterator1 first1,
393 Iterator2 last1,
394 Iterator3 first2,
395 Iterator4 last2) {
396 return CongruenceCommon::contains<KnuthBendixImpl>(
397 first1, last1, first2, last2);
398 }
399
401 // KnuthBendixImpl - interface requirements - reduce
403
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;
410
411 // Documented in KnuthBendix (because it appears there because we call
412 // CongruenceCommon::reduce_no_run directly so that bounds checks are
413 // done in KnuthBendix)
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);
422 }
423
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);
432 }
433
434 // Documented in KnuthBendix (because it appears there because we call
435 // CongruenceCommon::reduce directly so that bounds checks are
436 // done in KnuthBendix)
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);
444 }
445
446 // TODO(1) implement reduce_inplace x4 if possible.
447
449 // KnuthBendixImpl - setters for optional parameters - public
451
472 KnuthBendixImpl& max_pending_rules(size_t val) {
473 _settings.max_pending_rules = val;
474 return *this;
475 }
476
496 [[nodiscard]] size_t max_pending_rules() const noexcept {
497 return _settings.max_pending_rules;
498 }
499
522 KnuthBendixImpl& check_confluence_interval(size_t val) {
523 _settings.check_confluence_interval = val;
524 return *this;
525 }
526
546 [[nodiscard]] size_t check_confluence_interval() const noexcept {
547 return _settings.check_confluence_interval;
548 }
549
571 KnuthBendixImpl& max_overlap(size_t val) {
572 _settings.max_overlap = val;
573 return *this;
574 }
575
594 [[nodiscard]] size_t max_overlap() const noexcept {
595 return _settings.max_overlap;
596 }
597
618 KnuthBendixImpl& max_rules(size_t val) {
619 _settings.max_rules = val;
620 return *this;
621 }
622
643 [[nodiscard]] size_t max_rules() const noexcept {
644 return _settings.max_rules;
645 }
646
663 KnuthBendixImpl& overlap_policy(typename options::overlap val);
664
682 [[nodiscard]] typename options::overlap overlap_policy() const noexcept {
683 return _settings.overlap_policy;
684 }
685
687 // KnuthBendixImpl - member functions for rules and rewriting - public
689
690 // TODO(1) remove
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);
695 }
696
697 [[nodiscard]] Presentation<native_word_type> const&
698 internal_presentation() const noexcept {
699 return _presentation;
700 }
701
717 [[nodiscard]] size_t number_of_active_rules() const noexcept;
718
735 [[nodiscard]] size_t number_of_inactive_rules() const noexcept {
736 return _rewriter.number_of_inactive_rules();
737 }
738
759 [[nodiscard]] size_t number_of_pending_rules() const noexcept {
760 return _rewriter.number_of_pending_rules();
761 }
762
781 [[nodiscard]] size_t total_rules() const noexcept {
782 return _rewriter.stats().total_rules;
783 }
784
785 Rewriter& rewriter() noexcept {
786 return _rewriter;
787 }
788
789 // Documented in KnuthBendix
790 // TODO(1) should be const
791 // TODO(1) add note about empty active rules after, or better discuss that
792 // there are three kinds of rules in the system: active, inactive, and
793 // pending.
794 [[nodiscard]] auto active_rules();
795
814 KnuthBendixImpl& process_pending_rules() {
815 _rewriter.process_pending_rules();
816 return *this;
817 }
818
819 private:
820 // TODO(1) remove this ...
821 void rewrite_inplace(native_word_type& w);
822
823 // TODO(1) remove this ...
824 [[nodiscard]] native_word_type rewrite(native_word_type w) {
825 rewrite_inplace(w);
826 return w;
827 }
828
829 public:
831 // KnuthBendixImpl - main member functions - public
833
842 [[nodiscard]] bool confluent() const;
843
854 [[nodiscard]] bool confluent_known() const noexcept;
855
878 WordGraph<uint32_t> const& gilman_graph();
879
880 // Documented in KnuthBendix
881 [[nodiscard]] std::vector<native_word_type> const&
882 gilman_graph_node_labels() {
883 gilman_graph(); // to ensure that gilman_graph is initialised
884 return _gilman_graph_node_labels;
885 }
886
887 protected:
888 // run_impl is called by KnuthBendix
889 void run_impl() override;
890
891 private:
893 // KnuthBendixImpl - private member functions
895
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();
900
901 void stats_check_point();
902
903 void add_octo(native_word_type& w) const;
904 void rm_octo(native_word_type& w) const;
905
906 void add_rule_impl(native_word_type const& p, native_word_type const& q);
907
908 void overlap(detail::Rule const* u, detail::Rule const* v);
909
910 [[nodiscard]] size_t max_active_word_length() const {
911 return _rewriter.max_active_word_length();
912 }
913
914 void run_real(std::atomic_bool&);
915 [[nodiscard]] bool stop_running() const;
916
918 // Runner - pure virtual member functions - private
920
921 bool finished_impl() const override;
922 }; // class KnuthBendixImpl
923 } // namespace detail
924
926 // global functions - to_human_readable_repr
928
929 // TODO(1) for consistency (with ToddCoxeter), the next two functions should
930 // really be in knuth-bendix.hpp.
931
946#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
947 template <typename Word, typename Rewriter, typename ReductionOrder>
950 KnuthBendix<Word, Rewriter, ReductionOrder> const& kb);
951#else
952 template <typename Rewriter, typename ReductionOrder>
955 detail::KnuthBendixImpl<Rewriter, ReductionOrder> const& kb);
956#endif
957
975 // TODO(1) preferably kb would be a const&
976#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
977 template <typename Word, typename Rewriter, typename ReductionOrder>
979 to_human_readable_repr(KnuthBendix<Word, Rewriter, ReductionOrder>& kb);
980#else
981 template <typename Rewriter, typename ReductionOrder>
983 to_human_readable_repr(detail::KnuthBendixImpl<Rewriter, ReductionOrder>& kb);
984#endif
985
987 // TODO(1) kb should be const
988 template <typename Result, typename Rewriter, typename ReductionOrder>
989 auto to(detail::KnuthBendixImpl<Rewriter, ReductionOrder>& kb)
990 -> std::enable_if_t<
991 std::is_same_v<Presentation<typename Result::word_type>, Result>,
992 Result>;
993
994} // namespace libsemigroups
995
996#include "knuth-bendix-impl.tpp"
997
998#endif // LIBSEMIGROUPS_DETAIL_KNUTH_BENDIX_IMPL_HPP_
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.
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.