Computer Science – Computational Complexity
Scientific paper
2008-01-30
Computer Science
Computational Complexity
Master's thesis, 93 pages
Scientific paper
In this thesis, we study the place of regular languages within the communication complexity setting. 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 Omega(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 (\cite{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.
No associations
LandOfFree
Non-Deterministic Communication Complexity of Regular Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Non-Deterministic Communication Complexity of Regular Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-Deterministic Communication Complexity of Regular Languages will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-203816