𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Regular binoid expressions and regular binoid languages

✍ Scribed by Kosaburo Hashiguchi; Yoshito Wada; Shuji Jimbo

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
285 KB
Volume
304
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

Rewriting of Regular Expressions and Reg
Rewriting of Regular Expressions and Regular Path Queries
✍ Diego Calvanese; Giuseppe De Giacomo; Maurizio Lenzerini; Moshe Y. Vardi πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 189 KB

Recent work on semi-structured data has revitalized the interest in path queries, i.e., queries that ask for all pairs of objects in the database that are connected by a path conforming to a certain specification, in particular to a regular expression. Also, in semi-structured data, as well as in da

Squares of regular languages
Squares of regular languages
✍ Gerhard Lischke πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 127 KB

The square of a language L is the set of all words pp where p ∈ L. The square of a regular language may be regular too or context-free or none of both. We give characterizations for each of these cases and show that it is decidable whether a regular language has one of these properties.