2008/01/30 by Anil Ada, Ada, Anil · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0801.4777
Master's thesis, 93 pages
arxiv created 2008/01/30 · openalex publication_date 2008/01/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (\citeEil74) 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.