The notion of communication complexity was introduced by Yao in his seminal paper [Yao79]. In [BFS86], Babai Frankl and Simon developed a rich structure of communication complexity classes to understand the relationships between various models of communication complexity. This made it apparent that communication complexity was a self-contained mini-world within complexity theory. In this thesis, we study the place of regular languages within this mini-world. In particular, we are interested in the non-deterministic communication complexity of regular languages. / We show that a regular language has either O(1) or O(log n) non-deterministic complexity. We obtain several linear lower bound results which cover a wide range of regular languages having linear non-deterministic complexity. These lower bound results also imply a result in semigroup theory: we obtain sufficient conditions for not being in the positive variety Pol(Com). / To obtain our results, we use algebraic techniques. In the study of regular languages, the algebraic point of view pioneered by Eilenberg ([Eil74]) has led to many interesting results. Viewing a semigroup as a computational device that recognizes languages has proven to be prolific from both semigroup theory and formal languages perspectives. In this thesis, we provide further instances of such mutualism.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.112367 |
| Date | January 2007 |
| Creators | Ada, Anil. |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science.) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | alephsysno: 002710951, proquestno: AAIMR51056, Theses scanned by UMI/ProQuest. |
Page generated in 0.002 seconds