knuth-bendix-helpers.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2024-2025 James D. Mitchell + Maria Tsalakou
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
 
// This file contains the helpers for the KnuthBendix class template.
 
#ifndef LIBSEMIGROUPS_KNUTH_BENDIX_HELPERS_HPP_
#define LIBSEMIGROUPS_KNUTH_BENDIX_HELPERS_HPP_
 
#include <cstddef>      // for size_t
#include <iterator>     // for distance
#include <stack>        // for stack
#include <string>       // for basic_string, string
#include <type_traits>  // for is_same_v
#include <utility>      // for move
#include <vector>       // for vector
 
#include "cong-common-helpers.hpp"  // for partition, add_gener...
#include "constants.hpp"            // for UNDEFINED, POSITIVE_...
#include "debug.hpp"                // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"            // for LIBSEMIGROUPS_EXCEPTION
#include "knuth-bendix-class.hpp"   // for KnuthBendix
#include "paths.hpp"                // for Paths
#include "presentation.hpp"         // for Presentation
#include "ranges.hpp"               // for seq, input_range_ite...
#include "types.hpp"                // for congruence_kind, wor...
#include "word-graph-helpers.hpp"   // for word_graph
#include "word-graph.hpp"           // for WordGraph
#include "word-range.hpp"           // for ToString
 
#include "detail/fmt.hpp"              // for format
#include "detail/knuth-bendix-nf.hpp"  // for KnuthBendix, KnuthBe...
#include "detail/rewriters.hpp"        // for internal_string_type
 
namespace libsemigroups {
 
  namespace congruence_common {
    // Interface helpers - normal_forms

    template <typename Word, typename Rewriter, typename ReductionOrder>
    [[nodiscard]] auto
    normal_forms(KnuthBendix<Word, Rewriter, ReductionOrder>& kb) {
      return detail::KnuthBendixNormalFormRange<Word, Rewriter, ReductionOrder>(
          kb);
    }

    // Interface helpers - non_trivial_classes

    template <typename Word, typename Rewriter, typename ReductionOrder>
    [[nodiscard]] std::vector<std::vector<Word>>
    non_trivial_classes(KnuthBendix<Word, Rewriter, ReductionOrder>& kb1,
                        KnuthBendix<Word, Rewriter, ReductionOrder>& kb2);
 
  }  // namespace congruence_common


  namespace knuth_bendix {

    // KnuthBendix specific helpers

    template <typename Word, typename Rewriter, typename ReductionOrder>
    void by_overlap_length(KnuthBendix<Word, Rewriter, ReductionOrder>& kb);

#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    template <typename Rewriter, typename ReductionOrder>
    [[nodiscard]] bool
    is_reduced(detail::KnuthBendixImpl<Rewriter, ReductionOrder>& kb);
#else
    template <typename Word, typename Rewriter, typename ReductionOrder>
    [[nodiscard]] bool
    is_reduced(KnuthBendix<Word, Rewriter, ReductionOrder>& kb);
#endif

    // Interface helpers - add_generating_pair
 
    using congruence_common::add_generating_pair;
    using congruence_common::add_generating_pair_no_checks;

    // Interface helpers - contains
 
    using congruence_common::contains;
    using congruence_common::contains_no_checks;
    using congruence_common::currently_contains;
    using congruence_common::currently_contains_no_checks;

    // Interface helpers - reduce
 
    using congruence_common::reduce;
    using congruence_common::reduce_no_checks;
    using congruence_common::reduce_no_run;
    using congruence_common::reduce_no_run_no_checks;

    // Interface helpers - normal_forms
 
    using congruence_common::normal_forms;

    // Interface helpers - partition
 
    using congruence_common::partition;

    // Interface helpers - non_trivial_classes
 
    using congruence_common::non_trivial_classes;

    // Possible future interface helpers - redundant_rule

    template <typename Word, typename Time>
    [[nodiscard]] typename std::vector<Word>::const_iterator
    redundant_rule(Presentation<Word> const& p, Time t);
 
  }  // namespace knuth_bendix
}  // namespace libsemigroups
 
#include "knuth-bendix-helpers.tpp"
#endif  // LIBSEMIGROUPS_KNUTH_BENDIX_HELPERS_HPP_