SDSU Department of Computer Science
  
Home Contact Us Undergraduate Student Info Graduate Student Info Faculty & Staff News & Events
News Calendar Problem of the Fortnight

October 2009 Calendar

CS Masters' Thesis Defense

Title: Web-Accessible 3D Visualization of Partition Lattices Arising from PCP2 Adjacency Relations
Speaker: Sitara Gottipati
Date: Wednesday, October 21, 2009
Time: 3:00 p.m.
Location: GMCS 405
Thesis advisor: William Root

Abstract:
Although the Post Correspondence Problem (PCP) is known to be undecidable in general, certain minor restrictions on the problem’s conditions yield decidable variants. The decision problem obtained by restricting PCP to homomorphisms with domain cardinality k is denoted “PCPk”. Currently it is known that PCPk is undecidable for k > 6 and decidable for k < 3, but the decidability question has not yet been resolved for 3 <= k <= 6. In particular, the methods used by Karhumaki, Ehrenfeucht and Rozenberg in their 1982 proof of the decidability of PCP2 and in a subsequent improved proof in 2000 by Halava, Harju and Hirvensalo, have not proven applicable to resolving the decidability question for PCP3, which remains open. For this reason, alternative approaches to proving the decidability of PCP2 remain of interest. Recently an alternative approach based on reformulating the PCP2 decision problem in terms of a lattice of partitions induced by adjacency relations arising from each PCP2 problem instance has been suggested. This thesis project encompassed the design and implementation of web-hosted software for providing feature-rich 3D visualizations of such partition lattices.
webmaster@cs.sdsu.edu page counter College of Sciences