Message Boards Message Boards


[WSS16] Computational analysis of monoids and protogroup grammars

Posted 3 years ago
0 Replies
0 Total Likes

Project description:

Lambek (1999) introduced a new computational method for deciding whether an sentence in a natural language is grammatical. In his method sentences are modeled as elements of mathematical structures called pregroups. A pregroup is a monoid with an extra structure which is based on a partial order over its elements and a set of rules for how pregroup element multiplication relates to the partial order. Lambek used infinite pregroups.

My project started with the enumeration of all possible multiplication tables for a set of size m=1,2,3,4. Then I developed functions to check how many of these multiplication tables correspond to a monoid. A monoid (S,[CenterDot]) is an algebraic structure consisting of a set S which is closed under a binary associative operation [CenterDot] and contains a unique identity element. In order to get the total number of non-isomorphic monoids for a certain size I had to make sure that isomorphic monoids were not counted twice. The next step was to add more axioms to the definition of monoids and arrive at the definition of pregroups. A pregroup is a quintuple (S, [CenterDot], <=, l, r) consisting of a set S, a binary operation [CenterDot], a binary relation <= and two unary operations l,r. After my search for pregroups it turned out that there aren't any pregroups of size 1,2,3,4 which have non-trivial order. Based on this observation we stated 4 lemmas which say that all finite pregroups are groups with trivial order. After arriving at this conclusion I decided to use protogroups to construct grammars. A protogroup is a quintuple (S, [CenterDot], <=, l, r), which satisfies less axioms than a pregroup but they can as well be used to construct grammars. I studied protogroup grammars which model the process of determining whether a sequence of words is grammatically correct or not.

Monoid 4096 which is a protogroup with trivial order.

enter image description here

Monoid 2984516430 as a Cellular Automaton.

enter image description here

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract