Efficient iterative deepening for bounded exhaustive generation of complex structures
| Autor: | Muhammad Nawaz, Junaid Haroon Siddiqui, Affan Rauf |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Model checking
021103 operations research Exponential growth Computer science Bounded function 0211 other engineering and technologies 0202 electrical engineering electronic engineering information engineering Structure (category theory) 020207 software engineering 02 engineering and technology Iterative deepening depth-first search Algorithm |
| Zdroj: | ICSE (Companion Volume) |
| DOI: | 10.1145/3183440.3195002 |
| Popis: | The time required to generate valid structurally complex inputs grows exponentially with the input size. It makes it hard to predict, for a given structure, the most feasible input size that is completely explorable within a time budget. Iterative deepening generates inputs of size n before those of size n + 1 and eliminates guesswork to find such size. We build on Korat algorithm for structural test generation and present iKorat - an incremental algorithm for efficient iterative deepening. It avoids redundant work as opposed to naive Korat-based iterative deepening by using information from smaller sizes, which is kept in a highly compact format. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|