On the theory of patching. Pap, Z., Csopaki, G., & Dibuz, S. In Third IEEE International Conference on Software Engineering and Formal Methods (SEFM'05), pages 263–271, September, 2005. ISSN: 2160-7656doi abstract bibtex We study the problem of patching, i.e., modifying the behavior of an existing system. We consider systems modelled as finite state machines (FSMs), and define edit operators for them based on a traditional fault model. We argue that sequences of edit operations can be considered as models of patches defining modifications to an FSM system. We utilize recent results in graph matching theory as mathematical foundations. We introduce a new type of problem which we call the optimal patch or optimal update problem: given an FSM M modeling the behavior of an existing system and an other machine M' modeling a new design, find an optimal patch, i.e., the edit operations changing M to M' that are minimal according to a given cost function associated with the edit operations. We analyze the complexity of the problem, and conclude that it is unlikely to have a polynomial time solution for it. We also show that the problem can be easily transformed to a state-space search problem, for which many heuristic approximation algorithms have been developed.
@inproceedings{pap_theory_2005,
title = {On the theory of patching},
doi = {10.1109/SEFM.2005.31},
abstract = {We study the problem of patching, i.e., modifying the behavior of an existing system. We consider systems modelled as finite state machines (FSMs), and define edit operators for them based on a traditional fault model. We argue that sequences of edit operations can be considered as models of patches defining modifications to an FSM system. We utilize recent results in graph matching theory as mathematical foundations. We introduce a new type of problem which we call the optimal patch or optimal update problem: given an FSM M modeling the behavior of an existing system and an other machine M' modeling a new design, find an optimal patch, i.e., the edit operations changing M to M' that are minimal according to a given cost function associated with the edit operations. We analyze the complexity of the problem, and conclude that it is unlikely to have a polynomial time solution for it. We also show that the problem can be easily transformed to a state-space search problem, for which many heuristic approximation algorithms have been developed.},
booktitle = {Third {IEEE} {International} {Conference} on {Software} {Engineering} and {Formal} {Methods} ({SEFM}'05)},
author = {Pap, Z. and Csopaki, G. and Dibuz, S.},
month = sep,
year = {2005},
note = {ISSN: 2160-7656},
keywords = {Approximation algorithms, Automata, Computer errors, Computer science, Cost function, Heuristic algorithms, Informatics, Polynomials, Search problems, Testing, edit distance, edit operations, finite state machine, optimal patch, patching, update},
pages = {263--271},
}
Downloads: 0
{"_id":"mGNp6Svrt6TPo9snL","bibbaseid":"pap-csopaki-dibuz-onthetheoryofpatching-2005","author_short":["Pap, Z.","Csopaki, G.","Dibuz, S."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"On the theory of patching","doi":"10.1109/SEFM.2005.31","abstract":"We study the problem of patching, i.e., modifying the behavior of an existing system. We consider systems modelled as finite state machines (FSMs), and define edit operators for them based on a traditional fault model. We argue that sequences of edit operations can be considered as models of patches defining modifications to an FSM system. We utilize recent results in graph matching theory as mathematical foundations. We introduce a new type of problem which we call the optimal patch or optimal update problem: given an FSM M modeling the behavior of an existing system and an other machine M' modeling a new design, find an optimal patch, i.e., the edit operations changing M to M' that are minimal according to a given cost function associated with the edit operations. We analyze the complexity of the problem, and conclude that it is unlikely to have a polynomial time solution for it. We also show that the problem can be easily transformed to a state-space search problem, for which many heuristic approximation algorithms have been developed.","booktitle":"Third IEEE International Conference on Software Engineering and Formal Methods (SEFM'05)","author":[{"propositions":[],"lastnames":["Pap"],"firstnames":["Z."],"suffixes":[]},{"propositions":[],"lastnames":["Csopaki"],"firstnames":["G."],"suffixes":[]},{"propositions":[],"lastnames":["Dibuz"],"firstnames":["S."],"suffixes":[]}],"month":"September","year":"2005","note":"ISSN: 2160-7656","keywords":"Approximation algorithms, Automata, Computer errors, Computer science, Cost function, Heuristic algorithms, Informatics, Polynomials, Search problems, Testing, edit distance, edit operations, finite state machine, optimal patch, patching, update","pages":"263–271","bibtex":"@inproceedings{pap_theory_2005,\n\ttitle = {On the theory of patching},\n\tdoi = {10.1109/SEFM.2005.31},\n\tabstract = {We study the problem of patching, i.e., modifying the behavior of an existing system. We consider systems modelled as finite state machines (FSMs), and define edit operators for them based on a traditional fault model. We argue that sequences of edit operations can be considered as models of patches defining modifications to an FSM system. We utilize recent results in graph matching theory as mathematical foundations. We introduce a new type of problem which we call the optimal patch or optimal update problem: given an FSM M modeling the behavior of an existing system and an other machine M' modeling a new design, find an optimal patch, i.e., the edit operations changing M to M' that are minimal according to a given cost function associated with the edit operations. We analyze the complexity of the problem, and conclude that it is unlikely to have a polynomial time solution for it. We also show that the problem can be easily transformed to a state-space search problem, for which many heuristic approximation algorithms have been developed.},\n\tbooktitle = {Third {IEEE} {International} {Conference} on {Software} {Engineering} and {Formal} {Methods} ({SEFM}'05)},\n\tauthor = {Pap, Z. and Csopaki, G. and Dibuz, S.},\n\tmonth = sep,\n\tyear = {2005},\n\tnote = {ISSN: 2160-7656},\n\tkeywords = {Approximation algorithms, Automata, Computer errors, Computer science, Cost function, Heuristic algorithms, Informatics, Polynomials, Search problems, Testing, edit distance, edit operations, finite state machine, optimal patch, patching, update},\n\tpages = {263--271},\n}\n\n","author_short":["Pap, Z.","Csopaki, G.","Dibuz, S."],"key":"pap_theory_2005","id":"pap_theory_2005","bibbaseid":"pap-csopaki-dibuz-onthetheoryofpatching-2005","role":"author","urls":{},"keyword":["Approximation algorithms","Automata","Computer errors","Computer science","Cost function","Heuristic algorithms","Informatics","Polynomials","Search problems","Testing","edit distance","edit operations","finite state machine","optimal patch","patching","update"],"metadata":{"authorlinks":{}},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"https://bibbase.org/zotero/bxt101","dataSources":["Wsv2bQ4jPuc7qme8R"],"keywords":["approximation algorithms","automata","computer errors","computer science","cost function","heuristic algorithms","informatics","polynomials","search problems","testing","edit distance","edit operations","finite state machine","optimal patch","patching","update"],"search_terms":["theory","patching","pap","csopaki","dibuz"],"title":"On the theory of patching","year":2005}