23#ifndef LIBSEMIGROUPS_OBVINF_HPP_
24#define LIBSEMIGROUPS_OBVINF_HPP_
35#include "word-graph.hpp"
36#include "word-range.hpp"
38#include "detail/eigen.hpp"
39#include "detail/uf.hpp"
42#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
45 template <
typename Rewriter,
typename ReductionOrder>
46 class KnuthBendixImpl;
47 class ToddCoxeterImpl;
50 template <
typename Word>
53 template <
typename Word>
56 template <
typename Word>
61 template <
typename Word>
132 class IsObviouslyInfinite {
135 IsObviouslyInfinite() =
default;
180 IsObviouslyInfinite&
init(
size_t n);
192 : IsObviouslyInfinite(lphbt.size()) {}
220 IsObviouslyInfinite&
operator=(IsObviouslyInfinite
const&) =
delete;
223 IsObviouslyInfinite&
operator=(IsObviouslyInfinite&&) =
delete;
225 ~IsObviouslyInfinite();
270 template <
typename Char>
275#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
276 auto matrix_start = _matrix.rows();
277 _matrix.conservativeResize(matrix_start + (last - first) / 2,
279 _matrix.block(matrix_start, 0, (last - first) / 2, _matrix.cols())
282 auto matrix_start = 0;
283 std::fill(_matrix.begin(), _matrix.end(), 0);
288 for (
auto it = first; it < last; ++it) {
291 private_add_rule(matrix_start + (it - first) / 2, lhs, rhs);
293 _nr_letter_components = _letter_components.number_of_blocks();
344 template <
typename Char>
349#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
350 auto matrix_start = _matrix.rows();
351 _matrix.conservativeResize(matrix_start + (last - first) / 2,
353 _matrix.block(matrix_start, 0, (last - first) / 2, _matrix.cols())
356 auto matrix_start = 0;
357 std::fill(_matrix.begin(), _matrix.end(), 0);
363 for (
auto it = first; it < last; ++it) {
365 tmp.
assign(it->begin(), it->end());
369 tmp.
assign(it->begin(), it->end());
371 private_add_rule(matrix_start + (it - first) / 2, lhs, rhs);
373 _nr_letter_components = _letter_components.number_of_blocks();
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;
427 inline void plus_letters_in_word(
size_t row,
word_type const& w) {
428 letters_in_word(row, w, 1);
431 inline void minus_letters_in_word(
size_t row,
word_type const& w) {
432 letters_in_word(row, w, -1);
435 inline int64_t& matrix(
size_t row,
size_t col) {
436#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
437 return _matrix(row, col);
444 inline bool matrix_row_sums_to_0(
size_t row) {
445#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
446 return _matrix.row(row).sum() == 0;
458 detail::Duf<> _letter_components;
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;
467#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
468 Eigen::Matrix<int64_t, Eigen::Dynamic, Eigen::Dynamic> _matrix;
470 std::vector<int64_t> _matrix;
495 template <
typename Word>
588 template <
typename Word>
612 template <
typename Word>
644 template <
typename Rewriter,
typename ReductionOrder>
650 auto const& p = kb.internal_presentation();
651 if (p.alphabet().empty()) {
657 kb.internal_generating_pairs().
cbegin(),
658 kb.internal_generating_pairs().
cend());
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
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
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