Regular binoid expressions and regular binoid languages

Kosaburo Hashiguchi, Yoshito Wada, Shuji Jimbo

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


A bisemigroup consists of a set of elements and two associative operations. A bimonoid is a bisemigroup which has an identity to each associative operation. A binoid is a bimonoid which has the same identity to the two associative operations. In a previous paper, we introduced these three notions, and studied formal languages over free binoids (which are subsets of a free binoid where any element of a free binoid is denoted by its standard form which is a sequence of symbols). In this paper, we introduce a class of expressions called regular binoid expressions and show that any binoid language denoted by a regular binoid expression can be regarded to be a set of the standard forms of elements of a free binoid which can be recognized as a regular (monoid) language.

Original languageEnglish
Pages (from-to)291-313
Number of pages23
JournalTheoretical Computer Science
Issue number1-3
Publication statusPublished - Jul 28 2003
Externally publishedYes


  • Binoids
  • Regular binoid expressions
  • Regular languages
  • Right linear grammars

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Regular binoid expressions and regular binoid languages'. Together they form a unique fingerprint.

Cite this