-------------------------------------------------------------------------------
                                       
                                       
		   B O S T O N   U N I V E R S I T Y
                                       
		      Computer Science Department
                                       
			  C O L L O Q U I U M
                                       
		       Wednesday March 22, 1995
                                       
				 3:00pm
		       (Coffee served at 2:30pm)
                                       
			 Seminar Room / MCS 135
                                       

-------------------------------------------------------------------------------

		  Learning Real Time Infinite Automata
			       Amr Fahmy
			   Harvard University
 				    
  A real time acceptor is a pair of state machines, a control structure C
  and a data structure D. The data structure, defined as a state machine,
  usually has an infinite number of states while the controller has a
  finite number of states. The behavior of an acceptor is a state machine,
  B, that is infinite if the data structure is infinite, which accepts the
  same language as the acceptor. We show that L(B) = L(C \times D) where C
  \times D is the "cross product" state machine of C and D. We also show
  that both the state diagrams of C and D are "mirrored" in the state
  digram of B.  Using an algebraic theory for decomposing finite state
  machines we show how to decompose B back in to C and D.

  We present a learning algorithm for real time languages that identifies
  the language in the limit. The learning algorithm is presented with a
  truncated behavior which it attempts to decompose into a complete
  controller and partial data structure.  Learning is accomplished when
  the partial data structure, which results from the decomposition, is
  replaced with a complete one thus extending the partial
  behavior. Several examples of the learning process using several data
  structures will be presented. Recent results pertaining to the efficient
  learning of one counter automata will also be presented.

Host: Prof. Abdelsalam Heddaya
-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
   For more information contact Prof. Mark Crovella <crovella@bu.edu>
-------------------------------------------------------------------------------