Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2013, Vol. 14 Issue (8): 623-633    DOI: 10.1631/jzus.C1200349
    
Application of formal languages in polynomial transformations of instances between NP-complete problems
Jorge A. Ruiz-Vanoye, Joaquín Pérez-Ortega, Rodolfo A. Pazos Rangel, Ocotlán Díaz-Parra, Héctor J. Fraire-Huacuja, Juan Frausto-Solís, Gerardo Reyes-Salgado, Laura Cruz-Reyes
DACI, Universidad Autónoma del Carmen, Cd. del Carmen 24180, Mexico; Computer Science, Centro Nacional de Investigación y Desarrollo Tecnológico, Cuernavaca 62490, Mexico; Systems and Computer Science, Instituto Tecnológico de Ciudad Madero, Ciudad Madero 89440, Mexico; Informatics, Universidad Politécnica del Estado de Morelos, Jiutepec 62560, Mexico; Computer Science, Instituto Tecnológico de Cuautla, Cuautla 62745, Mexico
Application of formal languages in polynomial transformations of instances between NP-complete problems
Jorge A. Ruiz-Vanoye, Joaquín Pérez-Ortega, Rodolfo A. Pazos Rangel, Ocotlán Díaz-Parra, Héctor J. Fraire-Huacuja, Juan Frausto-Solís, Gerardo Reyes-Salgado, Laura Cruz-Reyes
DACI, Universidad Autónoma del Carmen, Cd. del Carmen 24180, Mexico; Computer Science, Centro Nacional de Investigación y Desarrollo Tecnológico, Cuernavaca 62490, Mexico; Systems and Computer Science, Instituto Tecnológico de Ciudad Madero, Ciudad Madero 89440, Mexico; Informatics, Universidad Politécnica del Estado de Morelos, Jiutepec 62560, Mexico; Computer Science, Instituto Tecnológico de Cuautla, Cuautla 62745, Mexico
 全文: PDF 
摘要： We propose the usage of formal languages for expressing instances of NP-complete problems for their application in polynomial transformations. The proposed approach, which consists of using formal language theory for polynomial transformations, is more robust, more practical, and faster to apply to real problems than the theory of polynomial transformations. In this paper we propose a methodology for transforming instances between NP-complete problems, which differs from Garey and Johnson’s. Unlike most transformations which are used for proving that a problem is NP-complete based on the NP-completeness of another problem, the proposed approach is intended for extrapolating some known characteristics, phenomena, or behaviors from a problem A to another problem B. This extrapolation could be useful for predicting the performance of an algorithm for solving B based on its known performance for problem A, or for taking an algorithm that solves A and adapting it to solve B.
关键词： Formal languages;  Polynomial transformations;  NP-completeness    
Abstract: We propose the usage of formal languages for expressing instances of NP-complete problems for their application in polynomial transformations. The proposed approach, which consists of using formal language theory for polynomial transformations, is more robust, more practical, and faster to apply to real problems than the theory of polynomial transformations. In this paper we propose a methodology for transforming instances between NP-complete problems, which differs from Garey and Johnson’s. Unlike most transformations which are used for proving that a problem is NP-complete based on the NP-completeness of another problem, the proposed approach is intended for extrapolating some known characteristics, phenomena, or behaviors from a problem A to another problem B. This extrapolation could be useful for predicting the performance of an algorithm for solving B based on its known performance for problem A, or for taking an algorithm that solves A and adapting it to solve B.
Key words: Formal languages    Polynomial transformations    NP-completeness
收稿日期: 2012-12-03 出版日期: 2013-08-02
CLC:  TP301.5  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Jorge A. Ruiz-Vanoye
Joaquín Pérez-Ortega
Rodolfo A. Pazos Rangel
Ocotlán Díaz-Parra
Héctor J. Fraire-Huacuja
Juan Frausto-Solís
Gerardo Reyes-Salgado
Laura Cruz-Reyes

引用本文:

Jorge A. Ruiz-Vanoye, Joaquín Pérez-Ortega, Rodolfo A. Pazos Rangel, Ocotlán Díaz-Parra, Héctor J. Fraire-Huacuja, Juan Frausto-Solís, Gerardo Reyes-Salgado, Laura Cruz-Reyes. Application of formal languages in polynomial transformations of instances between NP-complete problems. Front. Inform. Technol. Electron. Eng., 2013, 14(8): 623-633.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/jzus.C1200349    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2013/V14/I8/623

No related articles found!