Polynomial time multiplication and normal forms in free bands

DOI10.1016/J.TCS.2023.113783MaRDI QIDQ2693634zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 24 March 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

algorithmscomplexityfree bandsminimal word representativestransducersword problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Free bands and free *-bands
• The word problem in regular band free products
• Normal forms for band free products
• On free products of bands
• The word problem for free adequate semigroups.

Cites work

• A Noetherian and confluent rewrite system for idempotent semigroups
• A practical method for enumerating cosets of a finite abstract group
• Algorithms for computing finite semigroups
• All varieties of bands
• An optimal algorithm for computing the repetitions in a word
• Band monoid languages revisited
• Cell complexes, poset topology and the representation theory of algebras arising in algebraic combinatorics and discrete geometry
• Computing finite semigroups
• Efficient testing of equivalence of words in a free idempotent semigroup
• Every group is a maximal subgroup of the free idempotent generated semigroup over a band.
• Homogeneous bands
• scientific article; zbMATH DE number 789816 (Why is no real title available?)
• scientific article; zbMATH DE number 3217047 (Why is no real title available?)
• scientific article; zbMATH DE number 3071073 (Why is no real title available?)
• Minimisation of acyclic deterministic automata in linear time
• Rewriting in varieties of idempotent semigroups
• The lattice of equational classes of idempotent semigroups
• THE QUIVER OF THE SEMIGROUP ALGEBRA OF A LEFT REGULAR BAND
• Trees, band monoids and formal languages
• Varieties of Bands Revisited
• Varieties of idempotent semigroups

Cited in

(2)

• Normal forms for band free products
• Polynomial time multiplication and normal forms in free bands

Describes a project that uses

Uses Software

• pybind11
• Semigroups
• OEIS

This page was built for publication: Polynomial time multiplication and normal forms in free bands

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