Narrow Results

We study a novel representation of semiautomata, which is motivated by the method of trace-assertion specifications of software modules. Each state of the semiautomaton is represented by an arbitrary word leading to that state, the canonical word. The transitions of the semiautomaton give rise to a right congruence, the state-equivalence, on the set of input words of the semiautomaton: two words are state-equivalent if and only if they lead to the same state. We present a simple algorithm for finding a set of generators for state-equivalence. Directly from this set of generators, we construct a confluent prefix-rewriting system which permits us to transform any word to its canonical representative. In general, the rewriting system may allow infinite derivations. To address this issue, we impose the condition of prefix-continuity on the set of canonical words. A set is prefix-continuous if, whenever a word w and a prefix u of w are in the set, then all the prefixes of w longer than u are also in the set. Prefix-continuous sets include prefix-free and prefix-closed sets as special cases. We prove that the rewriting system is Noetherian if and only if the set of canonical words is prefix-continuous. Furthermore, if the set of canonical words is prefix-continuous, then the set of rewriting rules is irredundant. We show that each prefix-continuous canonical set corresponds to a spanning forest of the semiautomaton.

In the paper [1], Theorem 23 and Example 24 are incorrect. The corrected version is presented in this note.

Every tame, prime and alternating knot is equivalent to a tame, prime and alternating knot in regular position, with a common projection. In this work, we show that the augmented Dehn presentation of the knot group of a tame, prime, alternating knot in regular position, with a common projection has a finite and complete rewriting system. This provides an algorithm for solving the word problem with this presentation and we find an algorithm for solving the word problem with the Dehn presentation also.

In this paper we will present the results of Artin–Markov on braid groups by using the Gröbner–Shirshov basis. As a consequence we can reobtain the normal form of Artin–Markov–Ivanovsky as an easy corollary.

We consider a very simple Mealy machine (two nontrivial states over a two-symbol alphabet), and derive some properties of the semigroup it generates. It is an infinite, finitely generated semigroup, and we show that the growth function of its balls behaves asymptotically like ℓ^α, for ; that the semigroup satisfies the identity g⁶ = g⁴; and that its lattice of two-sided ideals is a chain.

Constructions that yield pseudorecursiveness in [I] (Int. J. Algebra Comput.6 (1996) 457–510) are extended in this article. Finitely based varieties of semigroups with increasingly strict expansions by additional unary operation symbols or individual constants are shown to have the pseudorecursive property: the equational theory is undecidable, but the subsets obtained by bounding the number of distinct variables are all recursive. The most stringent case considered here is the single unary operation or distinguished element. New techniques of stratified reducibility and interpretation via rewriting rules are employed to show the property inherits along a chain of theories. Pure semigroup varieties that are both finitely based and pseudorecursive will be discussed in a later paper.

A new pair of asymptotic invariants for finitely presented groups, called intrinsic and extrinsic tame filling functions, is introduced. These filling functions are quasi-isometry invariants that strengthen the notions of intrinsic and extrinsic diameter functions for finitely presented groups. We show that the existence of a (finite-valued) tame filling functions implies that the group is tame combable. Bounds on both intrinsic and extrinsic tame filling functions are discussed for stackable groups, including groups with a finite complete rewriting system, Thompson's group F, and almost convex groups.

In the general context of presentations of monoids, we study normalization process that are determined by their restriction to length-two words. Garside’s greedy normal forms and quadratic convergent rewriting systems, in particular those associated with the plactic monoids, are typical examples. Having introduced a parameter, called the class and measuring the complexity of the normalization of length-three words, we analyze the normalization of longer words and describe a number of possible behaviors. We fully axiomatize normalizations of class $(4,3)$, show the convergence of the associated rewriting systems, and characterize those deriving from a Garside family.

This paper determines relations between two notions concerning monoids: factorability structure, introduced to simplify the bar complex; and quadratic normalization, introduced to generalize quadratic rewriting systems and normalizations arising from Garside families. Factorable monoids are characterized in the axiomatic setting of quadratic normalizations. Additionally, quadratic normalizations of class $\left(4,3\right)$ are characterized in terms of factorability structures and a condition ensuring the termination of the associated rewriting system.

In this paper, we study the averaging operator by assigning a rewriting system to it. We obtain some basic results on the kind of rewriting system we used. In particular, we obtain a sufficient and necessary condition for the confluence. We supply the relationship between rewriting systems and Gröbner–Shirshov bases based on bracketed polynomials. As an application, we give a basis of the free unitary averaging algebra on a nonempty set.

The celebrated Diamond Lemma of Bergman gives an effectively verifiable criterion of uniqueness of normal forms for term rewriting in associative algebras. We revisit that result in the context of deformation theory and homotopical algebra; this leads to a new proof using multiplicative free resolutions. Specifically, our main result states that every such resolution of an algebra with monomial relations gives rise to its own Diamond Lemma, where Bergman’s condition of “resolvable ambiguities” is precisely the first nontrivial component of the Maurer–Cartan equation in the corresponding tangent complex. The same approach works for many other algebraic structures, emphasizing the relevance of computing resolutions of algebras with monomial relations.

In this paper, we obtain a complete rewriting system for monoid presentation of Schützenberger product of $n$ groups, which is firstly defined in [G. M. S. Gomes, H. Sezinando and J. E. Pin, Presentations of the Schützenberger product of $n$ groups, Comm. Algebra34(4) (2006) 1213–1235]. It gives an algorithm for getting normal form of elements and hence solving the word problem in this group.

We develop the theory of Gröbner bases on an algebra based on a well-ordered semigroup inspired by the discussions in Farkas et al.,^3,4 where the authors study multiplicative bases in an axiomatic way. We consider a reflexive semigroup with 0 equipped with a suitable well-order, and use it as a base of an algebra over a commutative ring, on which we develop a Gröbner basis theory.

Our framework is considered to be fairly general and unifies the existing Gröbner basis theories on several types of algebras (ref. ^1,6–10). We discuss a Gröbner basis theory from a view point of rewriting systems. We study behaviors of critical pairs in our situation and give a so-called critical pair theorem. We need to consider z-elements as well as usual critical pairs come from overlapping applications of rules.