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.

Thesis (M.S.)--Ohio University, August, 2000. / Title from PDF t.p.

Thesis--University of North Carolina. / Photocopy of type-script. Bibliography: leaves [143]-146.

Thesis--Massachusetts Institute of Technology. / Vita. Bibliography: p. 235-236.

by David A. Castanon, Bernard C. Levy, Stanley B. Gershwin. / "August, 1982." / Bibliography: leaf [2]

Ph.D. (Computer Science) / Traditionally a formal language can be characterized in two ways: by a generative device (a grammar) and an acceptive device (an automaton). The characterization of two- and three-dimensional Random Context Grammars by two- and three-dimensional Random Context Automata are investigated. This thesis is an attempt to progressively extend a certain class of grammars to higher dimensions where the class of languages generated in each dimension is contained in the class of languages generated in the next higher dimension. Random Context Array Automata which characterizes Random Context Array Grammars (Von Solms [4,5]) are defined. The power of both Random Context Array Grammars and Random Context Array Automata is inherent in the fact that the replacement of symbols in figures is subject to horizontal, vertical and global context. A proof is given for the equivalence of the class of languages generated by Random Context Array Grammars and the class of languages accepted by Random Context Array Automata. The two-dimensional Random Context Array Grammars are extended to three dimensions. Random Context Structure Grammars generate three-dimensional structures. A characteristic of Random Context Structure Grammars is that the replacement of symbols in a structure is subject to seven relevant contexts. Random Context Structure Automata which characterize Random Context Structure Grammars are defined. It is shown that the class of languages generated by Random Context Structure Grammars are equivalent to the class of languages accepted by Random Context Array Automata...

D.Phil. (Computer Science) / Please refer to full text to view abstract

Please read the abstract in the section 00front of this document / Dissertation (MSc (Computer Science))--University of Pretoria, 2003. / Computer Science / unrestricted

This thesis presents a Finite State Machine (FSM) Synthesizer developed at Portland State University. The synthesizer starts from a high level behavioral description, in which no states are specified, and generates the lower level FSM descriptions for simulation and physical layout generation.

A complete program to ease the task of large scale Finite State Machine (FSM) minimization presented in this thesis: TDFM (Two Dimensional FSM Minimizer), is a part of the DIADES system. DIADES is an Automatic Design Synthesis System whose development in the Department of Electrical Engineering at Portland State University is supported in part by a research grant from SHARP Microelectronics Technology.