-------------------------------------------------------------------------------
*** Note Day and Time ***                             *** Note Day and Time ***
-------------------------------------------------------------------------------
                                       
                                       
		   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
                                       
		       Tuesday, February 7, 1995
                                       
			     Janis Barzdins
				 9:30am
		       (Coffee served at 9:00am)
                                       
			       ** AND **

			    Rusins Freivalds
				11:00am
		       (Coffee served at 10:30am)

			 Seminar Room / MCS 135
                                       

-------------------------------------------------------------------------------
    TOWARDS EFFICIENT INDUCTIVE SYNTHESIS FROM INPUT/OUTPUT EXAMPLES
			     Janis Barzdins
  Institute of Mathematics and Computer Science, University of Latvia
				 9:30am
 

  We will begin with recursive - theoretic approach to Inductive
  Synthesis.  Then more practical approaches will be considered.
  Inductive Synthesis method based on finding local regularities
  (algebraic axioms) will be discussed. Special attention will be paid to
  the synthesis of expressions from input/output examples.  Efficient
  Inductive Synthesis algorithm will be presented. Corresponding computer
  experiments will be described. At the conclusion efficient Inductive
  Synthesis of Term Rewriting Systems will be considered, including
  computer experiments. Our conclusion will say that the synthesis of
  nontrivial functions and algorithms in a realistic time, entirely from
  input/output examples, is not a hopeless task.


    LOWER BOUNDS OF SPACE AND TIME COMPLEXITY OF RANDOMIZED MACHINES
			   Rusins  Freivalds
			  University of Latvia
				11:00am

  Randomized and deterministic multi-tape 2-way Turing machines are
  considered.  Separation theorems are proved for all constructible space
  functions of Monte Carlo multi-tape 2-way Turing machines. For instance,
  palindromes cannot be recognized by these machines in space less than
  log n. Another example is a language recognized by these machines in
  space log-star (n) but not in space inverse Ackermann function.

  Similar separation theorems are proved for all constructible time
  functions of n + f(n) type for Monte Carlo multi-tape 2-way Turing
  machines. In these theorems f(n) is linear or sublinear. There is a
  language recognizable by a deterministic machine in (1+e)n time but not
  recognizable by a Monte Carlo multi-tape 2-way Turing machine in n+ o(n)
  time. If g(n) is o(h(n)) then there is a language recognizable by a
  deterministic machine in n+h(n) time but not recognizable by a Monte
  Carlo machine in n+g(n) time.

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