./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3061b6dc Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.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 0464cc7a685168b5fc1a1b0dd8da6141b4b98c7c538345750bda8185cd005644 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-18 14:29:02,132 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-18 14:29:02,216 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-18 14:29:02,222 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-18 14:29:02,223 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-18 14:29:02,246 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-18 14:29:02,248 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-18 14:29:02,248 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-18 14:29:02,249 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-18 14:29:02,250 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-18 14:29:02,250 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-18 14:29:02,251 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-18 14:29:02,251 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-18 14:29:02,253 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-18 14:29:02,254 INFO L153 SettingsManager]: * Use SBE=true [2024-11-18 14:29:02,254 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-18 14:29:02,254 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-18 14:29:02,255 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-18 14:29:02,255 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-18 14:29:02,255 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-18 14:29:02,256 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-18 14:29:02,259 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-18 14:29:02,260 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-18 14:29:02,260 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-18 14:29:02,260 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-18 14:29:02,260 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-18 14:29:02,261 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-18 14:29:02,261 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-18 14:29:02,261 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-18 14:29:02,261 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-18 14:29:02,262 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-18 14:29:02,262 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-18 14:29:02,262 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 14:29:02,263 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-18 14:29:02,263 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-18 14:29:02,264 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-18 14:29:02,264 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-18 14:29:02,265 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-18 14:29:02,265 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-18 14:29:02,265 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-18 14:29:02,265 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-18 14:29:02,266 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-18 14:29:02,266 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 -> 0464cc7a685168b5fc1a1b0dd8da6141b4b98c7c538345750bda8185cd005644 [2024-11-18 14:29:02,539 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-18 14:29:02,565 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-18 14:29:02,568 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-18 14:29:02,569 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-18 14:29:02,570 INFO L274 PluginConnector]: CDTParser initialized [2024-11-18 14:29:02,571 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c [2024-11-18 14:29:03,957 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-18 14:29:04,173 INFO L384 CDTParser]: Found 1 translation units. [2024-11-18 14:29:04,178 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_dijkstra-u.c [2024-11-18 14:29:04,190 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/26dbb229e/4f82fd4587d948da83fa6a9c515bc833/FLAG71edac2a1 [2024-11-18 14:29:04,207 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/26dbb229e/4f82fd4587d948da83fa6a9c515bc833 [2024-11-18 14:29:04,209 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-18 14:29:04,211 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-18 14:29:04,214 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-18 14:29:04,214 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-18 14:29:04,219 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-18 14:29:04,220 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,221 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6858ed3a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04, skipping insertion in model container [2024-11-18 14:29:04,221 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,248 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-18 14:29:04,438 WARN L250 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_dijkstra-u.c[1076,1089] [2024-11-18 14:29:04,485 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 14:29:04,499 INFO L200 MainTranslator]: Completed pre-run [2024-11-18 14:29:04,512 WARN L250 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_dijkstra-u.c[1076,1089] [2024-11-18 14:29:04,550 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 14:29:04,573 INFO L204 MainTranslator]: Completed translation [2024-11-18 14:29:04,573 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04 WrapperNode [2024-11-18 14:29:04,574 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-18 14:29:04,575 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-18 14:29:04,575 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-18 14:29:04,575 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-18 14:29:04,581 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,591 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,621 INFO L138 Inliner]: procedures = 17, calls = 173, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 114 [2024-11-18 14:29:04,622 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-18 14:29:04,623 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-18 14:29:04,624 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-18 14:29:04,624 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-18 14:29:04,633 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,633 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,637 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,658 INFO L175 MemorySlicer]: Split 139 memory accesses to 6 slices as follows [2, 21, 30, 35, 29, 22]. 25 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0]. The 11 writes are split as follows [0, 1, 2, 3, 3, 2]. [2024-11-18 14:29:04,659 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,659 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,670 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,678 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,680 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,683 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,687 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-18 14:29:04,689 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-18 14:29:04,689 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-18 14:29:04,689 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-18 14:29:04,690 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04" (1/1) ... [2024-11-18 14:29:04,695 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 14:29:04,707 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:29:04,721 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-11-18 14:29:04,728 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-11-18 14:29:04,762 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-18 14:29:04,762 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_29_to_33_0 [2024-11-18 14:29:04,763 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_29_to_33_0 [2024-11-18 14:29:04,763 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-18 14:29:04,763 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-18 14:29:04,763 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-11-18 14:29:04,763 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-11-18 14:29:04,763 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-11-18 14:29:04,763 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2024-11-18 14:29:04,763 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-18 14:29:04,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-18 14:29:04,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-18 14:29:04,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-11-18 14:29:04,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-11-18 14:29:04,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-11-18 14:29:04,765 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2024-11-18 14:29:04,765 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_37_to_53_0 [2024-11-18 14:29:04,765 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_37_to_53_0 [2024-11-18 14:29:04,765 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-18 14:29:04,765 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-18 14:29:04,765 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-18 14:29:04,765 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-18 14:29:04,765 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-11-18 14:29:04,766 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-11-18 14:29:04,766 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-11-18 14:29:04,766 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2024-11-18 14:29:04,766 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-18 14:29:04,766 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-18 14:29:04,766 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-18 14:29:04,908 INFO L238 CfgBuilder]: Building ICFG [2024-11-18 14:29:04,910 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-18 14:29:05,245 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-11-18 14:29:05,246 INFO L287 CfgBuilder]: Performing block encoding [2024-11-18 14:29:05,260 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-18 14:29:05,260 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-18 14:29:05,261 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 02:29:05 BoogieIcfgContainer [2024-11-18 14:29:05,261 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-18 14:29:05,264 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-18 14:29:05,264 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-18 14:29:05,268 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-18 14:29:05,268 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.11 02:29:04" (1/3) ... [2024-11-18 14:29:05,269 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3d29017d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 02:29:05, skipping insertion in model container [2024-11-18 14:29:05,269 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:29:04" (2/3) ... [2024-11-18 14:29:05,269 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3d29017d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 02:29:05, skipping insertion in model container [2024-11-18 14:29:05,269 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 02:29:05" (3/3) ... [2024-11-18 14:29:05,270 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_dijkstra-u.c [2024-11-18 14:29:05,289 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-18 14:29:05,289 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-18 14:29:05,353 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-18 14:29:05,360 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;@46aecb8c, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-18 14:29:05,360 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-18 14:29:05,364 INFO L276 IsEmpty]: Start isEmpty. Operand has 47 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 32 states have internal predecessors, (37), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-18 14:29:05,370 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-18 14:29:05,370 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:29:05,371 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:29:05,371 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:29:05,376 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:29:05,376 INFO L85 PathProgramCache]: Analyzing trace with hash 2024161958, now seen corresponding path program 1 times [2024-11-18 14:29:05,382 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:29:05,383 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [660796044] [2024-11-18 14:29:05,383 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:29:05,383 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:29:05,505 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:29:05,599 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-18 14:29:05,600 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:29:05,600 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [660796044] [2024-11-18 14:29:05,601 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [660796044] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 14:29:05,601 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 14:29:05,601 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-18 14:29:05,603 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1791333902] [2024-11-18 14:29:05,603 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 14:29:05,607 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-18 14:29:05,607 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:29:05,626 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-18 14:29:05,627 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 14:29:05,629 INFO L87 Difference]: Start difference. First operand has 47 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 32 states have internal predecessors, (37), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-18 14:29:05,662 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:29:05,662 INFO L93 Difference]: Finished difference Result 91 states and 135 transitions. [2024-11-18 14:29:05,664 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-18 14:29:05,665 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (3), 2 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 16 [2024-11-18 14:29:05,666 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:29:05,672 INFO L225 Difference]: With dead ends: 91 [2024-11-18 14:29:05,672 INFO L226 Difference]: Without dead ends: 43 [2024-11-18 14:29:05,677 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 14:29:05,682 INFO L432 NwaCegarLoop]: 59 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 59 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 14:29:05,684 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 14:29:05,700 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-18 14:29:05,718 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2024-11-18 14:29:05,720 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 26 states have (on average 1.1538461538461537) internal successors, (30), 29 states have internal predecessors, (30), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-18 14:29:05,725 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 55 transitions. [2024-11-18 14:29:05,726 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 55 transitions. Word has length 16 [2024-11-18 14:29:05,727 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:29:05,727 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 55 transitions. [2024-11-18 14:29:05,727 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-18 14:29:05,728 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 55 transitions. [2024-11-18 14:29:05,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-18 14:29:05,729 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:29:05,729 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:29:05,729 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-18 14:29:05,729 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:29:05,730 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:29:05,730 INFO L85 PathProgramCache]: Analyzing trace with hash 715108188, now seen corresponding path program 1 times [2024-11-18 14:29:05,730 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:29:05,731 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1154990816] [2024-11-18 14:29:05,731 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:29:05,732 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:29:05,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:29:07,012 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-18 14:29:07,013 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:29:07,013 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1154990816] [2024-11-18 14:29:07,014 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1154990816] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 14:29:07,014 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 14:29:07,014 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2024-11-18 14:29:07,014 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [750649922] [2024-11-18 14:29:07,014 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 14:29:07,015 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-18 14:29:07,015 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:29:07,017 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-18 14:29:07,018 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2024-11-18 14:29:07,019 INFO L87 Difference]: Start difference. First operand 43 states and 55 transitions. Second operand has 13 states, 10 states have (on average 1.3) internal successors, (13), 9 states have internal predecessors, (13), 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-11-18 14:29:07,866 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:29:07,867 INFO L93 Difference]: Finished difference Result 76 states and 99 transitions. [2024-11-18 14:29:07,867 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-18 14:29:07,867 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 1.3) internal successors, (13), 9 states have internal predecessors, (13), 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 17 [2024-11-18 14:29:07,868 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:29:07,870 INFO L225 Difference]: With dead ends: 76 [2024-11-18 14:29:07,870 INFO L226 Difference]: Without dead ends: 74 [2024-11-18 14:29:07,871 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=65, Invalid=315, Unknown=0, NotChecked=0, Total=380 [2024-11-18 14:29:07,872 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 57 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 381 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 425 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 381 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-18 14:29:07,872 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 131 Invalid, 425 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 381 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-18 14:29:07,873 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2024-11-18 14:29:07,888 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 69. [2024-11-18 14:29:07,889 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 41 states have (on average 1.1219512195121952) internal successors, (46), 44 states have internal predecessors, (46), 20 states have call successors, (20), 5 states have call predecessors, (20), 7 states have return successors, (24), 19 states have call predecessors, (24), 19 states have call successors, (24) [2024-11-18 14:29:07,890 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 90 transitions. [2024-11-18 14:29:07,893 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 90 transitions. Word has length 17 [2024-11-18 14:29:07,894 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:29:07,894 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 90 transitions. [2024-11-18 14:29:07,894 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 1.3) internal successors, (13), 9 states have internal predecessors, (13), 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-11-18 14:29:07,894 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 90 transitions. [2024-11-18 14:29:07,895 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-18 14:29:07,896 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:29:07,896 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:29:07,896 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-18 14:29:07,897 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:29:07,897 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:29:07,899 INFO L85 PathProgramCache]: Analyzing trace with hash 1913135784, now seen corresponding path program 1 times [2024-11-18 14:29:07,899 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:29:07,900 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1134143990] [2024-11-18 14:29:07,900 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:29:07,900 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:29:07,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 14:29:07,956 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1659112501] [2024-11-18 14:29:07,956 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:29:07,956 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:29:07,956 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:29:07,958 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-11-18 14:29:07,960 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-11-18 14:29:08,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:29:08,238 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 67 conjuncts are in the unsatisfiable core [2024-11-18 14:29:08,252 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:29:08,308 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-11-18 14:29:08,326 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-11-18 14:29:08,332 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-11-18 14:29:08,347 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-11-18 14:29:08,700 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-11-18 14:29:08,704 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-11-18 14:29:08,773 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-18 14:29:08,773 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:29:09,007 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:29:09,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1134143990] [2024-11-18 14:29:09,008 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 14:29:09,008 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1659112501] [2024-11-18 14:29:09,008 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1659112501] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:29:09,008 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 14:29:09,011 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2024-11-18 14:29:09,012 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1452581652] [2024-11-18 14:29:09,014 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 14:29:09,014 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-18 14:29:09,014 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:29:09,015 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-18 14:29:09,015 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2024-11-18 14:29:09,015 INFO L87 Difference]: Start difference. First operand 69 states and 90 transitions. Second operand has 10 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-18 14:29:09,800 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:29:09,800 INFO L93 Difference]: Finished difference Result 92 states and 113 transitions. [2024-11-18 14:29:09,801 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-18 14:29:09,801 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 23 [2024-11-18 14:29:09,801 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:29:09,802 INFO L225 Difference]: With dead ends: 92 [2024-11-18 14:29:09,802 INFO L226 Difference]: Without dead ends: 90 [2024-11-18 14:29:09,803 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 14 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=71, Invalid=235, Unknown=0, NotChecked=0, Total=306 [2024-11-18 14:29:09,804 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 46 mSDsluCounter, 169 mSDsCounter, 0 mSdLazyCounter, 297 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 197 SdHoareTripleChecker+Invalid, 334 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 297 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-18 14:29:09,804 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 197 Invalid, 334 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 297 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-18 14:29:09,805 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2024-11-18 14:29:09,822 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 88. [2024-11-18 14:29:09,822 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 54 states have (on average 1.1296296296296295) internal successors, (61), 57 states have internal predecessors, (61), 23 states have call successors, (23), 8 states have call predecessors, (23), 10 states have return successors, (26), 22 states have call predecessors, (26), 21 states have call successors, (26) [2024-11-18 14:29:09,823 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 110 transitions. [2024-11-18 14:29:09,824 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 110 transitions. Word has length 23 [2024-11-18 14:29:09,824 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:29:09,824 INFO L471 AbstractCegarLoop]: Abstraction has 88 states and 110 transitions. [2024-11-18 14:29:09,824 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.125) internal successors, (17), 8 states have internal predecessors, (17), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-18 14:29:09,824 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 110 transitions. [2024-11-18 14:29:09,825 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-18 14:29:09,825 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:29:09,825 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:29:09,844 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-18 14:29:10,029 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-11-18 14:29:10,030 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:29:10,031 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:29:10,031 INFO L85 PathProgramCache]: Analyzing trace with hash -1510470269, now seen corresponding path program 1 times [2024-11-18 14:29:10,031 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:29:10,031 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2103853267] [2024-11-18 14:29:10,031 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:29:10,031 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:29:10,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:29:11,220 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-18 14:29:11,221 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:29:11,221 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2103853267] [2024-11-18 14:29:11,221 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2103853267] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:29:11,222 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1920124545] [2024-11-18 14:29:11,222 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:29:11,223 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:29:11,223 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:29:11,224 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-11-18 14:29:11,227 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-11-18 14:29:11,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:29:11,334 INFO L255 TraceCheckSpWp]: Trace formula consists of 217 conjuncts, 101 conjuncts are in the unsatisfiable core [2024-11-18 14:29:11,341 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:29:11,354 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-11-18 14:29:11,429 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-11-18 14:29:11,435 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-11-18 14:29:11,445 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-11-18 14:29:12,160 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-11-18 14:29:12,178 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-18 14:29:12,179 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 41 treesize of output 37 [2024-11-18 14:29:12,454 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-18 14:29:12,454 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 26 treesize of output 26 [2024-11-18 14:29:12,586 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-18 14:29:12,586 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:29:13,807 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1920124545] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:29:13,807 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 14:29:13,808 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 17] total 31 [2024-11-18 14:29:13,808 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [265814335] [2024-11-18 14:29:13,808 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 14:29:13,809 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2024-11-18 14:29:13,809 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:29:13,809 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2024-11-18 14:29:13,810 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=1299, Unknown=0, NotChecked=0, Total=1406 [2024-11-18 14:29:13,810 INFO L87 Difference]: Start difference. First operand 88 states and 110 transitions. Second operand has 31 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 23 states have internal predecessors, (30), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-18 14:29:22,959 WARN L286 SmtUtils]: Spent 8.06s on a formula simplification. DAG size of input: 88 DAG size of output: 67 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-18 14:29:33,024 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:29:33,024 INFO L93 Difference]: Finished difference Result 126 states and 160 transitions. [2024-11-18 14:29:33,025 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-11-18 14:29:33,026 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 23 states have internal predecessors, (30), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 23 [2024-11-18 14:29:33,026 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:29:33,031 INFO L225 Difference]: With dead ends: 126 [2024-11-18 14:29:33,031 INFO L226 Difference]: Without dead ends: 124 [2024-11-18 14:29:33,032 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 14 SyntacticMatches, 2 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 421 ImplicationChecksByTransitivity, 18.9s TimeCoverageRelationStatistics Valid=237, Invalid=2517, Unknown=2, NotChecked=0, Total=2756 [2024-11-18 14:29:33,033 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 103 mSDsluCounter, 336 mSDsCounter, 0 mSdLazyCounter, 1799 mSolverCounterSat, 77 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 119 SdHoareTripleChecker+Valid, 375 SdHoareTripleChecker+Invalid, 1876 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 77 IncrementalHoareTripleChecker+Valid, 1799 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2024-11-18 14:29:33,034 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [119 Valid, 375 Invalid, 1876 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [77 Valid, 1799 Invalid, 0 Unknown, 0 Unchecked, 2.0s Time] [2024-11-18 14:29:33,038 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2024-11-18 14:29:33,075 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 116. [2024-11-18 14:29:33,076 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 71 states have (on average 1.1267605633802817) internal successors, (80), 74 states have internal predecessors, (80), 30 states have call successors, (30), 11 states have call predecessors, (30), 14 states have return successors, (36), 30 states have call predecessors, (36), 28 states have call successors, (36) [2024-11-18 14:29:33,077 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 146 transitions. [2024-11-18 14:29:33,078 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 146 transitions. Word has length 23 [2024-11-18 14:29:33,078 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:29:33,078 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 146 transitions. [2024-11-18 14:29:33,079 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 23 states have internal predecessors, (30), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-18 14:29:33,079 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 146 transitions. [2024-11-18 14:29:33,080 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-18 14:29:33,080 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:29:33,080 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:29:33,099 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-18 14:29:33,284 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-11-18 14:29:33,285 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:29:33,285 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:29:33,285 INFO L85 PathProgramCache]: Analyzing trace with hash 1851427818, now seen corresponding path program 2 times [2024-11-18 14:29:33,286 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:29:33,286 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [366772880] [2024-11-18 14:29:33,286 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 14:29:33,286 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:29:33,339 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 14:29:33,340 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:29:34,525 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-18 14:29:34,525 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:29:34,525 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [366772880] [2024-11-18 14:29:34,526 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [366772880] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:29:34,526 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2003380483] [2024-11-18 14:29:34,526 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 14:29:34,526 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:29:34,526 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:29:34,531 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-11-18 14:29:34,534 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-11-18 14:29:34,636 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 14:29:34,636 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:29:34,640 INFO L255 TraceCheckSpWp]: Trace formula consists of 246 conjuncts, 110 conjuncts are in the unsatisfiable core [2024-11-18 14:29:34,644 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:29:34,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 1 [2024-11-18 14:29:34,695 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-11-18 14:29:34,704 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-11-18 14:29:34,946 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 8 treesize of output 1 [2024-11-18 14:29:35,325 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-18 14:29:35,325 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 40 treesize of output 40 [2024-11-18 14:29:47,650 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-11-18 14:29:47,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 21 treesize of output 13 [2024-11-18 14:29:47,734 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-18 14:29:47,735 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:29:48,269 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 37 treesize of output 33 [2024-11-18 14:29:49,015 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 233 treesize of output 221 [2024-11-18 14:29:49,035 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-18 14:29:49,036 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 249 treesize of output 249 [2024-11-18 14:29:50,211 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2003380483] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:29:50,211 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 14:29:50,211 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 17] total 33 [2024-11-18 14:29:50,212 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1424571861] [2024-11-18 14:29:50,212 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 14:29:50,212 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2024-11-18 14:29:50,213 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:29:50,213 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2024-11-18 14:29:50,217 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=1430, Unknown=3, NotChecked=0, Total=1560 [2024-11-18 14:29:50,217 INFO L87 Difference]: Start difference. First operand 116 states and 146 transitions. Second operand has 33 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 24 states have internal predecessors, (34), 8 states have call successors, (10), 8 states have call predecessors, (10), 4 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-18 14:29:57,418 WARN L286 SmtUtils]: Spent 6.41s on a formula simplification. DAG size of input: 70 DAG size of output: 56 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-18 14:29:58,651 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:29:58,651 INFO L93 Difference]: Finished difference Result 177 states and 227 transitions. [2024-11-18 14:29:58,652 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-18 14:29:58,652 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 24 states have internal predecessors, (34), 8 states have call successors, (10), 8 states have call predecessors, (10), 4 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 29 [2024-11-18 14:29:58,652 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:29:58,655 INFO L225 Difference]: With dead ends: 177 [2024-11-18 14:29:58,655 INFO L226 Difference]: Without dead ends: 175 [2024-11-18 14:29:58,656 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 620 ImplicationChecksByTransitivity, 21.1s TimeCoverageRelationStatistics Valid=300, Invalid=2777, Unknown=3, NotChecked=0, Total=3080 [2024-11-18 14:29:58,657 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 164 mSDsluCounter, 236 mSDsCounter, 0 mSdLazyCounter, 1036 mSolverCounterSat, 146 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 176 SdHoareTripleChecker+Valid, 260 SdHoareTripleChecker+Invalid, 1182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 146 IncrementalHoareTripleChecker+Valid, 1036 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-11-18 14:29:58,657 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [176 Valid, 260 Invalid, 1182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [146 Valid, 1036 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2024-11-18 14:29:58,658 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 175 states. [2024-11-18 14:29:58,691 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 175 to 144. [2024-11-18 14:29:58,691 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 88 states have (on average 1.1363636363636365) internal successors, (100), 92 states have internal predecessors, (100), 39 states have call successors, (39), 13 states have call predecessors, (39), 16 states have return successors, (45), 38 states have call predecessors, (45), 36 states have call successors, (45) [2024-11-18 14:29:58,693 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 184 transitions. [2024-11-18 14:29:58,693 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 184 transitions. Word has length 29 [2024-11-18 14:29:58,693 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:29:58,694 INFO L471 AbstractCegarLoop]: Abstraction has 144 states and 184 transitions. [2024-11-18 14:29:58,694 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 24 states have internal predecessors, (34), 8 states have call successors, (10), 8 states have call predecessors, (10), 4 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-18 14:29:58,694 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 184 transitions. [2024-11-18 14:29:58,695 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-18 14:29:58,695 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:29:58,695 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:29:58,711 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-18 14:29:58,895 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-11-18 14:29:58,896 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:29:58,896 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:29:58,896 INFO L85 PathProgramCache]: Analyzing trace with hash -1343310350, now seen corresponding path program 1 times [2024-11-18 14:29:58,897 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:29:58,897 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1853094024] [2024-11-18 14:29:58,897 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:29:58,897 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:29:58,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 14:29:58,937 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1812297998] [2024-11-18 14:29:58,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:29:58,938 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:29:58,938 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:29:58,942 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-11-18 14:29:58,943 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-11-18 14:29:59,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:29:59,112 INFO L255 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 97 conjuncts are in the unsatisfiable core [2024-11-18 14:29:59,116 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:29:59,121 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-11-18 14:29:59,126 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-11-18 14:29:59,132 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-11-18 14:29:59,139 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-11-18 14:29:59,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-11-18 14:29:59,523 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 26 treesize of output 14 [2024-11-18 14:29:59,532 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-11-18 14:29:59,631 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-18 14:29:59,632 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:30:00,604 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:30:00,605 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1853094024] [2024-11-18 14:30:00,605 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 14:30:00,605 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1812297998] [2024-11-18 14:30:00,605 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1812297998] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:30:00,605 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 14:30:00,605 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2024-11-18 14:30:00,605 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [743830803] [2024-11-18 14:30:00,605 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 14:30:00,606 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-18 14:30:00,606 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:30:00,606 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-18 14:30:00,606 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2024-11-18 14:30:00,607 INFO L87 Difference]: Start difference. First operand 144 states and 184 transitions. Second operand has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-18 14:30:01,498 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:30:01,498 INFO L93 Difference]: Finished difference Result 152 states and 190 transitions. [2024-11-18 14:30:01,498 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-18 14:30:01,499 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 29 [2024-11-18 14:30:01,499 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:30:01,500 INFO L225 Difference]: With dead ends: 152 [2024-11-18 14:30:01,500 INFO L226 Difference]: Without dead ends: 150 [2024-11-18 14:30:01,503 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 18 SyntacticMatches, 6 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=71, Invalid=235, Unknown=0, NotChecked=0, Total=306 [2024-11-18 14:30:01,504 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 45 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 311 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 213 SdHoareTripleChecker+Invalid, 346 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 311 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-18 14:30:01,504 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 213 Invalid, 346 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 311 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-18 14:30:01,505 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 150 states. [2024-11-18 14:30:01,546 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 150 to 148. [2024-11-18 14:30:01,546 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 91 states have (on average 1.1318681318681318) internal successors, (103), 95 states have internal predecessors, (103), 39 states have call successors, (39), 14 states have call predecessors, (39), 17 states have return successors, (45), 38 states have call predecessors, (45), 36 states have call successors, (45) [2024-11-18 14:30:01,548 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 187 transitions. [2024-11-18 14:30:01,548 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 187 transitions. Word has length 29 [2024-11-18 14:30:01,548 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:30:01,549 INFO L471 AbstractCegarLoop]: Abstraction has 148 states and 187 transitions. [2024-11-18 14:30:01,549 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-18 14:30:01,549 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 187 transitions. [2024-11-18 14:30:01,550 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-18 14:30:01,550 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:30:01,550 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-18 14:30:01,564 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-18 14:30:01,750 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-11-18 14:30:01,751 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:30:01,751 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:30:01,751 INFO L85 PathProgramCache]: Analyzing trace with hash -1540028529, now seen corresponding path program 1 times [2024-11-18 14:30:01,751 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:30:01,751 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1083568210] [2024-11-18 14:30:01,751 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:30:01,752 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:30:01,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 14:30:01,785 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [521754288] [2024-11-18 14:30:01,785 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:30:01,786 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:30:01,786 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:30:01,791 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-11-18 14:30:01,800 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-11-18 14:30:02,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:30:02,159 INFO L255 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 85 conjuncts are in the unsatisfiable core [2024-11-18 14:30:02,162 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:30:02,166 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-11-18 14:30:02,169 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-11-18 14:30:02,174 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-11-18 14:30:02,178 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-11-18 14:30:02,345 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-11-18 14:30:02,566 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-18 14:30:02,567 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 30 treesize of output 30 [2024-11-18 14:30:02,575 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-18 14:30:02,575 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 31 treesize of output 31 [2024-11-18 14:30:02,663 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-18 14:30:02,664 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:30:24,911 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:30:24,911 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1083568210] [2024-11-18 14:30:24,911 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 14:30:24,911 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [521754288] [2024-11-18 14:30:24,911 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [521754288] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:30:24,911 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 14:30:24,911 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2024-11-18 14:30:24,912 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1110630828] [2024-11-18 14:30:24,912 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 14:30:24,913 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-18 14:30:24,913 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:30:24,913 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-18 14:30:24,914 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=325, Unknown=4, NotChecked=0, Total=380 [2024-11-18 14:30:24,914 INFO L87 Difference]: Start difference. First operand 148 states and 187 transitions. Second operand has 14 states, 10 states have (on average 2.1) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-18 14:30:26,583 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:30:26,583 INFO L93 Difference]: Finished difference Result 192 states and 239 transitions. [2024-11-18 14:30:26,584 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-18 14:30:26,584 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 10 states have (on average 2.1) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 29 [2024-11-18 14:30:26,584 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:30:26,586 INFO L225 Difference]: With dead ends: 192 [2024-11-18 14:30:26,586 INFO L226 Difference]: Without dead ends: 190 [2024-11-18 14:30:26,587 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 24 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 22.0s TimeCoverageRelationStatistics Valid=99, Invalid=547, Unknown=4, NotChecked=0, Total=650 [2024-11-18 14:30:26,587 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 45 mSDsluCounter, 249 mSDsCounter, 0 mSdLazyCounter, 829 mSolverCounterSat, 33 mSolverCounterUnsat, 10 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 295 SdHoareTripleChecker+Invalid, 872 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 829 IncrementalHoareTripleChecker+Invalid, 10 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:30:26,587 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 295 Invalid, 872 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 829 Invalid, 10 Unknown, 0 Unchecked, 1.1s Time] [2024-11-18 14:30:26,588 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 190 states. [2024-11-18 14:30:26,636 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 190 to 186. [2024-11-18 14:30:26,637 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 186 states, 114 states have (on average 1.1228070175438596) internal successors, (128), 118 states have internal predecessors, (128), 49 states have call successors, (49), 18 states have call predecessors, (49), 22 states have return successors, (58), 49 states have call predecessors, (58), 45 states have call successors, (58) [2024-11-18 14:30:26,638 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 186 states to 186 states and 235 transitions. [2024-11-18 14:30:26,639 INFO L78 Accepts]: Start accepts. Automaton has 186 states and 235 transitions. Word has length 29 [2024-11-18 14:30:26,639 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:30:26,639 INFO L471 AbstractCegarLoop]: Abstraction has 186 states and 235 transitions. [2024-11-18 14:30:26,639 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 10 states have (on average 2.1) internal successors, (21), 11 states have internal predecessors, (21), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-18 14:30:26,639 INFO L276 IsEmpty]: Start isEmpty. Operand 186 states and 235 transitions. [2024-11-18 14:30:26,641 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-18 14:30:26,642 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:30:26,642 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:30:26,652 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-18 14:30:26,843 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:30:26,843 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:30:26,843 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:30:26,843 INFO L85 PathProgramCache]: Analyzing trace with hash -1260200778, now seen corresponding path program 2 times [2024-11-18 14:30:26,844 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:30:26,844 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1829824973] [2024-11-18 14:30:26,844 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 14:30:26,844 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:30:26,897 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 14:30:26,901 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 14:30:26,902 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2089075939] [2024-11-18 14:30:26,902 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 14:30:26,903 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:30:26,903 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:30:26,904 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-11-18 14:30:26,909 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-11-18 14:30:27,123 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 14:30:27,123 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:30:27,128 WARN L253 TraceCheckSpWp]: Trace formula consists of 267 conjuncts, 146 conjuncts are in the unsatisfiable core [2024-11-18 14:30:27,132 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:30:27,141 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-11-18 14:30:27,156 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-11-18 14:30:27,163 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-11-18 14:30:27,170 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-11-18 14:30:27,532 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-11-18 14:30:28,048 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-18 14:30:28,048 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 30 treesize of output 30 [2024-11-18 14:30:28,055 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-18 14:30:28,055 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 44 treesize of output 32 [2024-11-18 14:30:28,149 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-18 14:30:28,149 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:30:28,472 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:30:28,472 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1829824973] [2024-11-18 14:30:28,472 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 14:30:28,472 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2089075939] [2024-11-18 14:30:28,472 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2089075939] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:30:28,472 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 14:30:28,472 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2024-11-18 14:30:28,473 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1891876831] [2024-11-18 14:30:28,473 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 14:30:28,473 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-18 14:30:28,473 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:30:28,474 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-18 14:30:28,474 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=580, Unknown=0, NotChecked=0, Total=650 [2024-11-18 14:30:28,474 INFO L87 Difference]: Start difference. First operand 186 states and 235 transitions. Second operand has 21 states, 16 states have (on average 1.3125) internal successors, (21), 16 states have internal predecessors, (21), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-18 14:30:30,720 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:30:30,720 INFO L93 Difference]: Finished difference Result 230 states and 287 transitions. [2024-11-18 14:30:30,721 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-18 14:30:30,721 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 16 states have (on average 1.3125) internal successors, (21), 16 states have internal predecessors, (21), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 35 [2024-11-18 14:30:30,721 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:30:30,723 INFO L225 Difference]: With dead ends: 230 [2024-11-18 14:30:30,724 INFO L226 Difference]: Without dead ends: 228 [2024-11-18 14:30:30,725 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 15 SyntacticMatches, 1 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 249 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=165, Invalid=1241, Unknown=0, NotChecked=0, Total=1406 [2024-11-18 14:30:30,726 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 58 mSDsluCounter, 265 mSDsCounter, 0 mSdLazyCounter, 1061 mSolverCounterSat, 48 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 307 SdHoareTripleChecker+Invalid, 1113 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 1061 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-11-18 14:30:30,726 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 307 Invalid, 1113 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 1061 Invalid, 4 Unknown, 0 Unchecked, 1.5s Time] [2024-11-18 14:30:30,727 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 228 states. [2024-11-18 14:30:30,778 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 228 to 188. [2024-11-18 14:30:30,780 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 188 states, 115 states have (on average 1.1217391304347826) internal successors, (129), 119 states have internal predecessors, (129), 49 states have call successors, (49), 18 states have call predecessors, (49), 23 states have return successors, (60), 50 states have call predecessors, (60), 45 states have call successors, (60) [2024-11-18 14:30:30,781 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 188 states to 188 states and 238 transitions. [2024-11-18 14:30:30,781 INFO L78 Accepts]: Start accepts. Automaton has 188 states and 238 transitions. Word has length 35 [2024-11-18 14:30:30,783 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:30:30,783 INFO L471 AbstractCegarLoop]: Abstraction has 188 states and 238 transitions. [2024-11-18 14:30:30,783 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 16 states have (on average 1.3125) internal successors, (21), 16 states have internal predecessors, (21), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-18 14:30:30,784 INFO L276 IsEmpty]: Start isEmpty. Operand 188 states and 238 transitions. [2024-11-18 14:30:30,784 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-18 14:30:30,787 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:30:30,787 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:30:30,796 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-18 14:30:30,988 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:30:30,988 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:30:30,989 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:30:30,989 INFO L85 PathProgramCache]: Analyzing trace with hash 133435933, now seen corresponding path program 3 times [2024-11-18 14:30:30,989 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:30:30,989 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [47184927] [2024-11-18 14:30:30,989 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 14:30:30,989 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:30:31,073 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-18 14:30:31,073 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 14:30:31,075 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [812133156] [2024-11-18 14:30:31,075 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 14:30:31,075 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:30:31,075 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:30:31,077 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-11-18 14:30:31,079 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-11-18 14:30:31,281 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2024-11-18 14:30:31,281 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:30:31,283 INFO L255 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 59 conjuncts are in the unsatisfiable core [2024-11-18 14:30:31,286 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:30:31,296 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-11-18 14:30:31,317 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-11-18 14:30:31,324 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-11-18 14:30:31,542 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-11-18 14:30:31,546 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-11-18 14:30:31,548 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-11-18 14:30:31,578 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2024-11-18 14:30:31,578 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:30:31,783 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:30:31,783 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [47184927] [2024-11-18 14:30:31,784 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 14:30:31,784 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [812133156] [2024-11-18 14:30:31,784 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [812133156] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:30:31,784 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 14:30:31,784 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2024-11-18 14:30:31,784 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [60431744] [2024-11-18 14:30:31,784 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 14:30:31,784 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-18 14:30:31,785 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:30:31,785 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-18 14:30:31,785 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2024-11-18 14:30:31,785 INFO L87 Difference]: Start difference. First operand 188 states and 238 transitions. Second operand has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-18 14:30:32,188 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:30:32,188 INFO L93 Difference]: Finished difference Result 203 states and 256 transitions. [2024-11-18 14:30:32,188 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-18 14:30:32,189 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 41 [2024-11-18 14:30:32,189 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:30:32,190 INFO L225 Difference]: With dead ends: 203 [2024-11-18 14:30:32,190 INFO L226 Difference]: Without dead ends: 201 [2024-11-18 14:30:32,191 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 31 SyntacticMatches, 5 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=57, Invalid=215, Unknown=0, NotChecked=0, Total=272 [2024-11-18 14:30:32,191 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 41 mSDsluCounter, 197 mSDsCounter, 0 mSdLazyCounter, 261 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 230 SdHoareTripleChecker+Invalid, 291 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 261 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-18 14:30:32,191 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [45 Valid, 230 Invalid, 291 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 261 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-18 14:30:32,192 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 201 states. [2024-11-18 14:30:32,244 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 201 to 192. [2024-11-18 14:30:32,245 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 192 states, 118 states have (on average 1.11864406779661) internal successors, (132), 122 states have internal predecessors, (132), 49 states have call successors, (49), 19 states have call predecessors, (49), 24 states have return successors, (60), 50 states have call predecessors, (60), 45 states have call successors, (60) [2024-11-18 14:30:32,246 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 192 states to 192 states and 241 transitions. [2024-11-18 14:30:32,247 INFO L78 Accepts]: Start accepts. Automaton has 192 states and 241 transitions. Word has length 41 [2024-11-18 14:30:32,247 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:30:32,247 INFO L471 AbstractCegarLoop]: Abstraction has 192 states and 241 transitions. [2024-11-18 14:30:32,247 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-18 14:30:32,247 INFO L276 IsEmpty]: Start isEmpty. Operand 192 states and 241 transitions. [2024-11-18 14:30:32,248 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-18 14:30:32,248 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:30:32,248 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, 1, 1, 1] [2024-11-18 14:30:32,258 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-11-18 14:30:32,449 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:30:32,449 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:30:32,450 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:30:32,450 INFO L85 PathProgramCache]: Analyzing trace with hash -345050438, now seen corresponding path program 1 times [2024-11-18 14:30:32,450 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:30:32,450 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [805552503] [2024-11-18 14:30:32,450 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:30:32,450 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:30:32,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 14:30:32,475 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [760890998] [2024-11-18 14:30:32,475 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:30:32,476 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:30:32,476 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:30:32,478 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-11-18 14:30:32,479 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-11-18 14:30:32,657 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:30:32,659 INFO L255 TraceCheckSpWp]: Trace formula consists of 323 conjuncts, 87 conjuncts are in the unsatisfiable core [2024-11-18 14:30:32,662 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:30:32,665 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-11-18 14:30:32,667 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