In this paper,we consider a testing setting where the set of possible definitions of the Implementation Under Test(IUT),as well as the behavior of each of these definitions in all possible interactions,are extensional...In this paper,we consider a testing setting where the set of possible definitions of the Implementation Under Test(IUT),as well as the behavior of each of these definitions in all possible interactions,are extensionally defined,i.e.,on an element-by-element and case-by-case basis.Under this setting,the problem of finding the minimum testing strategy such that collected observations will necessarily let us decide whether the IUT is correct or not(i.e.,whether it necessarily belongs to the set of possible correct definitions or not)is studied in four possible problem variants:with or without non-determinism;and with or without more than one possible definition in the sets of possible correct and incorrect definitions.The computational complexity of these variants is studied,and properties such as PSPACE-completeness and Log-APX-hardness are identified.展开更多
基金This work has been partially supported by project PID2019-108528RB-C22by Comunidad de Madrid as part of the program S2018/TCS-4339(BLOQUES-CM)co-funded by EIE Funds of the European Union.
文摘In this paper,we consider a testing setting where the set of possible definitions of the Implementation Under Test(IUT),as well as the behavior of each of these definitions in all possible interactions,are extensionally defined,i.e.,on an element-by-element and case-by-case basis.Under this setting,the problem of finding the minimum testing strategy such that collected observations will necessarily let us decide whether the IUT is correct or not(i.e.,whether it necessarily belongs to the set of possible correct definitions or not)is studied in four possible problem variants:with or without non-determinism;and with or without more than one possible definition in the sets of possible correct and incorrect definitions.The computational complexity of these variants is studied,and properties such as PSPACE-completeness and Log-APX-hardness are identified.
