./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_hard2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 4a390ef5 Calling Ultimate with: /root/.sdkman/candidates/java/current/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 /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_hard2.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 --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 8571897e57404ad6e85df2c29745d5b56fa4d168673d3bc7c670c79b03a6c106 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-4a390ef-m [2024-10-24 01:11:40,050 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-24 01:11:40,112 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-24 01:11:40,116 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-24 01:11:40,116 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-24 01:11:40,140 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-24 01:11:40,142 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-24 01:11:40,142 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-24 01:11:40,143 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-24 01:11:40,144 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-24 01:11:40,144 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-24 01:11:40,145 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-24 01:11:40,145 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-24 01:11:40,146 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-24 01:11:40,147 INFO L153 SettingsManager]: * Use SBE=true [2024-10-24 01:11:40,148 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-24 01:11:40,148 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-24 01:11:40,148 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-24 01:11:40,148 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-24 01:11:40,149 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-24 01:11:40,149 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-24 01:11:40,149 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-24 01:11:40,152 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-24 01:11:40,152 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-24 01:11:40,152 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-24 01:11:40,152 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-24 01:11:40,153 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-24 01:11:40,153 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-24 01:11:40,153 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-24 01:11:40,153 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-24 01:11:40,154 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-24 01:11:40,154 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-24 01:11:40,154 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-24 01:11:40,154 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-24 01:11:40,155 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-24 01:11:40,155 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-24 01:11:40,155 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-24 01:11:40,155 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-24 01:11:40,156 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-24 01:11:40,156 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-24 01:11:40,156 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-24 01:11:40,156 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-24 01:11:40,157 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC 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 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 -> 8571897e57404ad6e85df2c29745d5b56fa4d168673d3bc7c670c79b03a6c106 [2024-10-24 01:11:40,404 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-24 01:11:40,429 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-24 01:11:40,432 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-24 01:11:40,434 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-24 01:11:40,434 INFO L274 PluginConnector]: CDTParser initialized [2024-10-24 01:11:40,435 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_hard2.c [2024-10-24 01:11:41,770 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-24 01:11:41,951 INFO L384 CDTParser]: Found 1 translation units. [2024-10-24 01:11:41,951 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_hard2.c [2024-10-24 01:11:41,960 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c7116b5ed/9dbb6988379d4e28b0775af4afa1d4b6/FLAGc0b28c3ea [2024-10-24 01:11:41,975 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c7116b5ed/9dbb6988379d4e28b0775af4afa1d4b6 [2024-10-24 01:11:41,978 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-24 01:11:41,980 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-24 01:11:41,982 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-24 01:11:41,982 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-24 01:11:41,987 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-24 01:11:41,988 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.10 01:11:41" (1/1) ... [2024-10-24 01:11:41,990 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@652c4cd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:41, skipping insertion in model container [2024-10-24 01:11:41,990 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.10 01:11:41" (1/1) ... [2024-10-24 01:11:42,015 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-24 01:11:42,268 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_hard2.c[1067,1080] [2024-10-24 01:11:42,284 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-24 01:11:42,297 INFO L200 MainTranslator]: Completed pre-run [2024-10-24 01:11:42,308 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_hard2.c[1067,1080] [2024-10-24 01:11:42,320 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-24 01:11:42,337 INFO L204 MainTranslator]: Completed translation [2024-10-24 01:11:42,338 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42 WrapperNode [2024-10-24 01:11:42,338 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-24 01:11:42,339 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-24 01:11:42,339 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-24 01:11:42,340 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-24 01:11:42,346 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42" (1/1) ... [2024-10-24 01:11:42,354 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42" (1/1) ... [2024-10-24 01:11:42,377 INFO L138 Inliner]: procedures = 17, calls = 90, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 78 [2024-10-24 01:11:42,378 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-24 01:11:42,378 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-24 01:11:42,378 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-24 01:11:42,378 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-24 01:11:42,386 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42" (1/1) ... [2024-10-24 01:11:42,386 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42" (1/1) ... [2024-10-24 01:11:42,389 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42" (1/1) ... [2024-10-24 01:11:42,412 INFO L175 MemorySlicer]: Split 56 memory accesses to 8 slices as follows [2, 8, 6, 8, 12, 6, 5, 9]. 21 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8, 0, 0, 0, 0, 0, 0]. The 12 writes are split as follows [0, 0, 1, 2, 3, 2, 1, 3]. [2024-10-24 01:11:42,412 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42" (1/1) ... [2024-10-24 01:11:42,412 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42" (1/1) ... [2024-10-24 01:11:42,419 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42" (1/1) ... [2024-10-24 01:11:42,421 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42" (1/1) ... [2024-10-24 01:11:42,423 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42" (1/1) ... [2024-10-24 01:11:42,424 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42" (1/1) ... [2024-10-24 01:11:42,428 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-24 01:11:42,428 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-24 01:11:42,428 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-24 01:11:42,429 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-24 01:11:42,429 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42" (1/1) ... [2024-10-24 01:11:42,434 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-24 01:11:42,445 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 01:11:42,458 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-10-24 01:11:42,461 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-10-24 01:11:42,496 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-24 01:11:42,496 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_40_to_50_0 [2024-10-24 01:11:42,497 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_40_to_50_0 [2024-10-24 01:11:42,497 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-24 01:11:42,497 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-10-24 01:11:42,497 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-10-24 01:11:42,497 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-10-24 01:11:42,497 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-10-24 01:11:42,497 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2024-10-24 01:11:42,497 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#6 [2024-10-24 01:11:42,497 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#7 [2024-10-24 01:11:42,497 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-10-24 01:11:42,498 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-10-24 01:11:42,498 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-10-24 01:11:42,498 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-10-24 01:11:42,498 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-10-24 01:11:42,498 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-10-24 01:11:42,498 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2024-10-24 01:11:42,499 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#6 [2024-10-24 01:11:42,499 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#7 [2024-10-24 01:11:42,499 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_30_to_37_0 [2024-10-24 01:11:42,499 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_30_to_37_0 [2024-10-24 01:11:42,499 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-24 01:11:42,500 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-24 01:11:42,500 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-10-24 01:11:42,500 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-10-24 01:11:42,500 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-10-24 01:11:42,500 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-10-24 01:11:42,500 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-10-24 01:11:42,500 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2024-10-24 01:11:42,501 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#6 [2024-10-24 01:11:42,501 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#7 [2024-10-24 01:11:42,501 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-24 01:11:42,501 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-24 01:11:42,501 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-10-24 01:11:42,607 INFO L238 CfgBuilder]: Building ICFG [2024-10-24 01:11:42,609 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-24 01:11:42,817 INFO L? ?]: Removed 9 outVars from TransFormulas that were not future-live. [2024-10-24 01:11:42,817 INFO L287 CfgBuilder]: Performing block encoding [2024-10-24 01:11:42,863 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-24 01:11:42,863 INFO L314 CfgBuilder]: Removed 2 assume(true) statements. [2024-10-24 01:11:42,864 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 01:11:42 BoogieIcfgContainer [2024-10-24 01:11:42,864 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-24 01:11:42,867 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-24 01:11:42,868 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-24 01:11:42,871 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-24 01:11:42,871 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.10 01:11:41" (1/3) ... [2024-10-24 01:11:42,871 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@31851594 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.10 01:11:42, skipping insertion in model container [2024-10-24 01:11:42,872 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 01:11:42" (2/3) ... [2024-10-24 01:11:42,872 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@31851594 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.10 01:11:42, skipping insertion in model container [2024-10-24 01:11:42,872 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 01:11:42" (3/3) ... [2024-10-24 01:11:42,873 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_hard2.c [2024-10-24 01:11:42,886 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-24 01:11:42,886 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-24 01:11:42,931 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-24 01:11:42,936 INFO L333 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, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, 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=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@20dc53d9, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-24 01:11:42,936 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-24 01:11:42,938 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 25 states have internal predecessors, (29), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-10-24 01:11:42,944 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-10-24 01:11:42,944 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:11:42,945 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 01:11:42,945 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:11:42,950 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:11:42,950 INFO L85 PathProgramCache]: Analyzing trace with hash -93468211, now seen corresponding path program 1 times [2024-10-24 01:11:42,957 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:11:42,957 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [324854844] [2024-10-24 01:11:42,958 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:42,958 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:11:43,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:43,571 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 01:11:43,571 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:11:43,571 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [324854844] [2024-10-24 01:11:43,572 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [324854844] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 01:11:43,572 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 01:11:43,572 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-10-24 01:11:43,578 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [234255331] [2024-10-24 01:11:43,579 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 01:11:43,584 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-10-24 01:11:43,584 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:11:43,606 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-24 01:11:43,607 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2024-10-24 01:11:43,609 INFO L87 Difference]: Start difference. First operand has 38 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 25 states have internal predecessors, (29), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 8 states, 6 states have (on average 1.0) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-24 01:11:43,833 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:11:43,833 INFO L93 Difference]: Finished difference Result 78 states and 114 transitions. [2024-10-24 01:11:43,835 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-24 01:11:43,836 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.0) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-10-24 01:11:43,837 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:11:43,844 INFO L225 Difference]: With dead ends: 78 [2024-10-24 01:11:43,845 INFO L226 Difference]: Without dead ends: 40 [2024-10-24 01:11:43,849 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-10-24 01:11:43,852 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 18 mSDsluCounter, 177 mSDsCounter, 0 mSdLazyCounter, 89 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 216 SdHoareTripleChecker+Invalid, 99 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 89 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 01:11:43,853 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 216 Invalid, 99 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 89 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 01:11:43,866 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2024-10-24 01:11:43,882 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 40. [2024-10-24 01:11:43,885 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 24 states have (on average 1.1666666666666667) internal successors, (28), 27 states have internal predecessors, (28), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-10-24 01:11:43,888 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 49 transitions. [2024-10-24 01:11:43,890 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 49 transitions. Word has length 8 [2024-10-24 01:11:43,891 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:11:43,892 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 49 transitions. [2024-10-24 01:11:43,892 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.0) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-24 01:11:43,892 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 49 transitions. [2024-10-24 01:11:43,893 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-10-24 01:11:43,893 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:11:43,893 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 01:11:43,894 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-24 01:11:43,894 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:11:43,895 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:11:43,895 INFO L85 PathProgramCache]: Analyzing trace with hash 1672762703, now seen corresponding path program 1 times [2024-10-24 01:11:43,895 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:11:43,895 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1041438036] [2024-10-24 01:11:43,896 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:43,896 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:11:43,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:44,196 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-24 01:11:44,198 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:44,203 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-24 01:11:44,203 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:11:44,204 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1041438036] [2024-10-24 01:11:44,204 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1041438036] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 01:11:44,204 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 01:11:44,204 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-10-24 01:11:44,205 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1156472262] [2024-10-24 01:11:44,206 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 01:11:44,208 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-10-24 01:11:44,208 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:11:44,209 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-24 01:11:44,210 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2024-10-24 01:11:44,210 INFO L87 Difference]: Start difference. First operand 40 states and 49 transitions. Second operand has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-24 01:11:44,383 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:11:44,383 INFO L93 Difference]: Finished difference Result 46 states and 54 transitions. [2024-10-24 01:11:44,384 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-24 01:11:44,384 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2024-10-24 01:11:44,384 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:11:44,385 INFO L225 Difference]: With dead ends: 46 [2024-10-24 01:11:44,385 INFO L226 Difference]: Without dead ends: 44 [2024-10-24 01:11:44,386 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-10-24 01:11:44,387 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 17 mSDsluCounter, 175 mSDsCounter, 0 mSdLazyCounter, 93 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 215 SdHoareTripleChecker+Invalid, 102 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 93 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 01:11:44,387 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 215 Invalid, 102 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 93 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 01:11:44,388 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2024-10-24 01:11:44,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 44. [2024-10-24 01:11:44,400 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 30 states have internal predecessors, (31), 11 states have call successors, (11), 5 states have call predecessors, (11), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-10-24 01:11:44,402 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 52 transitions. [2024-10-24 01:11:44,402 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 52 transitions. Word has length 14 [2024-10-24 01:11:44,402 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:11:44,403 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 52 transitions. [2024-10-24 01:11:44,403 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-24 01:11:44,403 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 52 transitions. [2024-10-24 01:11:44,406 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2024-10-24 01:11:44,406 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:11:44,406 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 01:11:44,406 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-24 01:11:44,406 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:11:44,407 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:11:44,407 INFO L85 PathProgramCache]: Analyzing trace with hash 588742735, now seen corresponding path program 1 times [2024-10-24 01:11:44,407 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:11:44,407 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [97618647] [2024-10-24 01:11:44,407 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:44,408 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:11:44,435 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 01:11:44,438 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [143088084] [2024-10-24 01:11:44,438 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:44,438 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:11:44,438 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 01:11:44,441 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) [2024-10-24 01:11:44,443 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-10-24 01:11:44,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:44,560 INFO L255 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 49 conjuncts are in the unsatisfiable core [2024-10-24 01:11:44,566 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 01:11:44,654 INFO L378 Elim1Store]: Elim1 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 [2024-10-24 01:11:44,661 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:44,669 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:45,040 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 01:11:45,040 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 01:11:45,194 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 01:11:45,195 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:11:45,195 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [97618647] [2024-10-24 01:11:45,196 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 01:11:45,196 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [143088084] [2024-10-24 01:11:45,196 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [143088084] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-24 01:11:45,196 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-24 01:11:45,197 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 13 [2024-10-24 01:11:45,197 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1485342299] [2024-10-24 01:11:45,197 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 01:11:45,197 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-10-24 01:11:45,197 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:11:45,198 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-24 01:11:45,198 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2024-10-24 01:11:45,198 INFO L87 Difference]: Start difference. First operand 44 states and 52 transitions. Second operand has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 01:11:45,451 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:11:45,452 INFO L93 Difference]: Finished difference Result 55 states and 65 transitions. [2024-10-24 01:11:45,454 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-24 01:11:45,455 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 20 [2024-10-24 01:11:45,455 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:11:45,457 INFO L225 Difference]: With dead ends: 55 [2024-10-24 01:11:45,457 INFO L226 Difference]: Without dead ends: 53 [2024-10-24 01:11:45,457 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 22 SyntacticMatches, 5 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=44, Invalid=196, Unknown=0, NotChecked=0, Total=240 [2024-10-24 01:11:45,460 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 15 mSDsluCounter, 168 mSDsCounter, 0 mSdLazyCounter, 107 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 207 SdHoareTripleChecker+Invalid, 116 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 107 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-24 01:11:45,461 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 207 Invalid, 116 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 107 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-24 01:11:45,462 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2024-10-24 01:11:45,477 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 48. [2024-10-24 01:11:45,477 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 33 states have internal predecessors, (34), 11 states have call successors, (11), 6 states have call predecessors, (11), 6 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-10-24 01:11:45,478 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 55 transitions. [2024-10-24 01:11:45,478 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 55 transitions. Word has length 20 [2024-10-24 01:11:45,479 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:11:45,479 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 55 transitions. [2024-10-24 01:11:45,479 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 01:11:45,479 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 55 transitions. [2024-10-24 01:11:45,480 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-10-24 01:11:45,480 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:11:45,480 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 01:11:45,497 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-24 01:11:45,682 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:11:45,683 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:11:45,683 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:11:45,684 INFO L85 PathProgramCache]: Analyzing trace with hash 1249325219, now seen corresponding path program 1 times [2024-10-24 01:11:45,684 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:11:45,684 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1135356810] [2024-10-24 01:11:45,684 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:45,684 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:11:45,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 01:11:45,729 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1361040159] [2024-10-24 01:11:45,731 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:45,731 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:11:45,731 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 01:11:45,733 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) [2024-10-24 01:11:45,735 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-10-24 01:11:45,857 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:45,859 INFO L255 TraceCheckSpWp]: Trace formula consists of 296 conjuncts, 55 conjuncts are in the unsatisfiable core [2024-10-24 01:11:45,864 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 01:11:45,877 INFO L378 Elim1Store]: Elim1 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 [2024-10-24 01:11:45,883 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:45,890 INFO L378 Elim1Store]: Elim1 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 1 [2024-10-24 01:11:46,142 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:11:46,146 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-10-24 01:11:46,177 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-10-24 01:11:46,178 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 01:11:46,320 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-10-24 01:11:46,320 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:11:46,321 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1135356810] [2024-10-24 01:11:46,321 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 01:11:46,321 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1361040159] [2024-10-24 01:11:46,321 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1361040159] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-24 01:11:46,321 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-24 01:11:46,321 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 9 [2024-10-24 01:11:46,321 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1339875526] [2024-10-24 01:11:46,321 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 01:11:46,322 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-10-24 01:11:46,322 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:11:46,322 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-24 01:11:46,323 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2024-10-24 01:11:46,323 INFO L87 Difference]: Start difference. First operand 48 states and 55 transitions. Second operand has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-24 01:11:46,518 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:11:46,519 INFO L93 Difference]: Finished difference Result 68 states and 81 transitions. [2024-10-24 01:11:46,519 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-24 01:11:46,519 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 32 [2024-10-24 01:11:46,520 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:11:46,522 INFO L225 Difference]: With dead ends: 68 [2024-10-24 01:11:46,524 INFO L226 Difference]: Without dead ends: 66 [2024-10-24 01:11:46,524 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 51 SyntacticMatches, 4 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2024-10-24 01:11:46,525 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 19 mSDsluCounter, 194 mSDsCounter, 0 mSdLazyCounter, 111 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 233 SdHoareTripleChecker+Invalid, 119 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 111 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 01:11:46,528 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 233 Invalid, 119 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 111 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 01:11:46,528 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2024-10-24 01:11:46,543 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 65. [2024-10-24 01:11:46,544 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 41 states have (on average 1.146341463414634) internal successors, (47), 45 states have internal predecessors, (47), 14 states have call successors, (14), 8 states have call predecessors, (14), 9 states have return successors, (17), 13 states have call predecessors, (17), 13 states have call successors, (17) [2024-10-24 01:11:46,546 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 78 transitions. [2024-10-24 01:11:46,548 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 78 transitions. Word has length 32 [2024-10-24 01:11:46,548 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:11:46,549 INFO L471 AbstractCegarLoop]: Abstraction has 65 states and 78 transitions. [2024-10-24 01:11:46,549 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-24 01:11:46,549 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 78 transitions. [2024-10-24 01:11:46,550 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-10-24 01:11:46,550 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:11:46,550 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 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] [2024-10-24 01:11:46,568 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-10-24 01:11:46,751 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2024-10-24 01:11:46,752 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:11:46,752 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:11:46,752 INFO L85 PathProgramCache]: Analyzing trace with hash -1316300518, now seen corresponding path program 1 times [2024-10-24 01:11:46,753 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:11:46,753 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2120707173] [2024-10-24 01:11:46,753 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:46,753 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:11:46,780 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 01:11:46,782 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [179788663] [2024-10-24 01:11:46,782 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:46,784 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:11:46,784 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 01:11:46,786 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) [2024-10-24 01:11:46,788 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-10-24 01:11:46,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:46,915 INFO L255 TraceCheckSpWp]: Trace formula consists of 311 conjuncts, 61 conjuncts are in the unsatisfiable core [2024-10-24 01:11:46,919 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 01:11:46,924 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:46,928 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:46,933 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:47,217 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-10-24 01:11:47,219 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 01:11:47,448 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:11:47,448 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2120707173] [2024-10-24 01:11:47,448 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 01:11:47,449 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [179788663] [2024-10-24 01:11:47,449 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [179788663] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 01:11:47,449 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 01:11:47,449 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2024-10-24 01:11:47,449 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [426836110] [2024-10-24 01:11:47,449 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 01:11:47,450 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-10-24 01:11:47,450 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:11:47,450 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-10-24 01:11:47,451 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2024-10-24 01:11:47,451 INFO L87 Difference]: Start difference. First operand 65 states and 78 transitions. Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (7), 5 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-10-24 01:11:47,991 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:11:47,992 INFO L93 Difference]: Finished difference Result 122 states and 139 transitions. [2024-10-24 01:11:47,992 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-10-24 01:11:47,992 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (7), 5 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 38 [2024-10-24 01:11:47,993 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:11:47,994 INFO L225 Difference]: With dead ends: 122 [2024-10-24 01:11:47,994 INFO L226 Difference]: Without dead ends: 120 [2024-10-24 01:11:47,995 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 38 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=102, Invalid=360, Unknown=0, NotChecked=0, Total=462 [2024-10-24 01:11:47,995 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 76 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 255 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 83 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 295 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 255 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-24 01:11:47,996 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [83 Valid, 113 Invalid, 295 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 255 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-24 01:11:47,996 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2024-10-24 01:11:48,015 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 118. [2024-10-24 01:11:48,016 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 76 states have (on average 1.118421052631579) internal successors, (85), 80 states have internal predecessors, (85), 22 states have call successors, (22), 16 states have call predecessors, (22), 19 states have return successors, (29), 21 states have call predecessors, (29), 20 states have call successors, (29) [2024-10-24 01:11:48,017 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 136 transitions. [2024-10-24 01:11:48,017 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 136 transitions. Word has length 38 [2024-10-24 01:11:48,017 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:11:48,017 INFO L471 AbstractCegarLoop]: Abstraction has 118 states and 136 transitions. [2024-10-24 01:11:48,018 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (7), 5 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-10-24 01:11:48,018 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 136 transitions. [2024-10-24 01:11:48,019 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-10-24 01:11:48,019 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:11:48,019 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 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] [2024-10-24 01:11:48,037 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-10-24 01:11:48,223 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:11:48,224 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:11:48,224 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:11:48,224 INFO L85 PathProgramCache]: Analyzing trace with hash -413636343, now seen corresponding path program 1 times [2024-10-24 01:11:48,224 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:11:48,225 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [820489346] [2024-10-24 01:11:48,225 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:48,225 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:11:48,259 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 01:11:48,261 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1837013277] [2024-10-24 01:11:48,261 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:48,261 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:11:48,262 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 01:11:48,263 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) [2024-10-24 01:11:48,265 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-10-24 01:11:48,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:48,390 INFO L255 TraceCheckSpWp]: Trace formula consists of 334 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-10-24 01:11:48,394 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 01:11:48,403 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:48,407 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:48,411 INFO L378 Elim1Store]: Elim1 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 [2024-10-24 01:11:48,579 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-10-24 01:11:48,651 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:11:48,654 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-10-24 01:11:48,686 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 4 proven. 30 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-10-24 01:11:48,686 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 01:11:52,891 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:11:52,891 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [820489346] [2024-10-24 01:11:52,891 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 01:11:52,892 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1837013277] [2024-10-24 01:11:52,892 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1837013277] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 01:11:52,892 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 01:11:52,892 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2024-10-24 01:11:52,892 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1478623893] [2024-10-24 01:11:52,892 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 01:11:52,893 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-10-24 01:11:52,893 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:11:52,893 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-10-24 01:11:52,894 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=105, Unknown=1, NotChecked=0, Total=132 [2024-10-24 01:11:52,894 INFO L87 Difference]: Start difference. First operand 118 states and 136 transitions. Second operand has 9 states, 8 states have (on average 3.0) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2024-10-24 01:11:53,274 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:11:53,275 INFO L93 Difference]: Finished difference Result 136 states and 155 transitions. [2024-10-24 01:11:53,275 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-24 01:11:53,275 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 3.0) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 48 [2024-10-24 01:11:53,276 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:11:53,277 INFO L225 Difference]: With dead ends: 136 [2024-10-24 01:11:53,277 INFO L226 Difference]: Without dead ends: 132 [2024-10-24 01:11:53,277 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 47 SyntacticMatches, 3 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=55, Invalid=184, Unknown=1, NotChecked=0, Total=240 [2024-10-24 01:11:53,278 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 43 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 249 mSolverCounterSat, 38 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 74 SdHoareTripleChecker+Invalid, 288 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 249 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-24 01:11:53,279 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [45 Valid, 74 Invalid, 288 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 249 Invalid, 1 Unknown, 0 Unchecked, 0.3s Time] [2024-10-24 01:11:53,280 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2024-10-24 01:11:53,309 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 128. [2024-10-24 01:11:53,310 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 128 states, 83 states have (on average 1.108433734939759) internal successors, (92), 86 states have internal predecessors, (92), 24 states have call successors, (24), 18 states have call predecessors, (24), 20 states have return successors, (30), 23 states have call predecessors, (30), 21 states have call successors, (30) [2024-10-24 01:11:53,311 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 128 states to 128 states and 146 transitions. [2024-10-24 01:11:53,311 INFO L78 Accepts]: Start accepts. Automaton has 128 states and 146 transitions. Word has length 48 [2024-10-24 01:11:53,312 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:11:53,312 INFO L471 AbstractCegarLoop]: Abstraction has 128 states and 146 transitions. [2024-10-24 01:11:53,312 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 3.0) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2024-10-24 01:11:53,312 INFO L276 IsEmpty]: Start isEmpty. Operand 128 states and 146 transitions. [2024-10-24 01:11:53,313 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-10-24 01:11:53,314 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:11:53,314 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 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] [2024-10-24 01:11:53,327 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-24 01:11:53,517 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:11:53,518 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:11:53,518 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:11:53,518 INFO L85 PathProgramCache]: Analyzing trace with hash 1419410849, now seen corresponding path program 1 times [2024-10-24 01:11:53,518 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:11:53,518 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1023428339] [2024-10-24 01:11:53,518 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:53,518 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:11:53,545 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:53,778 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 01:11:53,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:53,817 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 01:11:53,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:53,820 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-24 01:11:53,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:53,823 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-24 01:11:53,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:53,825 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-10-24 01:11:53,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:53,829 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-10-24 01:11:53,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:53,833 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-10-24 01:11:53,835 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:11:53,835 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1023428339] [2024-10-24 01:11:53,835 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1023428339] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 01:11:53,835 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 01:11:53,835 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-10-24 01:11:53,835 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1430492490] [2024-10-24 01:11:53,835 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 01:11:53,836 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-10-24 01:11:53,836 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:11:53,836 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-24 01:11:53,836 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-10-24 01:11:53,836 INFO L87 Difference]: Start difference. First operand 128 states and 146 transitions. Second operand has 8 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-24 01:11:54,051 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:11:54,051 INFO L93 Difference]: Finished difference Result 176 states and 203 transitions. [2024-10-24 01:11:54,052 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-24 01:11:54,052 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 49 [2024-10-24 01:11:54,052 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:11:54,053 INFO L225 Difference]: With dead ends: 176 [2024-10-24 01:11:54,054 INFO L226 Difference]: Without dead ends: 128 [2024-10-24 01:11:54,054 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2024-10-24 01:11:54,055 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 52 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 153 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 90 SdHoareTripleChecker+Invalid, 192 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 153 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-24 01:11:54,055 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [58 Valid, 90 Invalid, 192 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 153 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-24 01:11:54,056 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2024-10-24 01:11:54,077 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 126. [2024-10-24 01:11:54,078 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 82 states have (on average 1.0975609756097562) internal successors, (90), 85 states have internal predecessors, (90), 24 states have call successors, (24), 18 states have call predecessors, (24), 19 states have return successors, (26), 23 states have call predecessors, (26), 21 states have call successors, (26) [2024-10-24 01:11:54,079 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 140 transitions. [2024-10-24 01:11:54,079 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 140 transitions. Word has length 49 [2024-10-24 01:11:54,079 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:11:54,080 INFO L471 AbstractCegarLoop]: Abstraction has 126 states and 140 transitions. [2024-10-24 01:11:54,080 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-24 01:11:54,080 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 140 transitions. [2024-10-24 01:11:54,081 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2024-10-24 01:11:54,081 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:11:54,082 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 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, 1, 1] [2024-10-24 01:11:54,082 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-10-24 01:11:54,082 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:11:54,082 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:11:54,082 INFO L85 PathProgramCache]: Analyzing trace with hash -209116920, now seen corresponding path program 1 times [2024-10-24 01:11:54,082 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:11:54,082 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1313240017] [2024-10-24 01:11:54,083 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:54,083 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:11:54,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:54,329 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 01:11:54,333 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:54,361 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 01:11:54,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:54,364 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-24 01:11:54,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:54,368 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-24 01:11:54,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:54,382 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-10-24 01:11:54,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:54,405 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 01:11:54,406 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:54,409 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-24 01:11:54,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:54,412 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2024-10-24 01:11:54,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:54,415 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-10-24 01:11:54,416 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:11:54,416 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1313240017] [2024-10-24 01:11:54,416 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1313240017] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 01:11:54,416 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 01:11:54,416 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2024-10-24 01:11:54,416 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [433298454] [2024-10-24 01:11:54,416 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 01:11:54,417 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-10-24 01:11:54,417 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:11:54,418 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-10-24 01:11:54,418 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2024-10-24 01:11:54,418 INFO L87 Difference]: Start difference. First operand 126 states and 140 transitions. Second operand has 9 states, 8 states have (on average 2.75) internal successors, (22), 6 states have internal predecessors, (22), 3 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-10-24 01:11:54,667 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:11:54,667 INFO L93 Difference]: Finished difference Result 130 states and 144 transitions. [2024-10-24 01:11:54,668 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-24 01:11:54,668 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.75) internal successors, (22), 6 states have internal predecessors, (22), 3 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 54 [2024-10-24 01:11:54,668 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:11:54,669 INFO L225 Difference]: With dead ends: 130 [2024-10-24 01:11:54,669 INFO L226 Difference]: Without dead ends: 98 [2024-10-24 01:11:54,670 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=32, Invalid=78, Unknown=0, NotChecked=0, Total=110 [2024-10-24 01:11:54,670 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 37 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 194 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 66 SdHoareTripleChecker+Invalid, 224 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 194 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-24 01:11:54,671 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 66 Invalid, 224 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 194 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-24 01:11:54,671 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2024-10-24 01:11:54,701 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 96. [2024-10-24 01:11:54,702 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 62 states have (on average 1.1129032258064515) internal successors, (69), 65 states have internal predecessors, (69), 19 states have call successors, (19), 13 states have call predecessors, (19), 14 states have return successors, (21), 18 states have call predecessors, (21), 17 states have call successors, (21) [2024-10-24 01:11:54,703 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 109 transitions. [2024-10-24 01:11:54,703 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 109 transitions. Word has length 54 [2024-10-24 01:11:54,706 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:11:54,706 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 109 transitions. [2024-10-24 01:11:54,706 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.75) internal successors, (22), 6 states have internal predecessors, (22), 3 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-10-24 01:11:54,706 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 109 transitions. [2024-10-24 01:11:54,707 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2024-10-24 01:11:54,707 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:11:54,707 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 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] [2024-10-24 01:11:54,707 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-10-24 01:11:54,708 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:11:54,708 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:11:54,708 INFO L85 PathProgramCache]: Analyzing trace with hash 285838631, now seen corresponding path program 1 times [2024-10-24 01:11:54,708 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:11:54,708 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [260873424] [2024-10-24 01:11:54,708 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:54,708 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:11:54,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 01:11:54,751 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1063746787] [2024-10-24 01:11:54,751 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:54,752 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:11:54,752 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 01:11:54,753 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) [2024-10-24 01:11:54,755 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-10-24 01:11:54,884 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:11:54,887 INFO L255 TraceCheckSpWp]: Trace formula consists of 417 conjuncts, 79 conjuncts are in the unsatisfiable core [2024-10-24 01:11:54,891 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 01:11:54,902 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:54,906 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:54,911 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:55,252 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:11:55,261 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:11:55,479 INFO L134 CoverageAnalysis]: Checked inductivity of 109 backedges. 24 proven. 24 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2024-10-24 01:11:55,479 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 01:11:55,779 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:11:55,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [260873424] [2024-10-24 01:11:55,779 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 01:11:55,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1063746787] [2024-10-24 01:11:55,780 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1063746787] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 01:11:55,780 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 01:11:55,780 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2024-10-24 01:11:55,780 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1472387324] [2024-10-24 01:11:55,780 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 01:11:55,781 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-10-24 01:11:55,781 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:11:55,781 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-10-24 01:11:55,783 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2024-10-24 01:11:55,783 INFO L87 Difference]: Start difference. First operand 96 states and 109 transitions. Second operand has 14 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 10 states have internal predecessors, (27), 7 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2024-10-24 01:11:56,415 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:11:56,415 INFO L93 Difference]: Finished difference Result 130 states and 148 transitions. [2024-10-24 01:11:56,415 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-10-24 01:11:56,415 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 10 states have internal predecessors, (27), 7 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) Word has length 62 [2024-10-24 01:11:56,416 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:11:56,416 INFO L225 Difference]: With dead ends: 130 [2024-10-24 01:11:56,416 INFO L226 Difference]: Without dead ends: 128 [2024-10-24 01:11:56,417 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 58 SyntacticMatches, 3 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=115, Invalid=485, Unknown=0, NotChecked=0, Total=600 [2024-10-24 01:11:56,417 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 68 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 440 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 74 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 474 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 440 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-10-24 01:11:56,418 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [74 Valid, 129 Invalid, 474 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 440 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-10-24 01:11:56,418 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2024-10-24 01:11:56,444 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 126. [2024-10-24 01:11:56,445 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 81 states have (on average 1.1111111111111112) internal successors, (90), 84 states have internal predecessors, (90), 24 states have call successors, (24), 17 states have call predecessors, (24), 20 states have return successors, (31), 24 states have call predecessors, (31), 21 states have call successors, (31) [2024-10-24 01:11:56,446 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 145 transitions. [2024-10-24 01:11:56,446 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 145 transitions. Word has length 62 [2024-10-24 01:11:56,447 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:11:56,447 INFO L471 AbstractCegarLoop]: Abstraction has 126 states and 145 transitions. [2024-10-24 01:11:56,447 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 10 states have internal predecessors, (27), 7 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2024-10-24 01:11:56,447 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 145 transitions. [2024-10-24 01:11:56,448 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2024-10-24 01:11:56,448 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:11:56,449 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 01:11:56,466 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-10-24 01:11:56,652 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:11:56,653 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:11:56,654 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:11:56,654 INFO L85 PathProgramCache]: Analyzing trace with hash -1449137932, now seen corresponding path program 2 times [2024-10-24 01:11:56,654 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:11:56,654 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [971061763] [2024-10-24 01:11:56,654 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:56,654 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:11:56,702 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 01:11:56,706 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [464057634] [2024-10-24 01:11:56,706 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-24 01:11:56,706 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:11:56,706 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 01:11:56,708 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) [2024-10-24 01:11:56,709 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-10-24 01:11:56,902 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-24 01:11:56,902 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 01:11:56,905 INFO L255 TraceCheckSpWp]: Trace formula consists of 523 conjuncts, 105 conjuncts are in the unsatisfiable core [2024-10-24 01:11:56,910 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 01:11:56,916 INFO L378 Elim1Store]: Elim1 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 [2024-10-24 01:11:56,920 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:56,925 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:57,469 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:11:57,478 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:11:57,668 INFO L134 CoverageAnalysis]: Checked inductivity of 234 backedges. 36 proven. 43 refuted. 0 times theorem prover too weak. 155 trivial. 0 not checked. [2024-10-24 01:11:57,668 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 01:11:58,287 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:11:58,287 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [971061763] [2024-10-24 01:11:58,287 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 01:11:58,287 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [464057634] [2024-10-24 01:11:58,287 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [464057634] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 01:11:58,287 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 01:11:58,287 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-10-24 01:11:58,287 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [913107925] [2024-10-24 01:11:58,288 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 01:11:58,288 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-24 01:11:58,288 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:11:58,289 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-24 01:11:58,289 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=394, Unknown=0, NotChecked=0, Total=462 [2024-10-24 01:11:58,289 INFO L87 Difference]: Start difference. First operand 126 states and 145 transitions. Second operand has 16 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 12 states have internal predecessors, (29), 8 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) [2024-10-24 01:11:59,283 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:11:59,284 INFO L93 Difference]: Finished difference Result 158 states and 181 transitions. [2024-10-24 01:11:59,284 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-10-24 01:11:59,284 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 12 states have internal predecessors, (29), 8 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) Word has length 86 [2024-10-24 01:11:59,285 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:11:59,286 INFO L225 Difference]: With dead ends: 158 [2024-10-24 01:11:59,286 INFO L226 Difference]: Without dead ends: 156 [2024-10-24 01:11:59,286 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 79 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 171 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=128, Invalid=628, Unknown=0, NotChecked=0, Total=756 [2024-10-24 01:11:59,287 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 55 mSDsluCounter, 187 mSDsCounter, 0 mSdLazyCounter, 732 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 221 SdHoareTripleChecker+Invalid, 755 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 732 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-10-24 01:11:59,288 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 221 Invalid, 755 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 732 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-10-24 01:11:59,289 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 156 states. [2024-10-24 01:11:59,311 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 156 to 128. [2024-10-24 01:11:59,312 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 128 states, 82 states have (on average 1.1097560975609757) internal successors, (91), 85 states have internal predecessors, (91), 24 states have call successors, (24), 17 states have call predecessors, (24), 21 states have return successors, (33), 25 states have call predecessors, (33), 21 states have call successors, (33) [2024-10-24 01:11:59,313 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 128 states to 128 states and 148 transitions. [2024-10-24 01:11:59,313 INFO L78 Accepts]: Start accepts. Automaton has 128 states and 148 transitions. Word has length 86 [2024-10-24 01:11:59,314 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:11:59,314 INFO L471 AbstractCegarLoop]: Abstraction has 128 states and 148 transitions. [2024-10-24 01:11:59,314 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 12 states have internal predecessors, (29), 8 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 6 states have call predecessors, (10), 6 states have call successors, (10) [2024-10-24 01:11:59,314 INFO L276 IsEmpty]: Start isEmpty. Operand 128 states and 148 transitions. [2024-10-24 01:11:59,315 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2024-10-24 01:11:59,315 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:11:59,315 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 01:11:59,331 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-10-24 01:11:59,516 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:11:59,516 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:11:59,517 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:11:59,517 INFO L85 PathProgramCache]: Analyzing trace with hash 1808661633, now seen corresponding path program 3 times [2024-10-24 01:11:59,517 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:11:59,517 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1911501535] [2024-10-24 01:11:59,517 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:11:59,517 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:11:59,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 01:11:59,561 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1917599822] [2024-10-24 01:11:59,561 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-24 01:11:59,561 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:11:59,562 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 01:11:59,563 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) [2024-10-24 01:11:59,565 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-10-24 01:11:59,750 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-10-24 01:11:59,750 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 01:11:59,754 INFO L255 TraceCheckSpWp]: Trace formula consists of 571 conjuncts, 143 conjuncts are in the unsatisfiable core [2024-10-24 01:11:59,759 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 01:11:59,769 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:59,774 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:11:59,781 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:12:00,478 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:12:00,492 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:12:00,766 INFO L134 CoverageAnalysis]: Checked inductivity of 407 backedges. 48 proven. 64 refuted. 0 times theorem prover too weak. 295 trivial. 0 not checked. [2024-10-24 01:12:00,767 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 01:12:01,605 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:12:01,605 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1911501535] [2024-10-24 01:12:01,606 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 01:12:01,606 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1917599822] [2024-10-24 01:12:01,606 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1917599822] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 01:12:01,606 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 01:12:01,606 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2024-10-24 01:12:01,606 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [444537816] [2024-10-24 01:12:01,606 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 01:12:01,606 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-10-24 01:12:01,606 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:12:01,607 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-10-24 01:12:01,607 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=474, Unknown=0, NotChecked=0, Total=552 [2024-10-24 01:12:01,607 INFO L87 Difference]: Start difference. First operand 128 states and 148 transitions. Second operand has 18 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 14 states have internal predecessors, (30), 8 states have call successors, (12), 5 states have call predecessors, (12), 6 states have return successors, (11), 7 states have call predecessors, (11), 6 states have call successors, (11) [2024-10-24 01:12:02,720 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:12:02,721 INFO L93 Difference]: Finished difference Result 160 states and 184 transitions. [2024-10-24 01:12:02,721 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-10-24 01:12:02,721 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 14 states have internal predecessors, (30), 8 states have call successors, (12), 5 states have call predecessors, (12), 6 states have return successors, (11), 7 states have call predecessors, (11), 6 states have call successors, (11) Word has length 110 [2024-10-24 01:12:02,722 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:12:02,723 INFO L225 Difference]: With dead ends: 160 [2024-10-24 01:12:02,723 INFO L226 Difference]: Without dead ends: 158 [2024-10-24 01:12:02,723 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 101 SyntacticMatches, 3 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 215 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=138, Invalid=732, Unknown=0, NotChecked=0, Total=870 [2024-10-24 01:12:02,724 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 44 mSDsluCounter, 197 mSDsCounter, 0 mSdLazyCounter, 785 mSolverCounterSat, 22 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 232 SdHoareTripleChecker+Invalid, 808 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 785 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-10-24 01:12:02,724 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 232 Invalid, 808 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 785 Invalid, 1 Unknown, 0 Unchecked, 0.9s Time] [2024-10-24 01:12:02,724 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2024-10-24 01:12:02,759 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 130. [2024-10-24 01:12:02,759 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 83 states have (on average 1.108433734939759) internal successors, (92), 86 states have internal predecessors, (92), 24 states have call successors, (24), 17 states have call predecessors, (24), 22 states have return successors, (35), 26 states have call predecessors, (35), 21 states have call successors, (35) [2024-10-24 01:12:02,760 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 151 transitions. [2024-10-24 01:12:02,760 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 151 transitions. Word has length 110 [2024-10-24 01:12:02,761 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:12:02,761 INFO L471 AbstractCegarLoop]: Abstraction has 130 states and 151 transitions. [2024-10-24 01:12:02,761 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 14 states have internal predecessors, (30), 8 states have call successors, (12), 5 states have call predecessors, (12), 6 states have return successors, (11), 7 states have call predecessors, (11), 6 states have call successors, (11) [2024-10-24 01:12:02,761 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 151 transitions. [2024-10-24 01:12:02,762 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2024-10-24 01:12:02,762 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:12:02,762 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 01:12:02,777 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-10-24 01:12:02,963 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:12:02,963 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:12:02,964 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:12:02,964 INFO L85 PathProgramCache]: Analyzing trace with hash 927979470, now seen corresponding path program 4 times [2024-10-24 01:12:02,964 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:12:02,964 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [179999819] [2024-10-24 01:12:02,964 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:12:02,964 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:12:03,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 01:12:03,007 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [902671122] [2024-10-24 01:12:03,007 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-10-24 01:12:03,007 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:12:03,007 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 01:12:03,009 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) [2024-10-24 01:12:03,010 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-10-24 01:12:03,215 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-10-24 01:12:03,216 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 01:12:03,219 INFO L255 TraceCheckSpWp]: Trace formula consists of 612 conjuncts, 170 conjuncts are in the unsatisfiable core [2024-10-24 01:12:03,223 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 01:12:10,758 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 17 [2024-10-24 01:12:10,762 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2024-10-24 01:12:10,764 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2024-10-24 01:12:16,795 INFO L134 CoverageAnalysis]: Checked inductivity of 628 backedges. 128 proven. 17 refuted. 1 times theorem prover too weak. 482 trivial. 0 not checked. [2024-10-24 01:12:16,795 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 01:12:21,525 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:21,525 INFO L378 Elim1Store]: Elim1 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 36 treesize of output 39 [2024-10-24 01:12:21,533 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:21,533 INFO L378 Elim1Store]: Elim1 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 28 treesize of output 31 [2024-10-24 01:12:21,541 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:21,542 INFO L378 Elim1Store]: Elim1 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 20 treesize of output 23 [2024-10-24 01:12:21,946 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:21,947 INFO L378 Elim1Store]: Elim1 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 36 treesize of output 39 [2024-10-24 01:12:21,954 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:21,954 INFO L378 Elim1Store]: Elim1 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 28 treesize of output 31 [2024-10-24 01:12:21,963 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:21,963 INFO L378 Elim1Store]: Elim1 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 20 treesize of output 23 [2024-10-24 01:12:22,253 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:22,253 INFO L378 Elim1Store]: Elim1 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 36 treesize of output 39 [2024-10-24 01:12:22,265 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:22,265 INFO L378 Elim1Store]: Elim1 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 28 treesize of output 31 [2024-10-24 01:12:22,281 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:22,281 INFO L378 Elim1Store]: Elim1 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 20 treesize of output 23 [2024-10-24 01:12:22,460 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:22,460 INFO L378 Elim1Store]: Elim1 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 36 treesize of output 39 [2024-10-24 01:12:22,470 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:22,470 INFO L378 Elim1Store]: Elim1 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 28 treesize of output 31 [2024-10-24 01:12:22,480 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:22,480 INFO L378 Elim1Store]: Elim1 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 20 treesize of output 23 [2024-10-24 01:12:26,673 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:26,674 INFO L378 Elim1Store]: Elim1 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 36 treesize of output 39 [2024-10-24 01:12:26,681 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:26,682 INFO L378 Elim1Store]: Elim1 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 28 treesize of output 31 [2024-10-24 01:12:26,691 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:26,691 INFO L378 Elim1Store]: Elim1 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 20 treesize of output 23 [2024-10-24 01:12:27,221 INFO L134 CoverageAnalysis]: Checked inductivity of 628 backedges. 73 proven. 16 refuted. 0 times theorem prover too weak. 539 trivial. 0 not checked. [2024-10-24 01:12:27,221 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:12:27,221 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [179999819] [2024-10-24 01:12:27,221 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 01:12:27,221 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [902671122] [2024-10-24 01:12:27,221 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [902671122] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 01:12:27,222 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 01:12:27,222 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 17 [2024-10-24 01:12:27,223 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1357507933] [2024-10-24 01:12:27,223 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 01:12:27,224 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-10-24 01:12:27,224 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:12:27,225 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-10-24 01:12:27,225 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=225, Unknown=3, NotChecked=0, Total=272 [2024-10-24 01:12:27,225 INFO L87 Difference]: Start difference. First operand 130 states and 151 transitions. Second operand has 17 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 14 states have internal predecessors, (30), 7 states have call successors, (11), 4 states have call predecessors, (11), 5 states have return successors, (9), 4 states have call predecessors, (9), 5 states have call successors, (9) [2024-10-24 01:12:32,609 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-10-24 01:12:36,613 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-10-24 01:12:37,829 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.17s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-10-24 01:12:37,837 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:12:37,837 INFO L93 Difference]: Finished difference Result 159 states and 180 transitions. [2024-10-24 01:12:37,837 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-10-24 01:12:37,837 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 14 states have internal predecessors, (30), 7 states have call successors, (11), 4 states have call predecessors, (11), 5 states have return successors, (9), 4 states have call predecessors, (9), 5 states have call successors, (9) Word has length 134 [2024-10-24 01:12:37,838 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:12:37,839 INFO L225 Difference]: With dead ends: 159 [2024-10-24 01:12:37,839 INFO L226 Difference]: Without dead ends: 157 [2024-10-24 01:12:37,839 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 275 GetRequests, 249 SyntacticMatches, 3 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 20.9s TimeCoverageRelationStatistics Valid=101, Invalid=496, Unknown=3, NotChecked=0, Total=600 [2024-10-24 01:12:37,840 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 30 mSDsluCounter, 188 mSDsCounter, 0 mSdLazyCounter, 419 mSolverCounterSat, 29 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 450 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 419 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.4s IncrementalHoareTripleChecker+Time [2024-10-24 01:12:37,840 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 212 Invalid, 450 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 419 Invalid, 2 Unknown, 0 Unchecked, 10.4s Time] [2024-10-24 01:12:37,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 157 states. [2024-10-24 01:12:37,871 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 157 to 123. [2024-10-24 01:12:37,871 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 80 states have (on average 1.1125) internal successors, (89), 83 states have internal predecessors, (89), 23 states have call successors, (23), 17 states have call predecessors, (23), 19 states have return successors, (26), 22 states have call predecessors, (26), 20 states have call successors, (26) [2024-10-24 01:12:37,872 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 138 transitions. [2024-10-24 01:12:37,872 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 138 transitions. Word has length 134 [2024-10-24 01:12:37,873 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:12:37,873 INFO L471 AbstractCegarLoop]: Abstraction has 123 states and 138 transitions. [2024-10-24 01:12:37,873 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 14 states have internal predecessors, (30), 7 states have call successors, (11), 4 states have call predecessors, (11), 5 states have return successors, (9), 4 states have call predecessors, (9), 5 states have call successors, (9) [2024-10-24 01:12:37,873 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 138 transitions. [2024-10-24 01:12:37,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-10-24 01:12:37,874 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:12:37,874 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 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, 1, 1, 1, 1] [2024-10-24 01:12:37,889 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-10-24 01:12:38,074 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-10-24 01:12:38,075 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:12:38,075 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:12:38,075 INFO L85 PathProgramCache]: Analyzing trace with hash -559730474, now seen corresponding path program 1 times [2024-10-24 01:12:38,075 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:12:38,075 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1916380469] [2024-10-24 01:12:38,075 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:12:38,075 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:12:38,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:38,257 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 01:12:38,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:38,369 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 01:12:38,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:38,372 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-24 01:12:38,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:38,375 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-24 01:12:38,376 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:38,381 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-10-24 01:12:38,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:38,409 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 01:12:38,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:38,412 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-24 01:12:38,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:38,414 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-24 01:12:38,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:38,427 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2024-10-24 01:12:38,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:38,508 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-24 01:12:38,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:38,514 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-24 01:12:38,515 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:38,518 INFO L134 CoverageAnalysis]: Checked inductivity of 139 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2024-10-24 01:12:38,518 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:12:38,518 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1916380469] [2024-10-24 01:12:38,518 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1916380469] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 01:12:38,518 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [43922851] [2024-10-24 01:12:38,518 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:12:38,518 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:12:38,519 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 01:12:38,520 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) [2024-10-24 01:12:38,521 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-10-24 01:12:38,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:38,687 INFO L255 TraceCheckSpWp]: Trace formula consists of 440 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-10-24 01:12:38,690 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 01:12:38,693 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:12:38,780 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:12:38,843 INFO L134 CoverageAnalysis]: Checked inductivity of 139 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2024-10-24 01:12:38,844 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 01:12:39,047 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [43922851] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 01:12:39,048 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 01:12:39,048 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 18 [2024-10-24 01:12:39,048 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1761242153] [2024-10-24 01:12:39,048 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 01:12:39,048 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-10-24 01:12:39,048 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:12:39,049 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-10-24 01:12:39,049 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=382, Unknown=0, NotChecked=0, Total=462 [2024-10-24 01:12:39,049 INFO L87 Difference]: Start difference. First operand 123 states and 138 transitions. Second operand has 18 states, 14 states have (on average 2.9285714285714284) internal successors, (41), 14 states have internal predecessors, (41), 11 states have call successors, (18), 5 states have call predecessors, (18), 6 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) [2024-10-24 01:12:39,466 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:12:39,466 INFO L93 Difference]: Finished difference Result 128 states and 146 transitions. [2024-10-24 01:12:39,466 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-24 01:12:39,467 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 14 states have (on average 2.9285714285714284) internal successors, (41), 14 states have internal predecessors, (41), 11 states have call successors, (18), 5 states have call predecessors, (18), 6 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) Word has length 72 [2024-10-24 01:12:39,467 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:12:39,468 INFO L225 Difference]: With dead ends: 128 [2024-10-24 01:12:39,468 INFO L226 Difference]: Without dead ends: 116 [2024-10-24 01:12:39,468 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 112 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 164 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=153, Invalid=659, Unknown=0, NotChecked=0, Total=812 [2024-10-24 01:12:39,469 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 46 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 526 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 565 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 526 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-24 01:12:39,469 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 99 Invalid, 565 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 526 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-24 01:12:39,469 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2024-10-24 01:12:39,489 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 113. [2024-10-24 01:12:39,490 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 74 states have (on average 1.0945945945945945) internal successors, (81), 76 states have internal predecessors, (81), 21 states have call successors, (21), 16 states have call predecessors, (21), 17 states have return successors, (24), 20 states have call predecessors, (24), 19 states have call successors, (24) [2024-10-24 01:12:39,491 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 126 transitions. [2024-10-24 01:12:39,491 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 126 transitions. Word has length 72 [2024-10-24 01:12:39,491 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:12:39,491 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 126 transitions. [2024-10-24 01:12:39,492 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 14 states have (on average 2.9285714285714284) internal successors, (41), 14 states have internal predecessors, (41), 11 states have call successors, (18), 5 states have call predecessors, (18), 6 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) [2024-10-24 01:12:39,492 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 126 transitions. [2024-10-24 01:12:39,492 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-10-24 01:12:39,493 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:12:39,493 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 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] [2024-10-24 01:12:39,508 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-10-24 01:12:39,696 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-10-24 01:12:39,697 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:12:39,697 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:12:39,697 INFO L85 PathProgramCache]: Analyzing trace with hash 1185460084, now seen corresponding path program 1 times [2024-10-24 01:12:39,697 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:12:39,697 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [33302400] [2024-10-24 01:12:39,697 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:12:39,697 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:12:39,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 01:12:39,752 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1206909858] [2024-10-24 01:12:39,755 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:12:39,755 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:12:39,755 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 01:12:39,758 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) [2024-10-24 01:12:39,760 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-10-24 01:12:39,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 01:12:39,972 INFO L255 TraceCheckSpWp]: Trace formula consists of 514 conjuncts, 192 conjuncts are in the unsatisfiable core [2024-10-24 01:12:39,978 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 01:12:39,986 INFO L378 Elim1Store]: Elim1 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 [2024-10-24 01:12:39,992 INFO L378 Elim1Store]: Elim1 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 [2024-10-24 01:12:39,998 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:12:40,005 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:12:40,013 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:12:40,022 INFO L378 Elim1Store]: Elim1 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 1 [2024-10-24 01:12:40,679 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:12:40,699 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:12:41,267 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:12:41,277 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:12:41,358 INFO L349 Elim1Store]: treesize reduction 18, result has 60.9 percent of original size [2024-10-24 01:12:41,359 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 40 treesize of output 51 [2024-10-24 01:12:41,419 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-10-24 01:12:41,420 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 29 [2024-10-24 01:12:41,768 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:41,769 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 92 treesize of output 184 [2024-10-24 01:12:41,820 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:41,820 INFO L378 Elim1Store]: Elim1 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 68 treesize of output 112 [2024-10-24 01:12:42,069 INFO L134 CoverageAnalysis]: Checked inductivity of 142 backedges. 48 proven. 29 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-10-24 01:12:42,069 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 01:12:47,718 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:12:47,718 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [33302400] [2024-10-24 01:12:47,719 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 01:12:47,719 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1206909858] [2024-10-24 01:12:47,719 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1206909858] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 01:12:47,719 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 01:12:47,719 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2024-10-24 01:12:47,719 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2136676985] [2024-10-24 01:12:47,719 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 01:12:47,720 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-10-24 01:12:47,720 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:12:47,720 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-10-24 01:12:47,721 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=716, Unknown=0, NotChecked=0, Total=812 [2024-10-24 01:12:47,721 INFO L87 Difference]: Start difference. First operand 113 states and 126 transitions. Second operand has 19 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 14 states have internal predecessors, (32), 8 states have call successors, (13), 6 states have call predecessors, (13), 4 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2024-10-24 01:12:49,593 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:12:49,594 INFO L93 Difference]: Finished difference Result 155 states and 182 transitions. [2024-10-24 01:12:49,594 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-24 01:12:49,595 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 14 states have internal predecessors, (32), 8 states have call successors, (13), 6 states have call predecessors, (13), 4 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) Word has length 73 [2024-10-24 01:12:49,595 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:12:49,596 INFO L225 Difference]: With dead ends: 155 [2024-10-24 01:12:49,596 INFO L226 Difference]: Without dead ends: 153 [2024-10-24 01:12:49,597 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 68 SyntacticMatches, 5 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 336 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=161, Invalid=1099, Unknown=0, NotChecked=0, Total=1260 [2024-10-24 01:12:49,597 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 66 mSDsluCounter, 171 mSDsCounter, 0 mSdLazyCounter, 720 mSolverCounterSat, 32 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 202 SdHoareTripleChecker+Invalid, 754 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 720 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-10-24 01:12:49,597 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 202 Invalid, 754 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 720 Invalid, 2 Unknown, 0 Unchecked, 1.2s Time] [2024-10-24 01:12:49,598 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2024-10-24 01:12:49,647 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 149. [2024-10-24 01:12:49,648 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 149 states, 98 states have (on average 1.1020408163265305) internal successors, (108), 100 states have internal predecessors, (108), 27 states have call successors, (27), 21 states have call predecessors, (27), 23 states have return successors, (36), 27 states have call predecessors, (36), 25 states have call successors, (36) [2024-10-24 01:12:49,649 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 171 transitions. [2024-10-24 01:12:49,649 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 171 transitions. Word has length 73 [2024-10-24 01:12:49,650 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:12:49,650 INFO L471 AbstractCegarLoop]: Abstraction has 149 states and 171 transitions. [2024-10-24 01:12:49,650 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 14 states have internal predecessors, (32), 8 states have call successors, (13), 6 states have call predecessors, (13), 4 states have return successors, (10), 5 states have call predecessors, (10), 5 states have call successors, (10) [2024-10-24 01:12:49,650 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 171 transitions. [2024-10-24 01:12:49,651 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2024-10-24 01:12:49,652 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:12:49,652 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 01:12:49,672 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-10-24 01:12:49,856 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-10-24 01:12:49,857 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:12:49,857 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:12:49,857 INFO L85 PathProgramCache]: Analyzing trace with hash -480452217, now seen corresponding path program 2 times [2024-10-24 01:12:49,857 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:12:49,857 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1053518749] [2024-10-24 01:12:49,858 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:12:49,858 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:12:49,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 01:12:49,903 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1622291358] [2024-10-24 01:12:49,903 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-24 01:12:49,904 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:12:49,904 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 01:12:49,905 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) [2024-10-24 01:12:49,908 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-10-24 01:12:50,130 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-24 01:12:50,130 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 01:12:50,134 INFO L255 TraceCheckSpWp]: Trace formula consists of 620 conjuncts, 201 conjuncts are in the unsatisfiable core [2024-10-24 01:12:50,140 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 01:12:50,145 INFO L378 Elim1Store]: Elim1 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 1 [2024-10-24 01:12:50,146 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:12:50,150 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:12:50,154 INFO L378 Elim1Store]: Elim1 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 [2024-10-24 01:12:50,160 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:12:50,165 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:12:51,069 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:12:51,083 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:12:51,638 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:12:51,651 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:12:51,710 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-10-24 01:12:51,711 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 29 [2024-10-24 01:12:51,748 INFO L349 Elim1Store]: treesize reduction 18, result has 60.9 percent of original size [2024-10-24 01:12:51,749 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 40 treesize of output 51 [2024-10-24 01:12:52,008 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:52,008 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 88 treesize of output 172 [2024-10-24 01:12:52,047 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:12:52,048 INFO L378 Elim1Store]: Elim1 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 140 treesize of output 168 [2024-10-24 01:12:52,231 INFO L134 CoverageAnalysis]: Checked inductivity of 279 backedges. 72 proven. 48 refuted. 0 times theorem prover too weak. 159 trivial. 0 not checked. [2024-10-24 01:12:52,231 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 01:12:59,939 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 01:12:59,940 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1053518749] [2024-10-24 01:12:59,940 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 01:12:59,940 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1622291358] [2024-10-24 01:12:59,940 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1622291358] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 01:12:59,940 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 01:12:59,940 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2024-10-24 01:12:59,940 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [628693882] [2024-10-24 01:12:59,940 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 01:12:59,940 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-10-24 01:12:59,940 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 01:12:59,941 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-10-24 01:12:59,941 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=723, Unknown=1, NotChecked=0, Total=812 [2024-10-24 01:12:59,942 INFO L87 Difference]: Start difference. First operand 149 states and 171 transitions. Second operand has 19 states, 15 states have (on average 2.2666666666666666) internal successors, (34), 14 states have internal predecessors, (34), 9 states have call successors, (14), 6 states have call predecessors, (14), 5 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) [2024-10-24 01:13:01,934 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 01:13:01,934 INFO L93 Difference]: Finished difference Result 191 states and 227 transitions. [2024-10-24 01:13:01,934 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-24 01:13:01,934 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 15 states have (on average 2.2666666666666666) internal successors, (34), 14 states have internal predecessors, (34), 9 states have call successors, (14), 6 states have call predecessors, (14), 5 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) Word has length 97 [2024-10-24 01:13:01,935 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 01:13:01,936 INFO L225 Difference]: With dead ends: 191 [2024-10-24 01:13:01,936 INFO L226 Difference]: Without dead ends: 189 [2024-10-24 01:13:01,936 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 92 SyntacticMatches, 5 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 325 ImplicationChecksByTransitivity, 6.5s TimeCoverageRelationStatistics Valid=135, Invalid=1054, Unknown=1, NotChecked=0, Total=1190 [2024-10-24 01:13:01,937 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 48 mSDsluCounter, 247 mSDsCounter, 0 mSdLazyCounter, 972 mSolverCounterSat, 21 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 287 SdHoareTripleChecker+Invalid, 995 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 972 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-10-24 01:13:01,937 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 287 Invalid, 995 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 972 Invalid, 2 Unknown, 0 Unchecked, 1.5s Time] [2024-10-24 01:13:01,938 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2024-10-24 01:13:01,973 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 151. [2024-10-24 01:13:01,974 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 151 states, 99 states have (on average 1.101010101010101) internal successors, (109), 101 states have internal predecessors, (109), 27 states have call successors, (27), 21 states have call predecessors, (27), 24 states have return successors, (38), 28 states have call predecessors, (38), 25 states have call successors, (38) [2024-10-24 01:13:01,974 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 151 states to 151 states and 174 transitions. [2024-10-24 01:13:01,975 INFO L78 Accepts]: Start accepts. Automaton has 151 states and 174 transitions. Word has length 97 [2024-10-24 01:13:01,975 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 01:13:01,975 INFO L471 AbstractCegarLoop]: Abstraction has 151 states and 174 transitions. [2024-10-24 01:13:01,975 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 15 states have (on average 2.2666666666666666) internal successors, (34), 14 states have internal predecessors, (34), 9 states have call successors, (14), 6 states have call predecessors, (14), 5 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) [2024-10-24 01:13:01,975 INFO L276 IsEmpty]: Start isEmpty. Operand 151 states and 174 transitions. [2024-10-24 01:13:01,976 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 122 [2024-10-24 01:13:01,976 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 01:13:01,976 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 01:13:01,996 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-10-24 01:13:02,177 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-10-24 01:13:02,177 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 01:13:02,178 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 01:13:02,178 INFO L85 PathProgramCache]: Analyzing trace with hash 76350426, now seen corresponding path program 3 times [2024-10-24 01:13:02,178 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 01:13:02,178 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [999805428] [2024-10-24 01:13:02,178 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 01:13:02,178 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 01:13:02,223 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 01:13:02,226 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1030488243] [2024-10-24 01:13:02,226 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-24 01:13:02,226 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 01:13:02,226 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 01:13:02,228 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) [2024-10-24 01:13:02,231 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-10-24 01:13:03,286 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-10-24 01:13:03,286 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 01:13:03,293 INFO L255 TraceCheckSpWp]: Trace formula consists of 651 conjuncts, 271 conjuncts are in the unsatisfiable core [2024-10-24 01:13:03,301 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 01:13:03,310 INFO L378 Elim1Store]: Elim1 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 [2024-10-24 01:13:03,319 INFO L378 Elim1Store]: Elim1 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 1 [2024-10-24 01:13:03,322 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:13:03,331 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:13:03,336 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:13:03,343 INFO L378 Elim1Store]: Elim1 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 11 treesize of output 7 [2024-10-24 01:13:05,014 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:13:05,059 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:13:05,928 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:13:05,945 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-10-24 01:13:06,035 INFO L349 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2024-10-24 01:13:06,036 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 25 [2024-10-24 01:13:06,064 INFO L349 Elim1Store]: treesize reduction 14, result has 58.8 percent of original size [2024-10-24 01:13:06,065 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 40 treesize of output 43 [2024-10-24 01:13:06,322 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:13:06,322 INFO L378 Elim1Store]: Elim1 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 72 treesize of output 112 [2024-10-24 01:13:06,350 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-24 01:13:06,351 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 44 treesize of output 52 [2024-10-24 01:13:06,481 INFO L134 CoverageAnalysis]: Checked inductivity of 464 backedges. 114 proven. 100 refuted. 0 times theorem prover too weak. 250 trivial. 0 not checked. [2024-10-24 01:13:06,482 INFO L311 TraceCheckSpWp]: Computing backward predicates...