Randomized algorithm approach for solving PCP
Journal Title: International Journal on Computer Science and Engineering - Year 2012, Vol 4, Issue 1
Abstract
Post Correspondence Problem is an undecidable problem that was introduced by Emil Post and is often used in proofs of undecidability. No efficient nondeterministic solution to the problem exists. The paper intends to present a nondeterministic solution to the above problem. The proposed work has been tested for some constrained inputs and the results were encouraging. The paper also discusses the application of genetic algorithms to the solution and the requisite analysis. The approach presents an Artificial Intelligence based solution to a problem which is used in theoretical computer science for proving purposes and can be extended to solve many non deterministic problems.
Authors and Affiliations
Harsh Bhasin , Nishant Gupta
Keywords
Related Articles
- EP ID EP129831
- DOI -
- Views 106
- Downloads 0
Fingertip Detection for Hand Pose Recognition
In this paper, a novel algorithm is proposed for fingertip detection and finger type recognition. The algorithm is applied for locating fingertips in hand region extracted by Bayesian rule based skin color segmentation....
Context Ontology Construction For Cricket Video
Content based video retrieval systems are not complete in semantic sense. To improve the efficiency and the effectiveness of the retrieval system the content based retrieval systems must be equipped with the semantic bas...
Enhancing Security Of Agent-Oriented Techniques Programs Code Using Jar Files
Agent-oriented techniques characterize an exciting new way of analyzing, designing and building complex software systems in real time world. These techniques have the prospective to significantly improve current practice...
Step Counting Using Smartphone-Based Accelerometer
This paper presents a method for counting the number of steps taken by a user, while walking at any variable speed, using smartphone-based accelerometer. For this purpose, the steps are detected based on a relation betwe...
Investigating the performance improvement by sampling techniques in EEG data
In this paper the performance of oversampling methods such as SMOTE (Synthetic Minority Over-sampling Technique) and PCA (Principal Component Analysis) which are used for preprocessing are applied for the Brain computer...