The finite basis problem for words with at most two non-linear variables.

DOI10.1007/S00233-016-9799-4MaRDI QIDQ305772zbMATH OpenOpenAlexFDO

Authors Olga Sapir

Publication date 30 August 2016

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.6430

zbMATH Keywords

bases of identitiesalphabetsfinite basis problemfinitely based monoidsfree monoidsinherently non-finitely based monoidsisotermsRees quotientssemigroup identitiessemigroup varieties

Mathematics Subject Classification ID

Combinatorics on words (68R15) Free semigroups, generators and relations, word problems (20M05) Varieties and pseudovarieties of semigroups (20M07)

Abstract: Let A be an alphabet and W be a set of words in the free monoid A*. Let S(W) denote the Rees quotient over the ideal of A* consisting of all words that are not subwords of words in W. We call a set of words W finitely based if the monoid S(W) is finitely based. We find a simple algorithm that recognizes finitely based words among words with at most two non-linear variables. We also describe syntactically all hereditary finitely based monoids of the form S(W).

Recommendations

• On the finite basis problem for certain 2-limited words.
• Finitely based, finite sets of words
• FINITELY BASED WORDS
• scientific article; zbMATH DE number 1668759
• scientific article; zbMATH DE number 1899886

Cites work

• scientific article; zbMATH DE number 1668759 (Why is no real title available?)
• scientific article; zbMATH DE number 4023572 (Why is no real title available?)
• scientific article; zbMATH DE number 3654376 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• Bases for equational theories of semi-groups
• FINITELY BASED WORDS
• Finitely based monoids.
• Finitely based sets of 2-limited block-2-simple words
• Finitely based, finite sets of words
• Finiteness properties of varieties and the restriction to finite algebras.
• INHERENTLY NONFINITELY BASED FINITE SEMIGROUPS
• Maximal Specht varieties of monoids.
• Non-finitely based monoids.
• On the axiomatic rank of varieties generated by a semigroup or monoid with one defining relation
• On the finite basis problem for certain 2-limited words.
• PROBLEMS OF BURNSIDE TYPE AND THE FINITE BASIS PROPERTY IN VARIETIES OF SEMIGROUPS
• Polyhedral convex cones and the equational theory of the bicyclic semigroup
• TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
• The finite basis problem for finite semigroups
• The finite basis problem for the monoid of two-by-two upper triangular tropical matrices

Cited in

(10)

• Lee monoids are nonfinitely based while the sets of their isoterms are finitely based
• Varieties of monoids with complex lattices of subvarieties
• FINITELY BASED WORDS
• Finitely based monoids.
• Non-finitely based monoids.
• Finitely and non-finitely related words
• Classification of finitely based words in a class of words over a 3-letter alphabet.
• On the finite basis problem for certain 2-limited words.
• Finitely based sets of 2-limited block-2-simple words
• Deciding whether a finite set of words has rank at most two

This page was built for publication: The finite basis problem for words with at most two non-linear variables.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q305772)