Polynomial time multiplication and normal forms in free bands

DOI10.1016/j.tcs.2023.113783OpenAlexW4321766276MaRDI QIDQ2693634

Yanyan Li

Publication date: 24 March 2023

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

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

zbMATH Keywords

complexityalgorithmsword problemtransducersfree bandsminimal word representatives

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• OEIS
• Semigroups
• pybind11

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal algorithm for computing the repetitions in a word
• A Noetherian and confluent rewrite system for idempotent semigroups
• Minimisation of acyclic deterministic automata in linear time
• Band monoid languages revisited
• Homogeneous bands
• Computing finite semigroups
• Trees, band monoids and formal languages
• The lattice of equational classes of idempotent semigroups
• All varieties of bands
• Varieties of idempotent semigroups
• Rewriting in Varieties of Idempotent Semigroups
• Efficient Testing of Equivalence of Words in a Free Idempotent Semigroup
• THE QUIVER OF THE SEMIGROUP ALGEBRA OF A LEFT REGULAR BAND
• Varieties of Bands Revisited
• Algorithms for computing finite semigroups
• EVERY GROUP IS A MAXIMAL SUBGROUP OF THE FREE IDEMPOTENT GENERATED SEMIGROUP OVER A BAND
• Cell complexes, poset topology and the representation theory of algebras arising in algebraic combinatorics and discrete geometry
• A practical method for enumerating cosets of a finite abstract group

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