libsemigroups  v3.1.2
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
obvinf.hpp
1//
2// libsemigroups - C++ library for semigroups and monoids
3// Copyright (C) 2020-2025 James D. Mitchell + Reinis Cirpons
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 helper class for checking whether or not a congruence
20// defined by generating pairs or finitely presented semigroup or monoid is
21// obviously infinite.
22
23#ifndef LIBSEMIGROUPS_OBVINF_HPP_
24#define LIBSEMIGROUPS_OBVINF_HPP_
25
26#include <cstddef> // for size_t
27#include <numeric> // for accumulate
28#include <string> // for string
29#include <utility> // for pair
30#include <vector> // for vector
31
32#include "config.hpp" // for LIBSEMIGROUPS_EIGEN_ENABLED
33#include "ranges.hpp" // for rx/ranges
34#include "types.hpp" // for word_type etc
35#include "word-graph.hpp" // for is_acyclic
36#include "word-range.hpp" // for ToWord
37
38#include "detail/eigen.hpp" // for eigen
39#include "detail/uf.hpp" // for Duf
40
41namespace libsemigroups {
42#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
43
44 namespace detail {
45 template <typename Rewriter, typename ReductionOrder>
46 class KnuthBendixImpl; // forward decl
47 class ToddCoxeterImpl; // forward decl
48 } // namespace detail
49
50 template <typename Word>
51 class Congruence; // forward decl
52
53 template <typename Word>
54 class Kambites; // forward decl
55
56 template <typename Word>
57 class Presentation; // forward decl
58#endif
59
60 namespace presentation {
61 template <typename Word>
63 }
64
77
126 // TODO(1) there are definitely some assumptions about the calls to the member
127 // functions of an IsObviouslyInfinite (see for example the function
128 // is_obviously_infinite for a Presentation). These should be documented.
129 //
130 // TODO(1) this class should be more generic, like detail::CongruenceCommon
131 // and its derived classes, allowing arbitrary iterators of rules to be added
132 class IsObviouslyInfinite {
133 // The default constructor is private since an object that is default
134 // constructed isn't usable with the current public API.
135 IsObviouslyInfinite() = default;
136
137 public:
141
149
153
163 explicit IsObviouslyInfinite(size_t n);
164
180 IsObviouslyInfinite& init(size_t n);
181
191 explicit IsObviouslyInfinite(std::string const& lphbt)
192 : IsObviouslyInfinite(lphbt.size()) {}
193
209 IsObviouslyInfinite& init(std::string const& lphbt) {
210 return init(lphbt.size());
211 }
212
214 IsObviouslyInfinite(IsObviouslyInfinite const&) = delete;
215
217 IsObviouslyInfinite(IsObviouslyInfinite&&) = delete;
218
220 IsObviouslyInfinite& operator=(IsObviouslyInfinite const&) = delete;
221
223 IsObviouslyInfinite& operator=(IsObviouslyInfinite&&) = delete;
224
225 ~IsObviouslyInfinite();
226
245 IsObviouslyInfinite& add_rules_no_checks(word_type const&,
248
270 template <typename Char>
271 IsObviouslyInfinite& add_rules_no_checks(
272 std::basic_string<Char> const& lphbt,
273 typename std::vector<std::basic_string<Char>>::const_iterator first,
274 typename std::vector<std::basic_string<Char>>::const_iterator last) {
275#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
276 auto matrix_start = _matrix.rows();
277 _matrix.conservativeResize(matrix_start + (last - first) / 2,
278 Eigen::NoChange);
279 _matrix.block(matrix_start, 0, (last - first) / 2, _matrix.cols())
280 .setZero();
281#else
282 auto matrix_start = 0;
283 std::fill(_matrix.begin(), _matrix.end(), 0);
284#endif
285
286 v4::ToWord stw(lphbt);
287 word_type lhs, rhs;
288 for (auto it = first; it < last; ++it) {
289 stw(lhs, *it++); // lhs changed in-place
290 stw(rhs, *it); // rhs changed in-place
291 private_add_rule(matrix_start + (it - first) / 2, lhs, rhs);
292 }
293 _nr_letter_components = _letter_components.number_of_blocks();
294 return *this;
295 }
296
318 IsObviouslyInfinite& add_rules_no_checks(
319 char const* lphbt,
322 std::vector<std::string> copy(first, last);
323 return add_rules_no_checks(std::string(lphbt), copy.begin(), copy.end());
324 }
325
344 template <typename Char>
349#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
350 auto matrix_start = _matrix.rows();
351 _matrix.conservativeResize(matrix_start + (last - first) / 2,
352 Eigen::NoChange);
353 _matrix.block(matrix_start, 0, (last - first) / 2, _matrix.cols())
354 .setZero();
355#else
356 auto matrix_start = 0;
357 std::fill(_matrix.begin(), _matrix.end(), 0);
358#endif
359
360 v4::ToWord to_word(lphbt);
361 word_type lhs, rhs;
363 for (auto it = first; it < last; ++it) {
364 // changes lhs in-place
365 tmp.assign(it->begin(), it->end());
366 to_word(lhs, tmp);
367 ++it;
368 // changes rhs in-place
369 tmp.assign(it->begin(), it->end());
370 to_word(rhs, tmp);
371 private_add_rule(matrix_start + (it - first) / 2, lhs, rhs);
372 }
373 _nr_letter_components = _letter_components.number_of_blocks();
374 return *this;
375 }
376
398 IsObviouslyInfinite& add_rules_no_checks(std::string const& lphbt,
401
413 bool result() const;
414
415 // TODO(1) certificate() returning why the thing is obviously infinite
416
417 private:
418 void private_add_rule(size_t const, word_type const&, word_type const&);
419
420 inline void letters_in_word(size_t row, word_type const& w, int64_t adv) {
421 for (size_t const& x : w) {
422 matrix(row, x) += adv;
423 _seen[x] = true;
424 }
425 }
426
427 inline void plus_letters_in_word(size_t row, word_type const& w) {
428 letters_in_word(row, w, 1);
429 }
430
431 inline void minus_letters_in_word(size_t row, word_type const& w) {
432 letters_in_word(row, w, -1);
433 }
434
435 inline int64_t& matrix(size_t row, size_t col) {
436#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
437 return _matrix(row, col);
438#else
439 (void) row;
440 return _matrix[col];
441#endif
442 }
443
444 inline bool matrix_row_sums_to_0(size_t row) {
445#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
446 return _matrix.row(row).sum() == 0;
447#else
448 (void) row;
449 return std::accumulate(_matrix.cbegin(), _matrix.cend(), 0) == 0;
450#endif
451 }
452
453 // letter_type i belongs to "preserve" if there exists a relation where
454 // the number of occurrences of i is not the same on both sides of the
455 // relation letter_type i belongs to "unique" if there is a relation
456 // where one side consists solely of i.
457 bool _empty_word;
458 detail::Duf<> _letter_components;
459 size_t _nr_gens;
460 size_t _nr_letter_components;
461 size_t _nr_relations;
462 bool _preserve_length;
463 std::vector<bool> _preserve;
464 std::vector<bool> _seen;
465 std::vector<bool> _unique;
466
467#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
468 Eigen::Matrix<int64_t, Eigen::Dynamic, Eigen::Dynamic> _matrix;
469#else
470 std::vector<int64_t> _matrix;
471#endif
472 };
473
495 template <typename Word>
498 if (p.alphabet().empty()) {
499 return false;
500 }
501 auto it
503
504 if (*it != p.alphabet().size() - 1) {
505 auto copy_p = p;
507 copy_p,
508 rx::seq<typename Presentation<Word>::letter_type>(0)
509 | rx::take(p.alphabet().size()) | rx::to_vector());
510 IsObviouslyInfinite ioi(copy_p.alphabet().size());
512 p.alphabet(), copy_p.rules.cbegin(), copy_p.rules.cend());
513 return ioi.result();
514 }
515
518 return ioi.result();
519 }
520
540 template <>
542
565 bool is_obviously_infinite(detail::ToddCoxeterImpl const& tc);
566
587 // This function is implemented in cong-class.tpp
588 template <typename Word>
589 bool is_obviously_infinite(Congruence<Word>& c);
590
612 template <typename Word>
613 bool is_obviously_infinite(Kambites<Word>& k) {
614 if (k.finished() && k.small_overlap_class() >= 3) {
615 return true;
616 }
618 return true;
619 }
620 return k.small_overlap_class() >= 3;
621 }
622
644 template <typename Rewriter, typename ReductionOrder>
645 bool
646 is_obviously_infinite(detail::KnuthBendixImpl<Rewriter, ReductionOrder>& kb) {
647 if (kb.finished()) {
649 }
650 auto const& p = kb.internal_presentation();
651 if (p.alphabet().empty()) {
652 return false;
653 }
654 IsObviouslyInfinite ioi(p.alphabet().size());
655 ioi.add_rules_no_checks(p.alphabet(), p.rules.cbegin(), p.rules.cend());
656 ioi.add_rules_no_checks(p.alphabet(),
657 kb.internal_generating_pairs().cbegin(),
658 kb.internal_generating_pairs().cend());
659 return ioi.result();
660 }
661
662} // namespace libsemigroups
663#endif // LIBSEMIGROUPS_OBVINF_HPP_
T accumulate(T... args)
T assign(T... args)
T begin(T... args)
Class for checking if a finitely presented semigroup or monoid is obviously infinite.
Definition obvinf.hpp:132
typename std::vector< std::pair< std::string, std::string > >::const_iterator const_iterator_pair_string
Alias for std::vector< std::pair<std::string, std::string>>::const_iterator.
Definition obvinf.hpp:147
IsObviouslyInfinite & add_rules_no_checks(word_type const &, const_iterator_word_type first, const_iterator_word_type last)
Add rules from iterators to word_type.
IsObviouslyInfinite(size_t n)
Construct from alphabet size.
IsObviouslyInfinite & add_rules_no_checks(char const *lphbt, typename std::vector< std::string >::const_iterator first, typename std::vector< std::string >::const_iterator last)
Add rules from iterators to std::vector of std::string.
Definition obvinf.hpp:318
IsObviouslyInfinite & add_rules_no_checks(std::string const &lphbt, const_iterator_pair_string first, const_iterator_pair_string last)
Add rules from iterators to std::pair of std::string.
IsObviouslyInfinite(IsObviouslyInfinite &&)=delete
Deleted.
IsObviouslyInfinite(std::string const &lphbt)
Construct from alphabet.
Definition obvinf.hpp:191
IsObviouslyInfinite & operator=(IsObviouslyInfinite const &)=delete
Deleted.
IsObviouslyInfinite & add_rules_no_checks(std::basic_string< Char > const &lphbt, typename std::vector< std::basic_string< Char > >::const_iterator first, typename std::vector< std::basic_string< Char > >::const_iterator last)
Add rules from iterators to std::string.
Definition obvinf.hpp:271
IsObviouslyInfinite & init(std::string const &lphbt)
Definition obvinf.hpp:209
IsObviouslyInfinite & add_rules_no_checks(std::basic_string< Char > const &lphbt, const_iterator_word_type first, const_iterator_word_type last)
Add rules from iterators to word_type.
Definition obvinf.hpp:346
typename std::vector< word_type >::const_iterator const_iterator_word_type
Alias for std::vector<word_type>::const_iterator.
Definition obvinf.hpp:139
typename std::vector< std::string >::const_iterator const_iterator_string
Alias for std::vector<std::string>::const_iterator.
Definition obvinf.hpp:151
IsObviouslyInfinite(IsObviouslyInfinite const &)=delete
Deleted.
IsObviouslyInfinite & init(size_t n)
bool result() const
Returns whether or not the finitely presented semigroup or monoid is obviously infinite.
IsObviouslyInfinite & operator=(IsObviouslyInfinite &&)=delete
Deleted.
For an implementation of presentations for semigroups or monoids.
Definition presentation.hpp:102
void throw_if_bad_alphabet_or_rules() const
Check if the alphabet and rules are valid.
Definition presentation.hpp:603
std::vector< word_type > rules
Data member holding the rules of the presentation.
Definition presentation.hpp:131
word_type const & alphabet() const noexcept
Return the alphabet of the presentation.
Definition presentation.hpp:183
typename word_type::value_type letter_type
Type of the letters in the words that constitute the rules of a Presentation object.
Definition presentation.hpp:109
bool finished() const
Check if run has been run to completion or not.
Class for converting strings to word_type with specified alphabet.
Definition word-range.hpp:773
T empty(T... args)
T end(T... args)
T fill(T... args)
size_t small_overlap_class()
Get the small overlap class.
Presentation< native_word_type > const & presentation() const noexcept
Get the presentation used to define a Kambites instance (if any).
Definition kambites-class.hpp:344
WordGraph< uint32_t > const & gilman_graph()
Return the Gilman WordGraph.
bool is_obviously_infinite(Presentation< Word > const &p)
Function for checking if the finitely presented semigroup or monoid defined by a Presentation object ...
Definition obvinf.hpp:496
std::vector< letter_type > word_type
Type for a word over the generators of a semigroup.
Definition types.hpp:99
T max_element(T... args)
Namespace for Presentation helper functions.
Definition obvinf.hpp:60
void change_alphabet(Presentation< Word > &, Word const &)
Change or re-order the alphabet.
bool is_acyclic(WordGraph< Node > const &wg)
Check if a word graph is acyclic.
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
T size(T... args)