The word problem of a finitely generated group is commonly defined to be a formal language over a finite generating set. The class of finite groups has been characterised as the class of finitely generated groups that have word problem decidable by a finite state automaton. We give a natural generalisation of the notion of word problem from finitely generated groups to finitely generated semigroups by considering relations of strings. We characterise the class of finite semigroups by the class of finitely generated semigroups whose word problem is decidable by finite state automata. We then examine the class of semigroups with word problem decidable by asynchronous two tape finite state automata. Algebraic properties of semigroups in this class are considered, towards an algebraic characterisation. We take the next natural step to further extend the classes of semigroups under consideration to semigroups that have word problem decidable by a finite collection of asynchronous automata working independently. A central tool used in the derivation of structural results are so-called iteration lemmas. We define a hierarchy of the considered classes of semigroups and connect our original results with previous research.

published_or_final_version / Mathematics / Master / Master of Philosophy

published_or_final_version / Computer Science / Master / Master of Philosophy

No description available.

No description available.

Thesis (M.Eng.(Mechanical Engineering)--University of Pretoria, 2001. / Summaries in Afrikaans and English. Includes bibliographical references.

Thesis (M. Phil.)--University of Hong Kong, 1994. / Includes bibliographical references (leaves 100-101).

Thesis (Ph.D)--Computing, Georgia Institute of Technology, 2010. / Committee Chair: Ramachandran, Umakishore; Committee Member: Clark, Nathan; Committee Member: Haskin, Roger; Committee Member: Pu, Calton; Committee Member: Rehg, James. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Thesis (Ph. D.)--Ohio State University, 1986. / Includes bibliographical references (leaves 166-170). Available online via OhioLINK's ETD Center

Master of Science / Department of Computer Science / Daniel Andresen / Modern techniques for simulating granular matter can produce excellent quality simulations, but usually involve a great enough performance cost to render them ineffective for real time applications. This leaves something to be desired for low-cost systems and interactive simulations which are more forgiving to inaccurate simulations, but much more strict in regards to the performance of the simulation itself. What follows is a proposal for a method of simulating granular matter that could potentially support millions of particles and several types for each particle while maintaining acceptable frame rates on consumer level hardware. By leveraging the power of consumer level graphics cards, effective data representation, and a model built around Cellular Automata a simulation can be run in real time.