{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T13:16:35Z","timestamp":1769346995458,"version":"3.49.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T00:00:00Z","timestamp":1666396800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T00:00:00Z","timestamp":1666396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Front. Comput. Sci."],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s11704-022-1673-9","type":"journal-article","created":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T10:02:53Z","timestamp":1666432973000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Complexity of adaptive testing in scenarios defined extensionally"],"prefix":"10.1007","volume":"17","author":[{"given":"Ismael","family":"Rodr\u00edguez","sequence":"first","affiliation":[]},{"given":"David","family":"Rubio","sequence":"additional","affiliation":[]},{"given":"Fernando","family":"Rubio","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,22]]},"reference":[{"issue":"8","key":"1673_CR1","doi-asserted-by":"publisher","first-page":"1090","DOI":"10.1109\/5.533956","volume":"84","author":"D Lee","year":"1996","unstructured":"Lee D, Yannakakis M. Principles and methods of testing finite state machines-a survey. Proceedings of the IEEE, 1996, 84(8): 1090\u20131123","journal-title":"Proceedings of the IEEE"},{"key":"1673_CR2","doi-asserted-by":"crossref","unstructured":"Petrenko A. Fault model-driven test derivation from finite state models: annotated bibliography. In: Proceedings of the 4th Summer School on Modeling and Verification of Parallel Processes. 2001, 196\u2013205","DOI":"10.1007\/3-540-45510-8_10"},{"issue":"12","key":"1673_CR3","doi-asserted-by":"publisher","first-page":"1286","DOI":"10.1016\/j.infsof.2010.07.001","volume":"52","author":"R Dorofeeva","year":"2010","unstructured":"Dorofeeva R, El-Fakih K, Maag S, Cavalli A R, Yevtushenko N. FSM-based conformance testing methods: a survey annotated with experimental evaluation. Information and Software Technology, 2010, 52(12): 1286\u20131297","journal-title":"Information and Software Technology"},{"issue":"1","key":"1673_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0169-7552(96)00017-7","volume":"29","author":"J Tretmans","year":"1996","unstructured":"Tretmans J. Conformance testing with labelled transition systems: implementation relations and test generation. Computer Networks and ISDN Systems, 1996, 29(1): 49\u201379","journal-title":"Computer Networks and ISDN Systems"},{"key":"1673_CR5","doi-asserted-by":"crossref","unstructured":"Tretmans J. Testing concurrent systems: a formal approach. In: Proceedings of the 10th International Conference on Concurrency Theory. 1999, 46\u201365","DOI":"10.1007\/3-540-48320-9_6"},{"key":"1673_CR6","doi-asserted-by":"crossref","unstructured":"Brinksma E, Tretmans J. Testing transition systems: an annotated bibliography. In: Proceedings of the 4th Summer School on Modeling and Verification of Parallel Processes. 2001, 187\u2013195","DOI":"10.1007\/3-540-45510-8_9"},{"issue":"1\u20132","key":"1673_CR7","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/S0304-3975(99)00134-6","volume":"254","author":"J Springintveld","year":"2001","unstructured":"Springintveld J, Vaandrager F, D\u2019Argenio P R. Testing timed automata. Theoretical Computer Science, 2001, 254(1\u20132): 225\u2013257","journal-title":"Theoretical Computer Science"},{"key":"1673_CR8","doi-asserted-by":"crossref","unstructured":"Krichen M, Tripakis S. Black-box conformance testing for real-time systems. In: Proceedings of the 11th International SPIN Workshop on Model Checking of Software. 2004, 109\u2013126","DOI":"10.1007\/978-3-540-24732-6_8"},{"key":"1673_CR9","doi-asserted-by":"crossref","unstructured":"Berrada I, Castanet R, F\u00e9lix P, Salah A. Test case minimization for realtime systems using timed bound traces. In: Proceedings of the 18th IFIP TC 6\/WG 6.1 International Conference on Testing of Communicating Systems. 2006, 289\u2013305","DOI":"10.1007\/11754008_19"},{"issue":"6","key":"1673_CR10","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1109\/TC.2008.15","volume":"57","author":"M Merayo","year":"2008","unstructured":"Merayo M, N\u00fa\u00f1ez M, Rodr\u00edguez I. Extending EFSMs to specify and test timed systems with action durations and time-outs. IEEE Transactions on Computers, 2008, 57(6): 835\u2013844","journal-title":"IEEE Transactions on Computers"},{"key":"1673_CR11","doi-asserted-by":"crossref","unstructured":"Stoelinga M, Vaandrager F. A testing scenario for probabilistic automata. In: Proceedings of the 30th International Colloquium on Automata, Languages and Programming. 2003, 464\u2013477","DOI":"10.1007\/3-540-45061-0_38"},{"issue":"1\u20133","key":"1673_CR12","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/j.tcs.2005.10.047","volume":"353","author":"N L\u00f3pez","year":"2006","unstructured":"L\u00f3pez N, N\u00fa\u00f1ez M, Rodr\u00edguez I. Specification, testing and implementation relations for symbolic-probabilistic systems. Theoretical Computer Science, 2006, 353(1\u20133): 228\u2013248","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"1673_CR13","doi-asserted-by":"publisher","first-page":"3651","DOI":"10.1109\/JSYST.2019.2899697","volume":"13","author":"M Efatmaneshnik","year":"2019","unstructured":"Efatmaneshnik M, Shoval S, Joiner K. System test architecture evaluation: a probabilistic modeling approach. IEEE Systems Journal, 2019, 13(4): 3651\u20133662","journal-title":"IEEE Systems Journal"},{"issue":"8","key":"1673_CR14","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1109\/32.57623","volume":"16","author":"L J Morell","year":"1990","unstructured":"Morell L J. A theory of fault-based testing. IEEE Transactions on Software Engineering, 1990, 16(8): 844\u2013857","journal-title":"IEEE Transactions on Software Engineering"},{"issue":"4","key":"1673_CR15","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1145\/606612.606615","volume":"11","author":"R M Hierons","year":"2002","unstructured":"Hierons R M. Comparing test sets and criteria in the presence of test hypotheses and fault domains. ACM Transactions on Software Engineering and Methodology, 2002, 11(4): 427\u2013448","journal-title":"ACM Transactions on Software Engineering and Methodology"},{"issue":"4","key":"1673_CR16","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/1538942.1538944","volume":"18","author":"R M Hierons","year":"2009","unstructured":"Hierons R M. Verdict functions in testing with a fault domain or test hypotheses. ACM Transactions on Software Engineering and Methodology, 2009, 18(4): 14","journal-title":"ACM Transactions on Software Engineering and Methodology"},{"issue":"2","key":"1673_CR17","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.jlap.2007.03.002","volume":"74","author":"I Rodr\u00edguez","year":"2008","unstructured":"Rodr\u00edguez I, Merayo M G, N\u00fa\u00f1ez M. HOTL: hypotheses and observations testing logic. The Journal of Logic and Algebraic Programming, 2008, 74(2): 57\u201393","journal-title":"The Journal of Logic and Algebraic Programming"},{"issue":"9","key":"1673_CR18","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1109\/TSE.2014.2331690","volume":"40","author":"I Rodr\u00edguez","year":"2014","unstructured":"Rodr\u00edguez I, Llana L, Rabanal P. A general testability theory: classes, properties, complexity, and testing reductions. IEEE Transactions on Software Engineering, 2014, 40(9): 862\u2013894","journal-title":"IEEE Transactions on Software Engineering"},{"key":"1673_CR19","doi-asserted-by":"publisher","first-page":"100502","DOI":"10.1016\/j.jlamp.2019.100502","volume":"111","author":"I Rodr\u00edguez","year":"2020","unstructured":"Rodr\u00edguez I, Rosa-Velardo F, Rubio F. Introducing complexity to formal testing. Journal of Logical and Algebraic Methods in Programming, 2020, 111: 100502","journal-title":"Journal of Logical and Algebraic Methods in Programming"},{"key":"1673_CR20","doi-asserted-by":"crossref","unstructured":"Kushik N, Yevtushenko N. Adaptive homing is in P. In: Proceedings of the 10th Workshop on Model-Based Testing. 2015, 73\u201378","DOI":"10.4204\/EPTCS.180.5"},{"key":"1673_CR21","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ipl.2017.07.001","volume":"127","author":"H Yenig\u00fcn","year":"2017","unstructured":"Yenig\u00fcn H, Yevtushenko N, Kushik N. The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs. Information Processing Letters, 2017, 127: 49\u201353","journal-title":"Information Processing Letters"},{"key":"1673_CR22","doi-asserted-by":"crossref","unstructured":"Kushik N, Yevtushenko N, Yenigun H. Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs. In: Proceedings of the 4th International Workshop on DomAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn. 2016, 83\u201390","DOI":"10.5220\/0005854500830090"},{"key":"1673_CR23","doi-asserted-by":"crossref","unstructured":"Petrenko A, Yevtushenko N. Adaptive testing of deterministic implementations specified by nondeterministic FSMs. In: Proceedings of the 23rd IFIP WG 6.1 International Conference on Testing Software and Systems. 2011, 162\u2013178","DOI":"10.1007\/978-3-642-24580-0_12"},{"key":"1673_CR24","doi-asserted-by":"crossref","unstructured":"Petrenko A, Yevtushenko N. Adaptive testing of nondeterministic systems with FSM. In: Proceedings of the 15th IEEE International Symposium on High-Assurance Systems Engineering. 2014, 224\u2013228","DOI":"10.1109\/HASE.2014.39"},{"key":"1673_CR25","doi-asserted-by":"crossref","unstructured":"van den Bos P, Vaandrager F. State identification for labeled transition systems with inputs and outputs. In: Proceedings of the 16th International Conference on Formal Aspects of Component Software. 2019, 191\u2013212","DOI":"10.1007\/978-3-030-40914-2_10"},{"issue":"2","key":"1673_CR26","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s10703-019-00338-9","volume":"55","author":"R Bloem","year":"2019","unstructured":"Bloem R, Fey G, Greif F, K\u00f6nighofer R, Pill I, Riener H, R\u00f6ck F. Synthesizing adaptive test strategies from temporal logic specifications. Formal Methods in System Design, 2019, 55(2): 103\u2013135","journal-title":"Formal Methods in System Design"},{"key":"1673_CR27","doi-asserted-by":"crossref","unstructured":"Rodr\u00edguez I. A general testability theory. In: Proceedings of the 20th International Conference on Concurrency Theory. 2009, 572\u2013586","DOI":"10.1007\/978-3-642-04081-8_38"},{"key":"1673_CR28","unstructured":"Crescenzi P. A short guide to approximation preserving reductions. In: Proceedings of the 12th Annual IEEE Conference on Computational Complexity. 1997, 262\u2013273"},{"issue":"4","key":"1673_CR29","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U. A threshold of ln n for approximating set cover. Journal of the ACM, 1998, 45(4): 634\u2013652","journal-title":"Journal of the ACM"},{"key":"1673_CR30","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"2012","unstructured":"Sipser M. Introduction to the Theory of Computation. Boston: Cengage Learning, 2012"},{"issue":"1","key":"1673_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2273858","volume":"52","author":"L Stockmeyer","year":"1987","unstructured":"Stockmeyer L. Classifying the computational complexity of problems. The Journal of Symbolic Logic, 1987, 52(1): 1\u201343","journal-title":"The Journal of Symbolic Logic"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-022-1673-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11704-022-1673-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-022-1673-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T20:29:36Z","timestamp":1721420976000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11704-022-1673-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,22]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1673"],"URL":"https:\/\/doi.org\/10.1007\/s11704-022-1673-9","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"value":"2095-2228","type":"print"},{"value":"2095-2236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,22]]},"assertion":[{"value":"22 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"173206"}}