./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/array-crafted/zero_sum3.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version eb692b52 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/array-crafted/zero_sum3.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash d3267df59902b667587c98ecbe021c99cc3d2a5e5866fbd08ee1fb3133370aa4 --- Real Ultimate output --- This is Ultimate 0.2.2-?-eb692b5 [2022-07-19 09:55:22,505 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-19 09:55:22,507 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-19 09:55:22,537 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-19 09:55:22,538 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-19 09:55:22,539 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-19 09:55:22,540 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-19 09:55:22,542 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-19 09:55:22,543 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-19 09:55:22,544 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-19 09:55:22,545 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-19 09:55:22,546 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-19 09:55:22,546 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-19 09:55:22,547 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-19 09:55:22,548 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-19 09:55:22,552 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-19 09:55:22,553 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-19 09:55:22,558 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-19 09:55:22,560 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-19 09:55:22,566 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-19 09:55:22,570 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-19 09:55:22,571 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-19 09:55:22,572 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-19 09:55:22,573 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-19 09:55:22,576 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-19 09:55:22,580 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-19 09:55:22,583 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-19 09:55:22,584 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-19 09:55:22,585 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-19 09:55:22,586 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-19 09:55:22,587 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-19 09:55:22,587 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-19 09:55:22,589 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-19 09:55:22,589 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-19 09:55:22,590 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-19 09:55:22,591 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-19 09:55:22,591 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-19 09:55:22,592 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-19 09:55:22,592 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-19 09:55:22,592 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-19 09:55:22,594 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-19 09:55:22,596 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-19 09:55:22,597 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2022-07-19 09:55:22,626 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-19 09:55:22,632 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-19 09:55:22,633 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-19 09:55:22,633 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-19 09:55:22,634 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-07-19 09:55:22,634 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-07-19 09:55:22,635 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-19 09:55:22,635 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-19 09:55:22,635 INFO L138 SettingsManager]: * Use SBE=true [2022-07-19 09:55:22,636 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-19 09:55:22,636 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-19 09:55:22,636 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-19 09:55:22,637 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-19 09:55:22,637 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-19 09:55:22,637 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-07-19 09:55:22,637 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-07-19 09:55:22,637 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-07-19 09:55:22,637 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-19 09:55:22,638 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-19 09:55:22,639 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-19 09:55:22,639 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-07-19 09:55:22,639 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-19 09:55:22,640 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-19 09:55:22,640 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-07-19 09:55:22,640 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-19 09:55:22,641 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-19 09:55:22,641 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-07-19 09:55:22,641 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-07-19 09:55:22,641 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-19 09:55:22,641 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-07-19 09:55:22,642 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-07-19 09:55:22,642 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-07-19 09:55:22,642 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-07-19 09:55:22,642 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> d3267df59902b667587c98ecbe021c99cc3d2a5e5866fbd08ee1fb3133370aa4 [2022-07-19 09:55:22,932 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-19 09:55:22,952 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-19 09:55:22,954 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-19 09:55:22,955 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-19 09:55:22,956 INFO L275 PluginConnector]: CDTParser initialized [2022-07-19 09:55:22,957 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-crafted/zero_sum3.c [2022-07-19 09:55:23,020 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/066d7beda/fc8deae1be2b4083af1d24f08f5b9c14/FLAGab15b48bf [2022-07-19 09:55:23,433 INFO L306 CDTParser]: Found 1 translation units. [2022-07-19 09:55:23,435 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-crafted/zero_sum3.c [2022-07-19 09:55:23,441 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/066d7beda/fc8deae1be2b4083af1d24f08f5b9c14/FLAGab15b48bf [2022-07-19 09:55:23,834 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/066d7beda/fc8deae1be2b4083af1d24f08f5b9c14 [2022-07-19 09:55:23,836 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-19 09:55:23,837 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-19 09:55:23,841 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-19 09:55:23,841 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-19 09:55:23,844 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-19 09:55:23,844 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.07 09:55:23" (1/1) ... [2022-07-19 09:55:23,846 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4c046caf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:55:23, skipping insertion in model container [2022-07-19 09:55:23,846 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.07 09:55:23" (1/1) ... [2022-07-19 09:55:23,852 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-19 09:55:23,864 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-19 09:55:23,972 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-crafted/zero_sum3.c[400,413] [2022-07-19 09:55:23,994 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-19 09:55:24,004 INFO L203 MainTranslator]: Completed pre-run [2022-07-19 09:55:24,018 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-crafted/zero_sum3.c[400,413] [2022-07-19 09:55:24,045 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-19 09:55:24,061 INFO L208 MainTranslator]: Completed translation [2022-07-19 09:55:24,062 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:55:24 WrapperNode [2022-07-19 09:55:24,062 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-19 09:55:24,063 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-19 09:55:24,063 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-19 09:55:24,063 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-19 09:55:24,070 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:55:24" (1/1) ... [2022-07-19 09:55:24,083 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:55:24" (1/1) ... [2022-07-19 09:55:24,107 INFO L137 Inliner]: procedures = 15, calls = 17, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 105 [2022-07-19 09:55:24,107 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-19 09:55:24,109 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-19 09:55:24,109 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-19 09:55:24,109 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-19 09:55:24,115 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:55:24" (1/1) ... [2022-07-19 09:55:24,116 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:55:24" (1/1) ... [2022-07-19 09:55:24,119 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:55:24" (1/1) ... [2022-07-19 09:55:24,119 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:55:24" (1/1) ... [2022-07-19 09:55:24,137 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:55:24" (1/1) ... [2022-07-19 09:55:24,142 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:55:24" (1/1) ... [2022-07-19 09:55:24,147 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:55:24" (1/1) ... [2022-07-19 09:55:24,149 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-19 09:55:24,152 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-19 09:55:24,153 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-19 09:55:24,153 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-19 09:55:24,154 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:55:24" (1/1) ... [2022-07-19 09:55:24,161 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-19 09:55:24,205 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:55:24,249 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-07-19 09:55:24,273 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-07-19 09:55:24,295 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-19 09:55:24,295 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-19 09:55:24,296 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2022-07-19 09:55:24,296 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-07-19 09:55:24,296 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-19 09:55:24,296 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-19 09:55:24,296 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-07-19 09:55:24,296 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-07-19 09:55:24,360 INFO L234 CfgBuilder]: Building ICFG [2022-07-19 09:55:24,362 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-19 09:55:24,522 INFO L275 CfgBuilder]: Performing block encoding [2022-07-19 09:55:24,527 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-19 09:55:24,527 INFO L299 CfgBuilder]: Removed 7 assume(true) statements. [2022-07-19 09:55:24,529 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.07 09:55:24 BoogieIcfgContainer [2022-07-19 09:55:24,529 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-19 09:55:24,531 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-07-19 09:55:24,531 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-07-19 09:55:24,534 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-07-19 09:55:24,535 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.07 09:55:23" (1/3) ... [2022-07-19 09:55:24,540 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@958212f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.07 09:55:24, skipping insertion in model container [2022-07-19 09:55:24,540 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 09:55:24" (2/3) ... [2022-07-19 09:55:24,547 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@958212f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.07 09:55:24, skipping insertion in model container [2022-07-19 09:55:24,547 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.07 09:55:24" (3/3) ... [2022-07-19 09:55:24,548 INFO L111 eAbstractionObserver]: Analyzing ICFG zero_sum3.c [2022-07-19 09:55:24,561 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-07-19 09:55:24,565 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-07-19 09:55:24,612 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-07-19 09:55:24,630 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@4d118bdd, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@7cb9ebdd [2022-07-19 09:55:24,635 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-07-19 09:55:24,640 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 30 states have (on average 1.5666666666666667) internal successors, (47), 31 states have internal predecessors, (47), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:24,651 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2022-07-19 09:55:24,651 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:55:24,652 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:55:24,652 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:55:24,657 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:55:24,658 INFO L85 PathProgramCache]: Analyzing trace with hash 534528496, now seen corresponding path program 1 times [2022-07-19 09:55:24,666 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:55:24,666 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [973631688] [2022-07-19 09:55:24,667 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:55:24,667 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:55:24,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:55:24,820 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 09:55:24,821 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:55:24,822 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [973631688] [2022-07-19 09:55:24,823 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [973631688] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 09:55:24,823 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 09:55:24,823 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-07-19 09:55:24,825 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1080580352] [2022-07-19 09:55:24,826 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 09:55:24,830 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-07-19 09:55:24,832 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:55:24,861 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-07-19 09:55:24,863 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-19 09:55:24,865 INFO L87 Difference]: Start difference. First operand has 32 states, 30 states have (on average 1.5666666666666667) internal successors, (47), 31 states have internal predecessors, (47), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand has 2 states, 2 states have (on average 9.5) internal successors, (19), 2 states have internal predecessors, (19), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:24,887 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:55:24,888 INFO L93 Difference]: Finished difference Result 59 states and 86 transitions. [2022-07-19 09:55:24,889 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-19 09:55:24,891 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 9.5) internal successors, (19), 2 states have internal predecessors, (19), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 19 [2022-07-19 09:55:24,892 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:55:24,898 INFO L225 Difference]: With dead ends: 59 [2022-07-19 09:55:24,898 INFO L226 Difference]: Without dead ends: 27 [2022-07-19 09:55:24,901 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-19 09:55:24,914 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 39 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 09:55:24,916 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 09:55:24,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-07-19 09:55:24,950 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2022-07-19 09:55:24,952 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 26 states have internal predecessors, (33), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:24,954 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 33 transitions. [2022-07-19 09:55:24,955 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 33 transitions. Word has length 19 [2022-07-19 09:55:24,956 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:55:24,956 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 33 transitions. [2022-07-19 09:55:24,957 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 9.5) internal successors, (19), 2 states have internal predecessors, (19), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:24,957 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 33 transitions. [2022-07-19 09:55:24,958 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2022-07-19 09:55:24,958 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:55:24,958 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:55:24,958 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-07-19 09:55:24,959 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:55:24,961 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:55:24,961 INFO L85 PathProgramCache]: Analyzing trace with hash -697412484, now seen corresponding path program 1 times [2022-07-19 09:55:24,962 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:55:24,962 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [308571343] [2022-07-19 09:55:24,963 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:55:24,963 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:55:24,994 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:55:25,041 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 09:55:25,042 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:55:25,042 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [308571343] [2022-07-19 09:55:25,043 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [308571343] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 09:55:25,043 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 09:55:25,043 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-07-19 09:55:25,043 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1774151301] [2022-07-19 09:55:25,044 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 09:55:25,046 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-07-19 09:55:25,047 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:55:25,047 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-07-19 09:55:25,048 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-07-19 09:55:25,048 INFO L87 Difference]: Start difference. First operand 27 states and 33 transitions. Second operand has 3 states, 3 states have (on average 6.333333333333333) internal successors, (19), 3 states have internal predecessors, (19), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:25,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:55:25,115 INFO L93 Difference]: Finished difference Result 51 states and 63 transitions. [2022-07-19 09:55:25,116 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-07-19 09:55:25,116 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 6.333333333333333) internal successors, (19), 3 states have internal predecessors, (19), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 19 [2022-07-19 09:55:25,116 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:55:25,117 INFO L225 Difference]: With dead ends: 51 [2022-07-19 09:55:25,117 INFO L226 Difference]: Without dead ends: 29 [2022-07-19 09:55:25,121 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-07-19 09:55:25,123 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 1 mSDsluCounter, 15 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 46 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 09:55:25,124 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 46 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 09:55:25,126 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2022-07-19 09:55:25,132 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 28. [2022-07-19 09:55:25,132 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 27 states have internal predecessors, (34), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:25,133 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 34 transitions. [2022-07-19 09:55:25,134 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 34 transitions. Word has length 19 [2022-07-19 09:55:25,134 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:55:25,135 INFO L495 AbstractCegarLoop]: Abstraction has 28 states and 34 transitions. [2022-07-19 09:55:25,136 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 6.333333333333333) internal successors, (19), 3 states have internal predecessors, (19), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:25,138 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 34 transitions. [2022-07-19 09:55:25,139 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-07-19 09:55:25,139 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:55:25,139 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:55:25,139 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-07-19 09:55:25,140 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:55:25,141 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:55:25,141 INFO L85 PathProgramCache]: Analyzing trace with hash -506383970, now seen corresponding path program 1 times [2022-07-19 09:55:25,141 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:55:25,144 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [671450673] [2022-07-19 09:55:25,145 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:55:25,145 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:55:25,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:55:25,226 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-07-19 09:55:25,226 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:55:25,227 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [671450673] [2022-07-19 09:55:25,227 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [671450673] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 09:55:25,228 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 09:55:25,228 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-07-19 09:55:25,228 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1359834892] [2022-07-19 09:55:25,228 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 09:55:25,229 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-07-19 09:55:25,229 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:55:25,230 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-07-19 09:55:25,230 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2022-07-19 09:55:25,230 INFO L87 Difference]: Start difference. First operand 28 states and 34 transitions. Second operand has 4 states, 4 states have (on average 5.25) internal successors, (21), 4 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:25,335 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:55:25,335 INFO L93 Difference]: Finished difference Result 59 states and 75 transitions. [2022-07-19 09:55:25,336 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-07-19 09:55:25,336 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 5.25) internal successors, (21), 4 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 21 [2022-07-19 09:55:25,336 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:55:25,337 INFO L225 Difference]: With dead ends: 59 [2022-07-19 09:55:25,347 INFO L226 Difference]: Without dead ends: 40 [2022-07-19 09:55:25,348 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2022-07-19 09:55:25,349 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 39 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 17 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 09:55:25,350 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 17 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 09:55:25,351 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2022-07-19 09:55:25,354 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 34. [2022-07-19 09:55:25,355 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 33 states have (on average 1.2121212121212122) internal successors, (40), 33 states have internal predecessors, (40), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:25,356 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 40 transitions. [2022-07-19 09:55:25,356 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 40 transitions. Word has length 21 [2022-07-19 09:55:25,356 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:55:25,356 INFO L495 AbstractCegarLoop]: Abstraction has 34 states and 40 transitions. [2022-07-19 09:55:25,357 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 5.25) internal successors, (21), 4 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:25,357 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 40 transitions. [2022-07-19 09:55:25,358 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-07-19 09:55:25,358 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:55:25,358 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:55:25,358 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-07-19 09:55:25,361 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:55:25,361 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:55:25,362 INFO L85 PathProgramCache]: Analyzing trace with hash 615846698, now seen corresponding path program 1 times [2022-07-19 09:55:25,362 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:55:25,362 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1000853299] [2022-07-19 09:55:25,362 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:55:25,363 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:55:25,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:55:25,472 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-19 09:55:25,472 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:55:25,473 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1000853299] [2022-07-19 09:55:25,473 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1000853299] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:55:25,473 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1818386126] [2022-07-19 09:55:25,473 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:55:25,474 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:55:25,474 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:55:25,479 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:55:25,486 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-07-19 09:55:25,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:55:25,574 INFO L263 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 4 conjunts are in the unsatisfiable core [2022-07-19 09:55:25,578 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:55:25,632 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-19 09:55:25,633 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:55:25,661 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-19 09:55:25,662 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1818386126] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:55:25,662 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:55:25,662 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 7 [2022-07-19 09:55:25,662 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1688243501] [2022-07-19 09:55:25,662 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:55:25,663 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-19 09:55:25,663 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:55:25,664 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-19 09:55:25,664 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2022-07-19 09:55:25,664 INFO L87 Difference]: Start difference. First operand 34 states and 40 transitions. Second operand has 7 states, 7 states have (on average 5.714285714285714) internal successors, (40), 7 states have internal predecessors, (40), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:25,704 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:55:25,705 INFO L93 Difference]: Finished difference Result 65 states and 77 transitions. [2022-07-19 09:55:25,705 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-19 09:55:25,705 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 5.714285714285714) internal successors, (40), 7 states have internal predecessors, (40), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 33 [2022-07-19 09:55:25,705 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:55:25,706 INFO L225 Difference]: With dead ends: 65 [2022-07-19 09:55:25,706 INFO L226 Difference]: Without dead ends: 37 [2022-07-19 09:55:25,707 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 62 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2022-07-19 09:55:25,708 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 4 mSDsluCounter, 30 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 61 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 09:55:25,708 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 61 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 09:55:25,709 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2022-07-19 09:55:25,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 36. [2022-07-19 09:55:25,713 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 35 states have (on average 1.2) internal successors, (42), 35 states have internal predecessors, (42), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:25,714 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 42 transitions. [2022-07-19 09:55:25,714 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 42 transitions. Word has length 33 [2022-07-19 09:55:25,714 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:55:25,714 INFO L495 AbstractCegarLoop]: Abstraction has 36 states and 42 transitions. [2022-07-19 09:55:25,715 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 5.714285714285714) internal successors, (40), 7 states have internal predecessors, (40), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:25,715 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 42 transitions. [2022-07-19 09:55:25,715 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2022-07-19 09:55:25,716 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:55:25,716 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:55:25,751 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-07-19 09:55:25,940 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:55:25,941 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:55:25,941 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:55:25,941 INFO L85 PathProgramCache]: Analyzing trace with hash -160084788, now seen corresponding path program 2 times [2022-07-19 09:55:25,942 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:55:25,942 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1424158979] [2022-07-19 09:55:25,942 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:55:25,942 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:55:25,968 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:55:26,019 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-07-19 09:55:26,019 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:55:26,019 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1424158979] [2022-07-19 09:55:26,019 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1424158979] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:55:26,020 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1017452852] [2022-07-19 09:55:26,020 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-19 09:55:26,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:55:26,020 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:55:26,022 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:55:26,025 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-07-19 09:55:26,102 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-19 09:55:26,102 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:55:26,105 INFO L263 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 4 conjunts are in the unsatisfiable core [2022-07-19 09:55:26,108 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:55:26,181 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-07-19 09:55:26,181 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:55:26,233 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-07-19 09:55:26,234 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1017452852] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:55:26,234 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:55:26,234 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 8 [2022-07-19 09:55:26,234 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1708323013] [2022-07-19 09:55:26,234 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:55:26,235 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-07-19 09:55:26,235 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:55:26,241 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-07-19 09:55:26,241 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=31, Unknown=0, NotChecked=0, Total=56 [2022-07-19 09:55:26,242 INFO L87 Difference]: Start difference. First operand 36 states and 42 transitions. Second operand has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:26,354 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:55:26,354 INFO L93 Difference]: Finished difference Result 78 states and 94 transitions. [2022-07-19 09:55:26,355 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-19 09:55:26,355 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 35 [2022-07-19 09:55:26,355 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:55:26,356 INFO L225 Difference]: With dead ends: 78 [2022-07-19 09:55:26,356 INFO L226 Difference]: Without dead ends: 54 [2022-07-19 09:55:26,357 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 65 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=32, Invalid=40, Unknown=0, NotChecked=0, Total=72 [2022-07-19 09:55:26,358 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 55 mSDsluCounter, 12 mSDsCounter, 0 mSdLazyCounter, 83 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 25 SdHoareTripleChecker+Invalid, 133 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 83 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 09:55:26,358 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 25 Invalid, 133 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 83 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 09:55:26,359 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-07-19 09:55:26,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 48. [2022-07-19 09:55:26,363 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 47 states have (on average 1.148936170212766) internal successors, (54), 47 states have internal predecessors, (54), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:26,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 54 transitions. [2022-07-19 09:55:26,364 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 54 transitions. Word has length 35 [2022-07-19 09:55:26,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:55:26,365 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 54 transitions. [2022-07-19 09:55:26,365 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 5.0) internal successors, (40), 8 states have internal predecessors, (40), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:26,365 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 54 transitions. [2022-07-19 09:55:26,366 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-07-19 09:55:26,366 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:55:26,366 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:55:26,392 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-07-19 09:55:26,582 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:55:26,583 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:55:26,584 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:55:26,584 INFO L85 PathProgramCache]: Analyzing trace with hash -1337652904, now seen corresponding path program 3 times [2022-07-19 09:55:26,584 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:55:26,584 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [739424377] [2022-07-19 09:55:26,584 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:55:26,584 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:55:26,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:55:27,853 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 09:55:27,854 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:55:27,854 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [739424377] [2022-07-19 09:55:27,854 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [739424377] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:55:27,854 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2067337397] [2022-07-19 09:55:27,854 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-19 09:55:27,854 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:55:27,855 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:55:27,860 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:55:27,865 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-07-19 09:55:27,923 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-07-19 09:55:27,923 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:55:27,925 INFO L263 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 64 conjunts are in the unsatisfiable core [2022-07-19 09:55:27,929 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:55:29,291 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-19 09:55:29,293 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 26 treesize of output 29 [2022-07-19 09:55:29,477 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 09:55:29,478 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:55:35,164 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-19 09:55:35,164 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 36 treesize of output 93 [2022-07-19 09:55:35,432 INFO L356 Elim1Store]: treesize reduction 40, result has 52.9 percent of original size [2022-07-19 09:55:35,432 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 37 treesize of output 54 [2022-07-19 09:55:36,010 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 09:55:36,010 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2067337397] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:55:36,010 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:55:36,010 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 27, 32] total 68 [2022-07-19 09:55:36,011 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1167284614] [2022-07-19 09:55:36,011 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:55:36,011 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 68 states [2022-07-19 09:55:36,012 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:55:36,012 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 68 interpolants. [2022-07-19 09:55:36,015 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=427, Invalid=4128, Unknown=1, NotChecked=0, Total=4556 [2022-07-19 09:55:36,016 INFO L87 Difference]: Start difference. First operand 48 states and 54 transitions. Second operand has 68 states, 68 states have (on average 1.9558823529411764) internal successors, (133), 68 states have internal predecessors, (133), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:39,415 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:55:39,415 INFO L93 Difference]: Finished difference Result 161 states and 187 transitions. [2022-07-19 09:55:39,416 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2022-07-19 09:55:39,416 INFO L78 Accepts]: Start accepts. Automaton has has 68 states, 68 states have (on average 1.9558823529411764) internal successors, (133), 68 states have internal predecessors, (133), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 47 [2022-07-19 09:55:39,417 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:55:39,420 INFO L225 Difference]: With dead ends: 161 [2022-07-19 09:55:39,420 INFO L226 Difference]: Without dead ends: 157 [2022-07-19 09:55:39,424 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 183 GetRequests, 44 SyntacticMatches, 38 SemanticMatches, 101 ConstructedPredicates, 0 IntricatePredicates, 5 DeprecatedPredicates, 4261 ImplicationChecksByTransitivity, 8.6s TimeCoverageRelationStatistics Valid=965, Invalid=9540, Unknown=1, NotChecked=0, Total=10506 [2022-07-19 09:55:39,425 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 97 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 517 mSolverCounterSat, 79 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 97 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 1749 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 79 IncrementalHoareTripleChecker+Valid, 517 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 1153 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-07-19 09:55:39,426 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [97 Valid, 149 Invalid, 1749 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [79 Valid, 517 Invalid, 0 Unknown, 1153 Unchecked, 0.4s Time] [2022-07-19 09:55:39,427 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 157 states. [2022-07-19 09:55:39,439 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 157 to 77. [2022-07-19 09:55:39,439 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 76 states have (on average 1.1578947368421053) internal successors, (88), 76 states have internal predecessors, (88), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:39,440 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 88 transitions. [2022-07-19 09:55:39,441 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 88 transitions. Word has length 47 [2022-07-19 09:55:39,441 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:55:39,441 INFO L495 AbstractCegarLoop]: Abstraction has 77 states and 88 transitions. [2022-07-19 09:55:39,442 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 68 states, 68 states have (on average 1.9558823529411764) internal successors, (133), 68 states have internal predecessors, (133), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:39,442 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 88 transitions. [2022-07-19 09:55:39,443 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2022-07-19 09:55:39,443 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:55:39,443 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:55:39,465 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-07-19 09:55:39,655 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:55:39,656 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:55:39,656 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:55:39,657 INFO L85 PathProgramCache]: Analyzing trace with hash -1235984134, now seen corresponding path program 4 times [2022-07-19 09:55:39,657 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:55:39,657 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1934693199] [2022-07-19 09:55:39,657 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:55:39,657 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:55:39,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:55:39,778 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2022-07-19 09:55:39,779 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:55:39,779 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1934693199] [2022-07-19 09:55:39,779 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1934693199] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:55:39,779 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2053458409] [2022-07-19 09:55:39,780 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-19 09:55:39,780 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:55:39,780 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:55:39,784 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:55:39,788 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-07-19 09:55:39,832 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-19 09:55:39,832 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:55:39,834 INFO L263 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 8 conjunts are in the unsatisfiable core [2022-07-19 09:55:39,836 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:55:39,942 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 9 proven. 4 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2022-07-19 09:55:39,942 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:55:40,016 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 9 proven. 4 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2022-07-19 09:55:40,017 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2053458409] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:55:40,017 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:55:40,017 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2022-07-19 09:55:40,017 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1313733249] [2022-07-19 09:55:40,018 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:55:40,018 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-07-19 09:55:40,019 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:55:40,019 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-07-19 09:55:40,019 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=133, Unknown=0, NotChecked=0, Total=182 [2022-07-19 09:55:40,022 INFO L87 Difference]: Start difference. First operand 77 states and 88 transitions. Second operand has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 14 states have internal predecessors, (51), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:40,202 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:55:40,202 INFO L93 Difference]: Finished difference Result 152 states and 174 transitions. [2022-07-19 09:55:40,202 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-07-19 09:55:40,202 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 14 states have internal predecessors, (51), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 49 [2022-07-19 09:55:40,203 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:55:40,203 INFO L225 Difference]: With dead ends: 152 [2022-07-19 09:55:40,203 INFO L226 Difference]: Without dead ends: 80 [2022-07-19 09:55:40,204 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 92 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 64 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=82, Invalid=224, Unknown=0, NotChecked=0, Total=306 [2022-07-19 09:55:40,205 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 68 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 193 mSolverCounterSat, 64 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 257 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 64 IncrementalHoareTripleChecker+Valid, 193 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 09:55:40,205 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [68 Valid, 67 Invalid, 257 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [64 Valid, 193 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 09:55:40,206 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2022-07-19 09:55:40,219 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 79. [2022-07-19 09:55:40,219 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 78 states have (on average 1.1538461538461537) internal successors, (90), 78 states have internal predecessors, (90), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:40,220 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 90 transitions. [2022-07-19 09:55:40,221 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 90 transitions. Word has length 49 [2022-07-19 09:55:40,221 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:55:40,221 INFO L495 AbstractCegarLoop]: Abstraction has 79 states and 90 transitions. [2022-07-19 09:55:40,221 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 14 states have internal predecessors, (51), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:40,221 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 90 transitions. [2022-07-19 09:55:40,222 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-07-19 09:55:40,223 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:55:40,223 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:55:40,242 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-07-19 09:55:40,431 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:55:40,432 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:55:40,432 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:55:40,432 INFO L85 PathProgramCache]: Analyzing trace with hash -436136292, now seen corresponding path program 5 times [2022-07-19 09:55:40,432 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:55:40,433 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [404759799] [2022-07-19 09:55:40,433 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:55:40,433 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:55:40,448 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:55:40,518 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 1 proven. 12 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2022-07-19 09:55:40,518 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:55:40,518 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [404759799] [2022-07-19 09:55:40,519 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [404759799] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:55:40,519 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [132566449] [2022-07-19 09:55:40,519 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-19 09:55:40,519 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:55:40,519 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:55:40,521 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:55:40,522 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-07-19 09:55:40,604 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2022-07-19 09:55:40,604 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:55:40,605 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 8 conjunts are in the unsatisfiable core [2022-07-19 09:55:40,607 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:55:40,677 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 4 proven. 9 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2022-07-19 09:55:40,677 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:55:40,730 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 4 proven. 9 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2022-07-19 09:55:40,731 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [132566449] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:55:40,731 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:55:40,731 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2022-07-19 09:55:40,731 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1043574140] [2022-07-19 09:55:40,731 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:55:40,731 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-07-19 09:55:40,732 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:55:40,732 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-07-19 09:55:40,732 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=131, Unknown=0, NotChecked=0, Total=182 [2022-07-19 09:55:40,732 INFO L87 Difference]: Start difference. First operand 79 states and 90 transitions. Second operand has 14 states, 14 states have (on average 4.714285714285714) internal successors, (66), 14 states have internal predecessors, (66), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:40,895 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:55:40,896 INFO L93 Difference]: Finished difference Result 125 states and 145 transitions. [2022-07-19 09:55:40,896 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-07-19 09:55:40,896 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.714285714285714) internal successors, (66), 14 states have internal predecessors, (66), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 51 [2022-07-19 09:55:40,897 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:55:40,897 INFO L225 Difference]: With dead ends: 125 [2022-07-19 09:55:40,897 INFO L226 Difference]: Without dead ends: 68 [2022-07-19 09:55:40,898 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 95 SyntacticMatches, 2 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 61 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=105, Invalid=237, Unknown=0, NotChecked=0, Total=342 [2022-07-19 09:55:40,898 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 127 mSDsluCounter, 21 mSDsCounter, 0 mSdLazyCounter, 176 mSolverCounterSat, 99 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 127 SdHoareTripleChecker+Valid, 33 SdHoareTripleChecker+Invalid, 275 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 99 IncrementalHoareTripleChecker+Valid, 176 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 09:55:40,899 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [127 Valid, 33 Invalid, 275 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [99 Valid, 176 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 09:55:40,900 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2022-07-19 09:55:40,906 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 62. [2022-07-19 09:55:40,907 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 61 states have (on average 1.1147540983606556) internal successors, (68), 61 states have internal predecessors, (68), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:40,907 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 68 transitions. [2022-07-19 09:55:40,908 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 68 transitions. Word has length 51 [2022-07-19 09:55:40,908 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:55:40,908 INFO L495 AbstractCegarLoop]: Abstraction has 62 states and 68 transitions. [2022-07-19 09:55:40,908 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.714285714285714) internal successors, (66), 14 states have internal predecessors, (66), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:55:40,908 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 68 transitions. [2022-07-19 09:55:40,910 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2022-07-19 09:55:40,910 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:55:40,910 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:55:40,936 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-07-19 09:55:41,123 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:55:41,124 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:55:41,124 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:55:41,124 INFO L85 PathProgramCache]: Analyzing trace with hash -1781065978, now seen corresponding path program 6 times [2022-07-19 09:55:41,124 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:55:41,124 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1790350941] [2022-07-19 09:55:41,124 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:55:41,124 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:55:41,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:55:43,305 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 0 proven. 63 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 09:55:43,306 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:55:43,306 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1790350941] [2022-07-19 09:55:43,306 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1790350941] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:55:43,306 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [8463518] [2022-07-19 09:55:43,307 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-07-19 09:55:43,307 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:55:43,307 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:55:43,308 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:55:43,309 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-07-19 09:55:43,365 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-07-19 09:55:43,365 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:55:43,367 INFO L263 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 89 conjunts are in the unsatisfiable core [2022-07-19 09:55:43,371 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:55:47,131 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:55:47,134 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:55:47,153 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-19 09:55:47,153 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 2 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 34 treesize of output 61 [2022-07-19 09:55:47,500 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 0 proven. 63 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 09:55:47,500 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:56:31,646 INFO L356 Elim1Store]: treesize reduction 59, result has 73.9 percent of original size [2022-07-19 09:56:31,646 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 56 treesize of output 178 [2022-07-19 09:56:35,919 INFO L356 Elim1Store]: treesize reduction 117, result has 48.2 percent of original size [2022-07-19 09:56:35,919 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 55 treesize of output 119 [2022-07-19 09:56:37,659 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 4 proven. 59 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 09:56:37,660 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [8463518] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:56:37,660 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:56:37,663 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [40, 36, 40] total 106 [2022-07-19 09:56:37,664 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [221228608] [2022-07-19 09:56:37,664 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:56:37,665 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 106 states [2022-07-19 09:56:37,665 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:56:37,666 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 106 interpolants. [2022-07-19 09:56:37,668 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1024, Invalid=10094, Unknown=12, NotChecked=0, Total=11130 [2022-07-19 09:56:37,669 INFO L87 Difference]: Start difference. First operand 62 states and 68 transitions. Second operand has 106 states, 106 states have (on average 1.6037735849056605) internal successors, (170), 106 states have internal predecessors, (170), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:56:55,327 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:56:55,327 INFO L93 Difference]: Finished difference Result 148 states and 165 transitions. [2022-07-19 09:56:55,327 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 81 states. [2022-07-19 09:56:55,328 INFO L78 Accepts]: Start accepts. Automaton has has 106 states, 106 states have (on average 1.6037735849056605) internal successors, (170), 106 states have internal predecessors, (170), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 61 [2022-07-19 09:56:55,328 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:56:55,329 INFO L225 Difference]: With dead ends: 148 [2022-07-19 09:56:55,329 INFO L226 Difference]: Without dead ends: 142 [2022-07-19 09:56:55,332 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 216 GetRequests, 47 SyntacticMatches, 23 SemanticMatches, 146 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8758 ImplicationChecksByTransitivity, 59.8s TimeCoverageRelationStatistics Valid=1822, Invalid=19918, Unknown=16, NotChecked=0, Total=21756 [2022-07-19 09:56:55,333 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 95 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 521 mSolverCounterSat, 114 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 95 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 1764 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 114 IncrementalHoareTripleChecker+Valid, 521 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 1129 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-07-19 09:56:55,333 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [95 Valid, 144 Invalid, 1764 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [114 Valid, 521 Invalid, 0 Unknown, 1129 Unchecked, 0.4s Time] [2022-07-19 09:56:55,334 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2022-07-19 09:56:55,351 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 91. [2022-07-19 09:56:55,352 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 90 states have (on average 1.1222222222222222) internal successors, (101), 90 states have internal predecessors, (101), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:56:55,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 101 transitions. [2022-07-19 09:56:55,353 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 101 transitions. Word has length 61 [2022-07-19 09:56:55,353 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:56:55,353 INFO L495 AbstractCegarLoop]: Abstraction has 91 states and 101 transitions. [2022-07-19 09:56:55,354 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 106 states, 106 states have (on average 1.6037735849056605) internal successors, (170), 106 states have internal predecessors, (170), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:56:55,354 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 101 transitions. [2022-07-19 09:56:55,356 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2022-07-19 09:56:55,356 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:56:55,360 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:56:55,388 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-07-19 09:56:55,583 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:56:55,584 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:56:55,584 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:56:55,584 INFO L85 PathProgramCache]: Analyzing trace with hash 2140781352, now seen corresponding path program 7 times [2022-07-19 09:56:55,584 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:56:55,585 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1210114009] [2022-07-19 09:56:55,585 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:56:55,585 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:56:55,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:56:55,680 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 11 proven. 14 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-07-19 09:56:55,680 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:56:55,680 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1210114009] [2022-07-19 09:56:55,681 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1210114009] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:56:55,681 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [904038086] [2022-07-19 09:56:55,681 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-07-19 09:56:55,681 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:56:55,681 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:56:55,684 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:56:55,710 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-07-19 09:56:55,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:56:55,748 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 10 conjunts are in the unsatisfiable core [2022-07-19 09:56:55,752 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:56:55,876 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-07-19 09:56:55,876 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:56:55,940 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-07-19 09:56:55,940 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [904038086] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:56:55,940 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:56:55,940 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2022-07-19 09:56:55,940 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [714495806] [2022-07-19 09:56:55,941 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:56:55,941 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-07-19 09:56:55,941 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:56:55,942 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-07-19 09:56:55,942 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=202, Unknown=0, NotChecked=0, Total=272 [2022-07-19 09:56:55,942 INFO L87 Difference]: Start difference. First operand 91 states and 101 transitions. Second operand has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:56:56,200 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:56:56,200 INFO L93 Difference]: Finished difference Result 217 states and 242 transitions. [2022-07-19 09:56:56,200 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-07-19 09:56:56,201 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 63 [2022-07-19 09:56:56,201 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:56:56,201 INFO L225 Difference]: With dead ends: 217 [2022-07-19 09:56:56,202 INFO L226 Difference]: Without dead ends: 94 [2022-07-19 09:56:56,202 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 140 GetRequests, 119 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=118, Invalid=344, Unknown=0, NotChecked=0, Total=462 [2022-07-19 09:56:56,203 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 92 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 328 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 92 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 419 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 328 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-19 09:56:56,203 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [92 Valid, 80 Invalid, 419 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 328 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-19 09:56:56,204 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2022-07-19 09:56:56,218 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 93. [2022-07-19 09:56:56,219 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 92 states have (on average 1.1195652173913044) internal successors, (103), 92 states have internal predecessors, (103), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:56:56,219 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 103 transitions. [2022-07-19 09:56:56,219 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 103 transitions. Word has length 63 [2022-07-19 09:56:56,219 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:56:56,220 INFO L495 AbstractCegarLoop]: Abstraction has 93 states and 103 transitions. [2022-07-19 09:56:56,220 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:56:56,220 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 103 transitions. [2022-07-19 09:56:56,221 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2022-07-19 09:56:56,221 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:56:56,221 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:56:56,240 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-07-19 09:56:56,431 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:56:56,432 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:56:56,432 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:56:56,432 INFO L85 PathProgramCache]: Analyzing trace with hash -784405174, now seen corresponding path program 8 times [2022-07-19 09:56:56,432 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:56:56,433 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1079646742] [2022-07-19 09:56:56,433 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:56:56,433 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:56:56,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:56:56,533 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 4 proven. 21 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-07-19 09:56:56,533 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:56:56,533 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1079646742] [2022-07-19 09:56:56,534 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1079646742] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:56:56,534 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1974749603] [2022-07-19 09:56:56,534 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-19 09:56:56,534 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:56:56,534 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:56:56,536 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:56:56,538 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-07-19 09:56:56,590 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-19 09:56:56,590 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:56:56,591 INFO L263 TraceCheckSpWp]: Trace formula consists of 203 conjuncts, 10 conjunts are in the unsatisfiable core [2022-07-19 09:56:56,593 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:56:56,674 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 9 proven. 16 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-07-19 09:56:56,674 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:56:56,713 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 9 proven. 16 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-07-19 09:56:56,713 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1974749603] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:56:56,714 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:56:56,714 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2022-07-19 09:56:56,714 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1161285757] [2022-07-19 09:56:56,714 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:56:56,715 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-07-19 09:56:56,715 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:56:56,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-07-19 09:56:56,716 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=199, Unknown=0, NotChecked=0, Total=272 [2022-07-19 09:56:56,716 INFO L87 Difference]: Start difference. First operand 93 states and 103 transitions. Second operand has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:56:56,927 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:56:56,927 INFO L93 Difference]: Finished difference Result 155 states and 175 transitions. [2022-07-19 09:56:56,927 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-07-19 09:56:56,927 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 65 [2022-07-19 09:56:56,928 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:56:56,928 INFO L225 Difference]: With dead ends: 155 [2022-07-19 09:56:56,928 INFO L226 Difference]: Without dead ends: 82 [2022-07-19 09:56:56,929 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 122 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 107 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=152, Invalid=354, Unknown=0, NotChecked=0, Total=506 [2022-07-19 09:56:56,929 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 166 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 184 mSolverCounterSat, 139 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 166 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 323 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 139 IncrementalHoareTripleChecker+Valid, 184 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-19 09:56:56,929 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [166 Valid, 29 Invalid, 323 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [139 Valid, 184 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-19 09:56:56,930 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2022-07-19 09:56:56,937 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 76. [2022-07-19 09:56:56,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 76 states, 75 states have (on average 1.0933333333333333) internal successors, (82), 75 states have internal predecessors, (82), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:56:56,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 82 transitions. [2022-07-19 09:56:56,938 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 82 transitions. Word has length 65 [2022-07-19 09:56:56,938 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:56:56,938 INFO L495 AbstractCegarLoop]: Abstraction has 76 states and 82 transitions. [2022-07-19 09:56:56,939 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 17 states have internal predecessors, (57), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:56:56,939 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 82 transitions. [2022-07-19 09:56:56,939 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-07-19 09:56:56,940 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:56:56,940 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:56:56,958 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-07-19 09:56:57,147 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-07-19 09:56:57,148 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:56:57,148 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:56:57,148 INFO L85 PathProgramCache]: Analyzing trace with hash 958143540, now seen corresponding path program 9 times [2022-07-19 09:56:57,148 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:56:57,149 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1005447601] [2022-07-19 09:56:57,149 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:56:57,149 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:56:57,230 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:57:00,417 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 0 proven. 112 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 09:57:00,418 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:57:00,418 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1005447601] [2022-07-19 09:57:00,418 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1005447601] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:57:00,418 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2098265561] [2022-07-19 09:57:00,418 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-19 09:57:00,418 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:57:00,418 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:57:00,419 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:57:00,420 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-07-19 09:57:00,490 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2022-07-19 09:57:00,490 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:57:00,493 WARN L261 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 116 conjunts are in the unsatisfiable core [2022-07-19 09:57:00,496 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:57:00,569 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2022-07-19 09:57:03,137 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:57:03,140 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:57:03,142 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:57:03,152 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-19 09:57:03,153 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 73 treesize of output 59 [2022-07-19 09:57:03,452 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 7 proven. 96 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-07-19 09:57:03,452 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:57:09,592 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 0 proven. 103 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-07-19 09:57:09,592 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2098265561] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:57:09,592 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:57:09,592 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [58, 26, 23] total 97 [2022-07-19 09:57:09,593 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1195048997] [2022-07-19 09:57:09,593 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:57:09,593 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 97 states [2022-07-19 09:57:09,593 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:57:09,594 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 97 interpolants. [2022-07-19 09:57:09,596 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=561, Invalid=8751, Unknown=0, NotChecked=0, Total=9312 [2022-07-19 09:57:09,596 INFO L87 Difference]: Start difference. First operand 76 states and 82 transitions. Second operand has 97 states, 97 states have (on average 2.134020618556701) internal successors, (207), 97 states have internal predecessors, (207), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:19,280 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:57:19,280 INFO L93 Difference]: Finished difference Result 151 states and 165 transitions. [2022-07-19 09:57:19,280 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 91 states. [2022-07-19 09:57:19,281 INFO L78 Accepts]: Start accepts. Automaton has has 97 states, 97 states have (on average 2.134020618556701) internal successors, (207), 97 states have internal predecessors, (207), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 75 [2022-07-19 09:57:19,281 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:57:19,281 INFO L225 Difference]: With dead ends: 151 [2022-07-19 09:57:19,281 INFO L226 Difference]: Without dead ends: 147 [2022-07-19 09:57:19,284 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 290 GetRequests, 101 SyntacticMatches, 19 SemanticMatches, 170 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 7972 ImplicationChecksByTransitivity, 16.7s TimeCoverageRelationStatistics Valid=1766, Invalid=27646, Unknown=0, NotChecked=0, Total=29412 [2022-07-19 09:57:19,285 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 71 mSDsluCounter, 179 mSDsCounter, 0 mSdLazyCounter, 1378 mSolverCounterSat, 289 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 71 SdHoareTripleChecker+Valid, 190 SdHoareTripleChecker+Invalid, 2664 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 289 IncrementalHoareTripleChecker+Valid, 1378 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 997 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2022-07-19 09:57:19,285 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [71 Valid, 190 Invalid, 2664 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [289 Valid, 1378 Invalid, 0 Unknown, 997 Unchecked, 0.9s Time] [2022-07-19 09:57:19,286 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 147 states. [2022-07-19 09:57:19,309 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 147 to 111. [2022-07-19 09:57:19,309 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 110 states have (on average 1.1) internal successors, (121), 110 states have internal predecessors, (121), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:19,310 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 121 transitions. [2022-07-19 09:57:19,310 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 121 transitions. Word has length 75 [2022-07-19 09:57:19,310 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:57:19,310 INFO L495 AbstractCegarLoop]: Abstraction has 111 states and 121 transitions. [2022-07-19 09:57:19,311 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 97 states, 97 states have (on average 2.134020618556701) internal successors, (207), 97 states have internal predecessors, (207), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:19,311 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 121 transitions. [2022-07-19 09:57:19,312 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2022-07-19 09:57:19,312 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:57:19,312 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:57:19,333 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-07-19 09:57:19,523 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:57:19,524 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:57:19,524 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:57:19,524 INFO L85 PathProgramCache]: Analyzing trace with hash 1706175702, now seen corresponding path program 10 times [2022-07-19 09:57:19,524 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:57:19,524 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1661876535] [2022-07-19 09:57:19,524 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:57:19,524 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:57:19,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:57:19,626 INFO L134 CoverageAnalysis]: Checked inductivity of 121 backedges. 18 proven. 23 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2022-07-19 09:57:19,626 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:57:19,626 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1661876535] [2022-07-19 09:57:19,626 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1661876535] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:57:19,626 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [709991955] [2022-07-19 09:57:19,626 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-19 09:57:19,626 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:57:19,627 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:57:19,628 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:57:19,631 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-07-19 09:57:19,694 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-19 09:57:19,694 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:57:19,695 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-19 09:57:19,696 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:57:19,827 INFO L134 CoverageAnalysis]: Checked inductivity of 121 backedges. 25 proven. 16 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2022-07-19 09:57:19,827 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:57:19,904 INFO L134 CoverageAnalysis]: Checked inductivity of 121 backedges. 25 proven. 16 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2022-07-19 09:57:19,904 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [709991955] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:57:19,904 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:57:19,905 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 20 [2022-07-19 09:57:19,905 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [480852706] [2022-07-19 09:57:19,905 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:57:19,905 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-07-19 09:57:19,905 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:57:19,905 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-07-19 09:57:19,906 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=285, Unknown=0, NotChecked=0, Total=380 [2022-07-19 09:57:19,906 INFO L87 Difference]: Start difference. First operand 111 states and 121 transitions. Second operand has 20 states, 20 states have (on average 3.15) internal successors, (63), 20 states have internal predecessors, (63), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:20,212 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:57:20,213 INFO L93 Difference]: Finished difference Result 265 states and 290 transitions. [2022-07-19 09:57:20,213 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-07-19 09:57:20,213 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 3.15) internal successors, (63), 20 states have internal predecessors, (63), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 77 [2022-07-19 09:57:20,214 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:57:20,214 INFO L225 Difference]: With dead ends: 265 [2022-07-19 09:57:20,214 INFO L226 Difference]: Without dead ends: 114 [2022-07-19 09:57:20,215 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 146 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 147 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=161, Invalid=489, Unknown=0, NotChecked=0, Total=650 [2022-07-19 09:57:20,215 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 95 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 428 mSolverCounterSat, 105 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 95 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 533 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 105 IncrementalHoareTripleChecker+Valid, 428 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-19 09:57:20,216 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [95 Valid, 93 Invalid, 533 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [105 Valid, 428 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-19 09:57:20,216 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2022-07-19 09:57:20,229 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 113. [2022-07-19 09:57:20,229 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 112 states have (on average 1.0982142857142858) internal successors, (123), 112 states have internal predecessors, (123), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:20,230 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 123 transitions. [2022-07-19 09:57:20,230 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 123 transitions. Word has length 77 [2022-07-19 09:57:20,230 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:57:20,230 INFO L495 AbstractCegarLoop]: Abstraction has 113 states and 123 transitions. [2022-07-19 09:57:20,230 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 3.15) internal successors, (63), 20 states have internal predecessors, (63), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:20,231 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 123 transitions. [2022-07-19 09:57:20,231 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2022-07-19 09:57:20,231 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:57:20,231 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:57:20,249 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-07-19 09:57:20,435 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-07-19 09:57:20,435 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:57:20,436 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:57:20,436 INFO L85 PathProgramCache]: Analyzing trace with hash 1014758264, now seen corresponding path program 11 times [2022-07-19 09:57:20,436 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:57:20,436 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2063726381] [2022-07-19 09:57:20,436 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:57:20,436 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:57:20,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:57:20,550 INFO L134 CoverageAnalysis]: Checked inductivity of 130 backedges. 9 proven. 32 refuted. 0 times theorem prover too weak. 89 trivial. 0 not checked. [2022-07-19 09:57:20,551 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:57:20,551 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2063726381] [2022-07-19 09:57:20,551 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2063726381] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:57:20,551 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1984973033] [2022-07-19 09:57:20,551 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-19 09:57:20,551 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:57:20,552 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:57:20,556 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:57:20,581 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-07-19 09:57:20,743 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2022-07-19 09:57:20,743 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:57:20,744 INFO L263 TraceCheckSpWp]: Trace formula consists of 242 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-19 09:57:20,746 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:57:20,919 INFO L134 CoverageAnalysis]: Checked inductivity of 130 backedges. 25 proven. 16 refuted. 0 times theorem prover too weak. 89 trivial. 0 not checked. [2022-07-19 09:57:20,920 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:57:21,047 INFO L134 CoverageAnalysis]: Checked inductivity of 130 backedges. 25 proven. 16 refuted. 0 times theorem prover too weak. 89 trivial. 0 not checked. [2022-07-19 09:57:21,047 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1984973033] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:57:21,047 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:57:21,047 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 29 [2022-07-19 09:57:21,048 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1102377743] [2022-07-19 09:57:21,048 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:57:21,048 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2022-07-19 09:57:21,048 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:57:21,049 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2022-07-19 09:57:21,049 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=685, Unknown=0, NotChecked=0, Total=812 [2022-07-19 09:57:21,049 INFO L87 Difference]: Start difference. First operand 113 states and 123 transitions. Second operand has 29 states, 29 states have (on average 3.3448275862068964) internal successors, (97), 29 states have internal predecessors, (97), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:21,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:57:21,468 INFO L93 Difference]: Finished difference Result 185 states and 205 transitions. [2022-07-19 09:57:21,471 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-07-19 09:57:21,472 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 29 states have (on average 3.3448275862068964) internal successors, (97), 29 states have internal predecessors, (97), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 79 [2022-07-19 09:57:21,472 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:57:21,472 INFO L225 Difference]: With dead ends: 185 [2022-07-19 09:57:21,472 INFO L226 Difference]: Without dead ends: 96 [2022-07-19 09:57:21,473 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 185 GetRequests, 150 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 296 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=241, Invalid=1091, Unknown=0, NotChecked=0, Total=1332 [2022-07-19 09:57:21,474 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 313 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 482 mSolverCounterSat, 263 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 313 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 745 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 263 IncrementalHoareTripleChecker+Valid, 482 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-19 09:57:21,474 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [313 Valid, 56 Invalid, 745 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [263 Valid, 482 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-19 09:57:21,474 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2022-07-19 09:57:21,486 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 90. [2022-07-19 09:57:21,486 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 89 states have (on average 1.0786516853932584) internal successors, (96), 89 states have internal predecessors, (96), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:21,486 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 96 transitions. [2022-07-19 09:57:21,486 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 96 transitions. Word has length 79 [2022-07-19 09:57:21,486 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:57:21,487 INFO L495 AbstractCegarLoop]: Abstraction has 90 states and 96 transitions. [2022-07-19 09:57:21,487 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 3.3448275862068964) internal successors, (97), 29 states have internal predecessors, (97), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:21,487 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 96 transitions. [2022-07-19 09:57:21,487 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2022-07-19 09:57:21,487 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:57:21,487 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:57:21,505 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-07-19 09:57:21,688 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-07-19 09:57:21,688 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:57:21,688 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:57:21,688 INFO L85 PathProgramCache]: Analyzing trace with hash -1296238366, now seen corresponding path program 12 times [2022-07-19 09:57:21,689 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:57:21,689 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1756313000] [2022-07-19 09:57:21,689 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:57:21,689 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:57:21,783 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:57:26,353 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 6 proven. 169 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 09:57:26,354 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:57:26,354 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1756313000] [2022-07-19 09:57:26,354 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1756313000] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:57:26,354 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1460290400] [2022-07-19 09:57:26,354 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-07-19 09:57:26,354 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:57:26,354 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:57:26,355 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:57:26,356 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-07-19 09:57:26,438 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 6 check-sat command(s) [2022-07-19 09:57:26,439 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:57:26,441 WARN L261 TraceCheckSpWp]: Trace formula consists of 267 conjuncts, 146 conjunts are in the unsatisfiable core [2022-07-19 09:57:26,445 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:57:26,524 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2022-07-19 09:57:30,373 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-19 09:57:30,374 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 23 [2022-07-19 09:57:30,736 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 3 proven. 171 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-07-19 09:57:30,737 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:57:40,114 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 0 proven. 159 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-07-19 09:57:40,114 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1460290400] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:57:40,114 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:57:40,115 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [68, 33, 27] total 113 [2022-07-19 09:57:40,115 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1961448110] [2022-07-19 09:57:40,115 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:57:40,115 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 113 states [2022-07-19 09:57:40,115 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:57:40,116 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 113 interpolants. [2022-07-19 09:57:40,117 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=580, Invalid=12076, Unknown=0, NotChecked=0, Total=12656 [2022-07-19 09:57:40,117 INFO L87 Difference]: Start difference. First operand 90 states and 96 transitions. Second operand has 113 states, 113 states have (on average 2.150442477876106) internal successors, (243), 113 states have internal predecessors, (243), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:51,624 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:57:51,625 INFO L93 Difference]: Finished difference Result 182 states and 196 transitions. [2022-07-19 09:57:51,625 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 103 states. [2022-07-19 09:57:51,625 INFO L78 Accepts]: Start accepts. Automaton has has 113 states, 113 states have (on average 2.150442477876106) internal successors, (243), 113 states have internal predecessors, (243), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 89 [2022-07-19 09:57:51,625 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:57:51,626 INFO L225 Difference]: With dead ends: 182 [2022-07-19 09:57:51,626 INFO L226 Difference]: Without dead ends: 178 [2022-07-19 09:57:51,628 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 330 GetRequests, 119 SyntacticMatches, 29 SemanticMatches, 182 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9692 ImplicationChecksByTransitivity, 22.0s TimeCoverageRelationStatistics Valid=1734, Invalid=31938, Unknown=0, NotChecked=0, Total=33672 [2022-07-19 09:57:51,629 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 43 mSDsluCounter, 228 mSDsCounter, 0 mSdLazyCounter, 1988 mSolverCounterSat, 269 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 239 SdHoareTripleChecker+Invalid, 3529 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 269 IncrementalHoareTripleChecker+Valid, 1988 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 1272 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2022-07-19 09:57:51,629 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [43 Valid, 239 Invalid, 3529 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [269 Valid, 1988 Invalid, 0 Unknown, 1272 Unchecked, 1.4s Time] [2022-07-19 09:57:51,630 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2022-07-19 09:57:51,654 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 131. [2022-07-19 09:57:51,655 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 130 states have (on average 1.0846153846153845) internal successors, (141), 130 states have internal predecessors, (141), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:51,655 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 141 transitions. [2022-07-19 09:57:51,655 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 141 transitions. Word has length 89 [2022-07-19 09:57:51,656 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:57:51,656 INFO L495 AbstractCegarLoop]: Abstraction has 131 states and 141 transitions. [2022-07-19 09:57:51,656 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 113 states, 113 states have (on average 2.150442477876106) internal successors, (243), 113 states have internal predecessors, (243), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:51,656 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 141 transitions. [2022-07-19 09:57:51,657 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-07-19 09:57:51,657 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:57:51,657 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:57:51,679 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-07-19 09:57:51,871 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-07-19 09:57:51,872 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:57:51,872 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:57:51,872 INFO L85 PathProgramCache]: Analyzing trace with hash -91318780, now seen corresponding path program 13 times [2022-07-19 09:57:51,872 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:57:51,872 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [934729755] [2022-07-19 09:57:51,872 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:57:51,872 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:57:51,889 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:57:52,017 INFO L134 CoverageAnalysis]: Checked inductivity of 186 backedges. 27 proven. 34 refuted. 0 times theorem prover too weak. 125 trivial. 0 not checked. [2022-07-19 09:57:52,018 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:57:52,018 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [934729755] [2022-07-19 09:57:52,018 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [934729755] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:57:52,018 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1795450094] [2022-07-19 09:57:52,018 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-07-19 09:57:52,018 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:57:52,018 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:57:52,023 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:57:52,024 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-07-19 09:57:52,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:57:52,103 INFO L263 TraceCheckSpWp]: Trace formula consists of 272 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-19 09:57:52,105 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:57:52,309 INFO L134 CoverageAnalysis]: Checked inductivity of 186 backedges. 36 proven. 25 refuted. 0 times theorem prover too weak. 125 trivial. 0 not checked. [2022-07-19 09:57:52,309 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:57:52,407 INFO L134 CoverageAnalysis]: Checked inductivity of 186 backedges. 36 proven. 25 refuted. 0 times theorem prover too weak. 125 trivial. 0 not checked. [2022-07-19 09:57:52,407 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1795450094] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:57:52,407 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:57:52,407 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 15] total 23 [2022-07-19 09:57:52,408 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1777390365] [2022-07-19 09:57:52,408 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:57:52,408 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-07-19 09:57:52,408 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:57:52,408 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-07-19 09:57:52,409 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=382, Unknown=0, NotChecked=0, Total=506 [2022-07-19 09:57:52,409 INFO L87 Difference]: Start difference. First operand 131 states and 141 transitions. Second operand has 23 states, 23 states have (on average 3.0) internal successors, (69), 23 states have internal predecessors, (69), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:52,756 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:57:52,756 INFO L93 Difference]: Finished difference Result 313 states and 338 transitions. [2022-07-19 09:57:52,757 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-07-19 09:57:52,757 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 3.0) internal successors, (69), 23 states have internal predecessors, (69), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 91 [2022-07-19 09:57:52,757 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:57:52,757 INFO L225 Difference]: With dead ends: 313 [2022-07-19 09:57:52,758 INFO L226 Difference]: Without dead ends: 134 [2022-07-19 09:57:52,758 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 202 GetRequests, 173 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 199 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=211, Invalid=659, Unknown=0, NotChecked=0, Total=870 [2022-07-19 09:57:52,759 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 109 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 497 mSolverCounterSat, 97 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 109 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 594 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 97 IncrementalHoareTripleChecker+Valid, 497 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-19 09:57:52,759 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [109 Valid, 73 Invalid, 594 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [97 Valid, 497 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-19 09:57:52,760 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 134 states. [2022-07-19 09:57:52,787 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 134 to 133. [2022-07-19 09:57:52,787 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 133 states, 132 states have (on average 1.0833333333333333) internal successors, (143), 132 states have internal predecessors, (143), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:52,787 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 143 transitions. [2022-07-19 09:57:52,788 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 143 transitions. Word has length 91 [2022-07-19 09:57:52,788 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:57:52,788 INFO L495 AbstractCegarLoop]: Abstraction has 133 states and 143 transitions. [2022-07-19 09:57:52,788 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 3.0) internal successors, (69), 23 states have internal predecessors, (69), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:52,788 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 143 transitions. [2022-07-19 09:57:52,789 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2022-07-19 09:57:52,789 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:57:52,789 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:57:52,808 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-07-19 09:57:52,996 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-07-19 09:57:52,997 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:57:52,997 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:57:52,997 INFO L85 PathProgramCache]: Analyzing trace with hash 703668518, now seen corresponding path program 14 times [2022-07-19 09:57:52,997 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:57:52,997 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2033938548] [2022-07-19 09:57:52,998 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:57:52,998 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:57:53,012 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:57:53,121 INFO L134 CoverageAnalysis]: Checked inductivity of 197 backedges. 16 proven. 45 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2022-07-19 09:57:53,121 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:57:53,121 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2033938548] [2022-07-19 09:57:53,121 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2033938548] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:57:53,121 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [490305782] [2022-07-19 09:57:53,121 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-19 09:57:53,122 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:57:53,122 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:57:53,124 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:57:53,132 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-07-19 09:57:53,214 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-19 09:57:53,214 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:57:53,216 INFO L263 TraceCheckSpWp]: Trace formula consists of 281 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-19 09:57:53,218 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:57:53,361 INFO L134 CoverageAnalysis]: Checked inductivity of 197 backedges. 25 proven. 36 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2022-07-19 09:57:53,361 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:57:53,417 INFO L134 CoverageAnalysis]: Checked inductivity of 197 backedges. 25 proven. 36 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2022-07-19 09:57:53,417 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [490305782] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:57:53,417 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:57:53,418 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 15] total 23 [2022-07-19 09:57:53,418 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1508154420] [2022-07-19 09:57:53,418 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:57:53,418 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-07-19 09:57:53,418 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:57:53,419 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-07-19 09:57:53,419 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=129, Invalid=377, Unknown=0, NotChecked=0, Total=506 [2022-07-19 09:57:53,419 INFO L87 Difference]: Start difference. First operand 133 states and 143 transitions. Second operand has 23 states, 23 states have (on average 3.0) internal successors, (69), 23 states have internal predecessors, (69), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:53,814 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:57:53,815 INFO L93 Difference]: Finished difference Result 215 states and 235 transitions. [2022-07-19 09:57:53,815 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-07-19 09:57:53,815 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 3.0) internal successors, (69), 23 states have internal predecessors, (69), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 93 [2022-07-19 09:57:53,815 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:57:53,816 INFO L225 Difference]: With dead ends: 215 [2022-07-19 09:57:53,816 INFO L226 Difference]: Without dead ends: 110 [2022-07-19 09:57:53,816 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 207 GetRequests, 176 SyntacticMatches, 2 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 229 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=273, Invalid=657, Unknown=0, NotChecked=0, Total=930 [2022-07-19 09:57:53,817 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 311 mSDsluCounter, 23 mSDsCounter, 0 mSdLazyCounter, 286 mSolverCounterSat, 275 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 311 SdHoareTripleChecker+Valid, 35 SdHoareTripleChecker+Invalid, 561 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 275 IncrementalHoareTripleChecker+Valid, 286 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-19 09:57:53,817 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [311 Valid, 35 Invalid, 561 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [275 Valid, 286 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-19 09:57:53,817 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2022-07-19 09:57:53,836 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 104. [2022-07-19 09:57:53,836 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 103 states have (on average 1.0679611650485437) internal successors, (110), 103 states have internal predecessors, (110), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:53,837 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 110 transitions. [2022-07-19 09:57:53,837 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 110 transitions. Word has length 93 [2022-07-19 09:57:53,837 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:57:53,837 INFO L495 AbstractCegarLoop]: Abstraction has 104 states and 110 transitions. [2022-07-19 09:57:53,837 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 3.0) internal successors, (69), 23 states have internal predecessors, (69), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:57:53,838 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 110 transitions. [2022-07-19 09:57:53,838 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2022-07-19 09:57:53,838 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:57:53,838 INFO L195 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:57:53,866 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-07-19 09:57:54,047 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:57:54,047 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:57:54,048 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:57:54,048 INFO L85 PathProgramCache]: Analyzing trace with hash -1101361904, now seen corresponding path program 15 times [2022-07-19 09:57:54,048 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:57:54,048 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1740703429] [2022-07-19 09:57:54,048 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:57:54,048 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:57:54,197 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:58:00,280 INFO L134 CoverageAnalysis]: Checked inductivity of 252 backedges. 0 proven. 252 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 09:58:00,281 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:58:00,281 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1740703429] [2022-07-19 09:58:00,281 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1740703429] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:58:00,281 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [115781027] [2022-07-19 09:58:00,281 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-19 09:58:00,281 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:58:00,282 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:58:00,283 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:58:00,284 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-07-19 09:58:00,396 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2022-07-19 09:58:00,396 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:58:00,399 WARN L261 TraceCheckSpWp]: Trace formula consists of 306 conjuncts, 172 conjunts are in the unsatisfiable core [2022-07-19 09:58:00,402 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:58:00,490 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2022-07-19 09:58:09,419 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:09,421 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:09,422 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:09,422 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:09,424 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:09,425 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:09,429 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:09,430 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:09,430 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:09,452 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-19 09:58:09,452 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 9 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 109 treesize of output 109 [2022-07-19 09:58:09,886 INFO L134 CoverageAnalysis]: Checked inductivity of 252 backedges. 7 proven. 236 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-07-19 09:58:09,886 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:58:22,220 INFO L134 CoverageAnalysis]: Checked inductivity of 252 backedges. 0 proven. 227 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2022-07-19 09:58:22,220 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [115781027] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:58:22,220 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:58:22,220 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [76, 36, 31] total 131 [2022-07-19 09:58:22,220 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [620140105] [2022-07-19 09:58:22,220 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:58:22,221 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 131 states [2022-07-19 09:58:22,221 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:58:22,221 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 131 interpolants. [2022-07-19 09:58:22,222 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=952, Invalid=16077, Unknown=1, NotChecked=0, Total=17030 [2022-07-19 09:58:22,223 INFO L87 Difference]: Start difference. First operand 104 states and 110 transitions. Second operand has 131 states, 131 states have (on average 2.1603053435114505) internal successors, (283), 131 states have internal predecessors, (283), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:58:36,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:58:36,310 INFO L93 Difference]: Finished difference Result 181 states and 192 transitions. [2022-07-19 09:58:36,311 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 80 states. [2022-07-19 09:58:36,311 INFO L78 Accepts]: Start accepts. Automaton has has 131 states, 131 states have (on average 2.1603053435114505) internal successors, (283), 131 states have internal predecessors, (283), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 103 [2022-07-19 09:58:36,312 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:58:36,312 INFO L225 Difference]: With dead ends: 181 [2022-07-19 09:58:36,312 INFO L226 Difference]: Without dead ends: 177 [2022-07-19 09:58:36,315 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 372 GetRequests, 137 SyntacticMatches, 32 SemanticMatches, 203 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11202 ImplicationChecksByTransitivity, 33.0s TimeCoverageRelationStatistics Valid=2245, Invalid=39574, Unknown=1, NotChecked=0, Total=41820 [2022-07-19 09:58:36,316 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 57 mSDsluCounter, 235 mSDsCounter, 0 mSdLazyCounter, 2743 mSolverCounterSat, 182 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 246 SdHoareTripleChecker+Invalid, 4215 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 182 IncrementalHoareTripleChecker+Valid, 2743 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 1290 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2022-07-19 09:58:36,316 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 246 Invalid, 4215 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [182 Valid, 2743 Invalid, 0 Unknown, 1290 Unchecked, 1.7s Time] [2022-07-19 09:58:36,316 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2022-07-19 09:58:36,350 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 165. [2022-07-19 09:58:36,350 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 165 states, 164 states have (on average 1.0731707317073171) internal successors, (176), 164 states have internal predecessors, (176), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:58:36,351 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 176 transitions. [2022-07-19 09:58:36,351 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 176 transitions. Word has length 103 [2022-07-19 09:58:36,351 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:58:36,351 INFO L495 AbstractCegarLoop]: Abstraction has 165 states and 176 transitions. [2022-07-19 09:58:36,351 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 131 states, 131 states have (on average 2.1603053435114505) internal successors, (283), 131 states have internal predecessors, (283), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:58:36,351 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 176 transitions. [2022-07-19 09:58:36,352 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2022-07-19 09:58:36,352 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:58:36,352 INFO L195 NwaCegarLoop]: trace histogram [7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:58:36,378 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2022-07-19 09:58:36,577 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-07-19 09:58:36,578 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:58:36,578 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:58:36,578 INFO L85 PathProgramCache]: Analyzing trace with hash -1793599822, now seen corresponding path program 16 times [2022-07-19 09:58:36,578 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:58:36,578 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1968745400] [2022-07-19 09:58:36,578 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:58:36,578 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:58:36,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:58:36,734 INFO L134 CoverageAnalysis]: Checked inductivity of 265 backedges. 38 proven. 47 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-07-19 09:58:36,735 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:58:36,735 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1968745400] [2022-07-19 09:58:36,735 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1968745400] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:58:36,735 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [647343039] [2022-07-19 09:58:36,735 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-19 09:58:36,735 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:58:36,735 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:58:36,736 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:58:36,737 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-07-19 09:58:36,811 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-19 09:58:36,811 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:58:36,812 INFO L263 TraceCheckSpWp]: Trace formula consists of 242 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-19 09:58:36,814 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:58:37,011 INFO L134 CoverageAnalysis]: Checked inductivity of 265 backedges. 49 proven. 36 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-07-19 09:58:37,012 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:58:37,136 INFO L134 CoverageAnalysis]: Checked inductivity of 265 backedges. 49 proven. 36 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-07-19 09:58:37,137 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [647343039] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:58:37,137 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:58:37,137 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 17] total 26 [2022-07-19 09:58:37,137 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [250922934] [2022-07-19 09:58:37,137 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:58:37,138 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-07-19 09:58:37,138 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:58:37,138 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-07-19 09:58:37,138 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=157, Invalid=493, Unknown=0, NotChecked=0, Total=650 [2022-07-19 09:58:37,139 INFO L87 Difference]: Start difference. First operand 165 states and 176 transitions. Second operand has 26 states, 26 states have (on average 2.8846153846153846) internal successors, (75), 26 states have internal predecessors, (75), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:58:37,541 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:58:37,541 INFO L93 Difference]: Finished difference Result 328 states and 350 transitions. [2022-07-19 09:58:37,541 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2022-07-19 09:58:37,542 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 2.8846153846153846) internal successors, (75), 26 states have internal predecessors, (75), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 105 [2022-07-19 09:58:37,542 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:58:37,542 INFO L225 Difference]: With dead ends: 328 [2022-07-19 09:58:37,542 INFO L226 Difference]: Without dead ends: 168 [2022-07-19 09:58:37,543 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 233 GetRequests, 200 SyntacticMatches, 1 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 258 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=268, Invalid=854, Unknown=0, NotChecked=0, Total=1122 [2022-07-19 09:58:37,544 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 114 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 576 mSolverCounterSat, 122 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 114 SdHoareTripleChecker+Valid, 87 SdHoareTripleChecker+Invalid, 698 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 122 IncrementalHoareTripleChecker+Valid, 576 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-19 09:58:37,544 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [114 Valid, 87 Invalid, 698 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [122 Valid, 576 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-19 09:58:37,545 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states. [2022-07-19 09:58:37,570 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 167. [2022-07-19 09:58:37,570 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 167 states, 166 states have (on average 1.072289156626506) internal successors, (178), 166 states have internal predecessors, (178), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:58:37,571 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 167 states to 167 states and 178 transitions. [2022-07-19 09:58:37,571 INFO L78 Accepts]: Start accepts. Automaton has 167 states and 178 transitions. Word has length 105 [2022-07-19 09:58:37,571 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:58:37,571 INFO L495 AbstractCegarLoop]: Abstraction has 167 states and 178 transitions. [2022-07-19 09:58:37,572 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 2.8846153846153846) internal successors, (75), 26 states have internal predecessors, (75), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:58:37,572 INFO L276 IsEmpty]: Start isEmpty. Operand 167 states and 178 transitions. [2022-07-19 09:58:37,572 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2022-07-19 09:58:37,572 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:58:37,573 INFO L195 NwaCegarLoop]: trace histogram [7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:58:37,590 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-07-19 09:58:37,777 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:58:37,777 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:58:37,777 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:58:37,777 INFO L85 PathProgramCache]: Analyzing trace with hash 1120878164, now seen corresponding path program 17 times [2022-07-19 09:58:37,777 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:58:37,777 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1422824478] [2022-07-19 09:58:37,777 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:58:37,777 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:58:37,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:58:37,922 INFO L134 CoverageAnalysis]: Checked inductivity of 278 backedges. 25 proven. 60 refuted. 0 times theorem prover too weak. 193 trivial. 0 not checked. [2022-07-19 09:58:37,923 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:58:37,923 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1422824478] [2022-07-19 09:58:37,923 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1422824478] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:58:37,923 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1938709816] [2022-07-19 09:58:37,923 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-19 09:58:37,923 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:58:37,923 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:58:37,928 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:58:37,930 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-07-19 09:58:38,153 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2022-07-19 09:58:38,154 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:58:38,157 INFO L263 TraceCheckSpWp]: Trace formula consists of 320 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-19 09:58:38,159 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:58:38,367 INFO L134 CoverageAnalysis]: Checked inductivity of 278 backedges. 36 proven. 49 refuted. 0 times theorem prover too weak. 193 trivial. 0 not checked. [2022-07-19 09:58:38,367 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:58:38,455 INFO L134 CoverageAnalysis]: Checked inductivity of 278 backedges. 36 proven. 49 refuted. 0 times theorem prover too weak. 193 trivial. 0 not checked. [2022-07-19 09:58:38,456 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1938709816] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:58:38,456 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:58:38,456 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 17] total 26 [2022-07-19 09:58:38,456 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1611850313] [2022-07-19 09:58:38,456 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:58:38,456 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-07-19 09:58:38,456 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:58:38,457 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-07-19 09:58:38,457 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=163, Invalid=487, Unknown=0, NotChecked=0, Total=650 [2022-07-19 09:58:38,457 INFO L87 Difference]: Start difference. First operand 167 states and 178 transitions. Second operand has 26 states, 26 states have (on average 3.769230769230769) internal successors, (98), 26 states have internal predecessors, (98), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:58:38,810 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 09:58:38,810 INFO L93 Difference]: Finished difference Result 245 states and 265 transitions. [2022-07-19 09:58:38,810 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-07-19 09:58:38,811 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 3.769230769230769) internal successors, (98), 26 states have internal predecessors, (98), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 107 [2022-07-19 09:58:38,811 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 09:58:38,811 INFO L225 Difference]: With dead ends: 245 [2022-07-19 09:58:38,811 INFO L226 Difference]: Without dead ends: 124 [2022-07-19 09:58:38,812 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 238 GetRequests, 203 SyntacticMatches, 2 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 305 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=347, Invalid=843, Unknown=0, NotChecked=0, Total=1190 [2022-07-19 09:58:38,812 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 254 mSDsluCounter, 28 mSDsCounter, 0 mSdLazyCounter, 365 mSolverCounterSat, 219 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 254 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 584 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 219 IncrementalHoareTripleChecker+Valid, 365 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-19 09:58:38,812 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [254 Valid, 40 Invalid, 584 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [219 Valid, 365 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-19 09:58:38,813 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2022-07-19 09:58:38,831 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 118. [2022-07-19 09:58:38,831 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 117 states have (on average 1.0598290598290598) internal successors, (124), 117 states have internal predecessors, (124), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:58:38,832 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 124 transitions. [2022-07-19 09:58:38,832 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 124 transitions. Word has length 107 [2022-07-19 09:58:38,832 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 09:58:38,832 INFO L495 AbstractCegarLoop]: Abstraction has 118 states and 124 transitions. [2022-07-19 09:58:38,832 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 3.769230769230769) internal successors, (98), 26 states have internal predecessors, (98), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 09:58:38,832 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 124 transitions. [2022-07-19 09:58:38,833 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2022-07-19 09:58:38,833 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 09:58:38,833 INFO L195 NwaCegarLoop]: trace histogram [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 09:58:38,851 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2022-07-19 09:58:39,038 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:58:39,038 INFO L420 AbstractCegarLoop]: === Iteration 21 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 09:58:39,038 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 09:58:39,038 INFO L85 PathProgramCache]: Analyzing trace with hash 680376510, now seen corresponding path program 18 times [2022-07-19 09:58:39,039 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 09:58:39,039 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [724526322] [2022-07-19 09:58:39,039 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 09:58:39,039 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 09:58:39,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 09:58:47,206 INFO L134 CoverageAnalysis]: Checked inductivity of 343 backedges. 34 proven. 309 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 09:58:47,206 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 09:58:47,206 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [724526322] [2022-07-19 09:58:47,207 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [724526322] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-19 09:58:47,207 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1759974605] [2022-07-19 09:58:47,207 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-07-19 09:58:47,207 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 09:58:47,207 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 09:58:47,208 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-19 09:58:47,209 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-07-19 09:58:47,314 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2022-07-19 09:58:47,314 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 09:58:47,317 WARN L261 TraceCheckSpWp]: Trace formula consists of 345 conjuncts, 192 conjunts are in the unsatisfiable core [2022-07-19 09:58:47,320 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 09:58:55,052 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,053 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,053 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,054 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,055 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,056 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,057 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,059 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,061 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,061 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,064 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,065 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,066 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,067 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,068 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,068 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,069 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,070 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,071 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,072 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,072 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,073 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,074 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,075 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,077 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,080 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,081 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,082 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,083 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,084 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-19 09:58:55,146 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-19 09:58:55,146 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 10 select indices, 10 select index equivalence classes, 30 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 45 case distinctions, treesize of input 181 treesize of output 257 [2022-07-19 09:58:55,741 INFO L134 CoverageAnalysis]: Checked inductivity of 343 backedges. 13 proven. 294 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2022-07-19 09:58:55,742 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 09:59:10,060 INFO L356 Elim1Store]: treesize reduction 1183, result has 20.9 percent of original size [2022-07-19 09:59:10,060 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 14 select indices, 14 select index equivalence classes, 0 disjoint index pairs (out of 91 index pairs), introduced 14 new quantified variables, introduced 91 case distinctions, treesize of input 134 treesize of output 332 [2022-07-19 09:59:10,761 INFO L356 Elim1Store]: treesize reduction 1345, result has 10.1 percent of original size [2022-07-19 09:59:10,761 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 14 select indices, 14 select index equivalence classes, 0 disjoint index pairs (out of 91 index pairs), introduced 14 new quantified variables, introduced 91 case distinctions, treesize of input 133 treesize of output 169 [2022-07-19 09:59:11,275 INFO L134 CoverageAnalysis]: Checked inductivity of 343 backedges. 0 proven. 307 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2022-07-19 09:59:11,276 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1759974605] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 09:59:11,276 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-19 09:59:11,276 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [87, 38, 36] total 150 [2022-07-19 09:59:11,276 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1870802116] [2022-07-19 09:59:11,276 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-19 09:59:11,276 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 150 states [2022-07-19 09:59:11,276 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 09:59:11,277 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 150 interpolants. [2022-07-19 09:59:11,278 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1279, Invalid=21071, Unknown=0, NotChecked=0, Total=22350 [2022-07-19 09:59:11,279 INFO L87 Difference]: Start difference. First operand 118 states and 124 transitions. Second operand has 150 states, 150 states have (on average 2.1333333333333333) internal successors, (320), 150 states have internal predecessors, (320), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0)