./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_hard2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 798a7b37 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/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.6.800.v20240513-1750.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_hard2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 8571897e57404ad6e85df2c29745d5b56fa4d168673d3bc7c670c79b03a6c106 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 14:40:05,610 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 14:40:05,663 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-03 14:40:05,666 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 14:40:05,666 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 14:40:05,685 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 14:40:05,687 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 14:40:05,687 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 14:40:05,688 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 14:40:05,688 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 14:40:05,688 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 14:40:05,688 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 14:40:05,689 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 14:40:05,689 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 14:40:05,689 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 14:40:05,689 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 14:40:05,689 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 14:40:05,690 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 14:40:05,690 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 14:40:05,690 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 14:40:05,690 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 14:40:05,690 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 14:40:05,690 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 14:40:05,690 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 14:40:05,690 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 14:40:05,690 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 14:40:05,690 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 14:40:05,690 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 14:40:05,690 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 14:40:05,691 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 14:40:05,691 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 14:40:05,691 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 14:40:05,691 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:40:05,691 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 14:40:05,691 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 14:40:05,691 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 14:40:05,691 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 14:40:05,691 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 14:40:05,691 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 14:40:05,692 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 14:40:05,692 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 14:40:05,692 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 14:40:05,692 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 14:40:05,692 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 8571897e57404ad6e85df2c29745d5b56fa4d168673d3bc7c670c79b03a6c106 [2025-03-03 14:40:05,900 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 14:40:05,912 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 14:40:05,914 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 14:40:05,915 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 14:40:05,915 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 14:40:05,916 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_hard2.c [2025-03-03 14:40:07,119 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4c4b460ef/780034111b0f482aa1bf3211c5153e62/FLAGee6975240 [2025-03-03 14:40:07,300 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 14:40:07,301 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_hard2.c [2025-03-03 14:40:07,308 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4c4b460ef/780034111b0f482aa1bf3211c5153e62/FLAGee6975240 [2025-03-03 14:40:07,322 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4c4b460ef/780034111b0f482aa1bf3211c5153e62 [2025-03-03 14:40:07,324 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 14:40:07,326 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 14:40:07,339 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 14:40:07,339 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 14:40:07,349 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 14:40:07,350 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,351 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5274cb6c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07, skipping insertion in model container [2025-03-03 14:40:07,351 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,365 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 14:40:07,484 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_hard2.c[1067,1080] [2025-03-03 14:40:07,506 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:40:07,515 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 14:40:07,524 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_hard2.c[1067,1080] [2025-03-03 14:40:07,537 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:40:07,549 INFO L204 MainTranslator]: Completed translation [2025-03-03 14:40:07,550 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07 WrapperNode [2025-03-03 14:40:07,550 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 14:40:07,551 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 14:40:07,552 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 14:40:07,552 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 14:40:07,556 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,565 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,579 INFO L138 Inliner]: procedures = 17, calls = 90, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 78 [2025-03-03 14:40:07,580 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 14:40:07,580 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 14:40:07,580 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 14:40:07,580 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 14:40:07,586 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,586 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,588 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,601 INFO L175 MemorySlicer]: Split 56 memory accesses to 8 slices as follows [2, 8, 5, 6, 9, 6, 8, 12]. 21 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8, 0, 0, 0, 0, 0, 0]. The 12 writes are split as follows [0, 0, 1, 2, 3, 1, 2, 3]. [2025-03-03 14:40:07,604 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,604 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,610 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,611 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,612 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,613 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,614 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 14:40:07,615 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 14:40:07,615 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 14:40:07,615 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 14:40:07,616 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07" (1/1) ... [2025-03-03 14:40:07,621 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:40:07,630 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:40:07,641 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) [2025-03-03 14:40:07,646 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 [2025-03-03 14:40:07,662 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 14:40:07,662 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_40_to_50_0 [2025-03-03 14:40:07,662 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_40_to_50_0 [2025-03-03 14:40:07,663 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 14:40:07,663 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-03 14:40:07,663 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-03-03 14:40:07,663 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2025-03-03 14:40:07,663 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2025-03-03 14:40:07,663 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2025-03-03 14:40:07,663 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#6 [2025-03-03 14:40:07,663 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#7 [2025-03-03 14:40:07,663 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-03 14:40:07,663 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-03-03 14:40:07,663 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-03-03 14:40:07,664 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-03-03 14:40:07,664 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2025-03-03 14:40:07,664 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2025-03-03 14:40:07,664 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2025-03-03 14:40:07,664 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#6 [2025-03-03 14:40:07,664 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#7 [2025-03-03 14:40:07,664 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_30_to_37_0 [2025-03-03 14:40:07,664 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_30_to_37_0 [2025-03-03 14:40:07,664 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 14:40:07,664 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 14:40:07,664 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-03-03 14:40:07,665 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-03-03 14:40:07,665 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-03-03 14:40:07,665 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2025-03-03 14:40:07,665 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2025-03-03 14:40:07,665 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2025-03-03 14:40:07,665 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#6 [2025-03-03 14:40:07,665 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#7 [2025-03-03 14:40:07,665 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-03 14:40:07,666 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-03 14:40:07,666 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-03 14:40:07,744 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 14:40:07,746 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 14:40:07,909 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L110: call ULTIMATE.dealloc(main_~#A~0#1.base, main_~#A~0#1.offset);havoc main_~#A~0#1.base, main_~#A~0#1.offset;call ULTIMATE.dealloc(main_~#B~0#1.base, main_~#B~0#1.offset);havoc main_~#B~0#1.base, main_~#B~0#1.offset;call ULTIMATE.dealloc(main_~#r~0#1.base, main_~#r~0#1.offset);havoc main_~#r~0#1.base, main_~#r~0#1.offset;call ULTIMATE.dealloc(main_~#d~0#1.base, main_~#d~0#1.offset);havoc main_~#d~0#1.base, main_~#d~0#1.offset;call ULTIMATE.dealloc(main_~#p~0#1.base, main_~#p~0#1.offset);havoc main_~#p~0#1.base, main_~#p~0#1.offset;call ULTIMATE.dealloc(main_~#q~0#1.base, main_~#q~0#1.offset);havoc main_~#q~0#1.base, main_~#q~0#1.offset; [2025-03-03 14:40:07,936 INFO L? ?]: Removed 9 outVars from TransFormulas that were not future-live. [2025-03-03 14:40:07,936 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 14:40:07,947 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 14:40:07,947 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 14:40:07,948 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:40:07 BoogieIcfgContainer [2025-03-03 14:40:07,948 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 14:40:07,949 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 14:40:07,949 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 14:40:07,954 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 14:40:07,954 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 02:40:07" (1/3) ... [2025-03-03 14:40:07,955 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1902acd3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:40:07, skipping insertion in model container [2025-03-03 14:40:07,955 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:40:07" (2/3) ... [2025-03-03 14:40:07,955 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1902acd3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:40:07, skipping insertion in model container [2025-03-03 14:40:07,955 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:40:07" (3/3) ... [2025-03-03 14:40:07,956 INFO L128 eAbstractionObserver]: Analyzing ICFG recursified_hard2.c [2025-03-03 14:40:07,966 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 14:40:07,967 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG recursified_hard2.c that has 4 procedures, 41 locations, 1 initial locations, 0 loop locations, and 1 error locations. [2025-03-03 14:40:07,999 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 14:40:08,006 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;@1be8db7b, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 14:40:08,006 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-03 14:40:08,009 INFO L276 IsEmpty]: Start isEmpty. Operand has 41 states, 25 states have (on average 1.28) internal successors, (32), 28 states have internal predecessors, (32), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-03 14:40:08,012 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2025-03-03 14:40:08,012 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:40:08,013 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:40:08,013 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:40:08,016 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:40:08,016 INFO L85 PathProgramCache]: Analyzing trace with hash 1640937684, now seen corresponding path program 1 times [2025-03-03 14:40:08,020 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:40:08,021 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1169321251] [2025-03-03 14:40:08,021 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:08,021 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:40:08,092 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-03 14:40:08,123 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-03 14:40:08,123 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:08,123 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:40:08,463 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:40:08,464 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:40:08,464 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1169321251] [2025-03-03 14:40:08,465 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1169321251] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:40:08,465 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:40:08,465 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-03-03 14:40:08,466 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [187027486] [2025-03-03 14:40:08,466 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:40:08,469 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-03 14:40:08,469 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:40:08,482 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-03 14:40:08,483 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2025-03-03 14:40:08,485 INFO L87 Difference]: Start difference. First operand has 41 states, 25 states have (on average 1.28) internal successors, (32), 28 states have internal predecessors, (32), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 14:40:08,633 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:40:08,633 INFO L93 Difference]: Finished difference Result 83 states and 119 transitions. [2025-03-03 14:40:08,634 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-03 14:40:08,635 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2025-03-03 14:40:08,635 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:40:08,639 INFO L225 Difference]: With dead ends: 83 [2025-03-03 14:40:08,639 INFO L226 Difference]: Without dead ends: 41 [2025-03-03 14:40:08,641 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2025-03-03 14:40:08,642 INFO L435 NwaCegarLoop]: 44 mSDtfsCounter, 18 mSDsluCounter, 202 mSDsCounter, 0 mSdLazyCounter, 80 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 246 SdHoareTripleChecker+Invalid, 90 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 80 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:40:08,643 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 246 Invalid, 90 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 80 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:40:08,651 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2025-03-03 14:40:08,662 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2025-03-03 14:40:08,662 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 25 states have (on average 1.16) internal successors, (29), 28 states have internal predecessors, (29), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-03 14:40:08,665 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 50 transitions. [2025-03-03 14:40:08,667 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 50 transitions. Word has length 9 [2025-03-03 14:40:08,668 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:40:08,668 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 50 transitions. [2025-03-03 14:40:08,668 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 14:40:08,669 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 50 transitions. [2025-03-03 14:40:08,669 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2025-03-03 14:40:08,669 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:40:08,670 INFO L218 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:40:08,670 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-03 14:40:08,670 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:40:08,671 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:40:08,671 INFO L85 PathProgramCache]: Analyzing trace with hash 1061295684, now seen corresponding path program 1 times [2025-03-03 14:40:08,671 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:40:08,671 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1873772324] [2025-03-03 14:40:08,671 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:08,671 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:40:08,685 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 15 statements into 1 equivalence classes. [2025-03-03 14:40:08,691 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 15 of 15 statements. [2025-03-03 14:40:08,691 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:08,692 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:40:08,898 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:40:08,898 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:40:08,899 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1873772324] [2025-03-03 14:40:08,899 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1873772324] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:40:08,899 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:40:08,899 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2025-03-03 14:40:08,899 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1437790222] [2025-03-03 14:40:08,899 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:40:08,900 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-03 14:40:08,900 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:40:08,901 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-03 14:40:08,901 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2025-03-03 14:40:08,902 INFO L87 Difference]: Start difference. First operand 41 states and 50 transitions. Second operand has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (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) [2025-03-03 14:40:09,014 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:40:09,014 INFO L93 Difference]: Finished difference Result 47 states and 55 transitions. [2025-03-03 14:40:09,014 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-03 14:40:09,015 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (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 15 [2025-03-03 14:40:09,015 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:40:09,019 INFO L225 Difference]: With dead ends: 47 [2025-03-03 14:40:09,019 INFO L226 Difference]: Without dead ends: 45 [2025-03-03 14:40:09,019 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2025-03-03 14:40:09,020 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 17 mSDsluCounter, 184 mSDsCounter, 0 mSdLazyCounter, 89 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 226 SdHoareTripleChecker+Invalid, 98 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 89 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:40:09,020 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 226 Invalid, 98 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 89 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:40:09,020 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2025-03-03 14:40:09,025 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2025-03-03 14:40:09,025 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 28 states have (on average 1.1428571428571428) internal successors, (32), 31 states have internal predecessors, (32), 11 states have call successors, (11), 5 states have call predecessors, (11), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-03 14:40:09,026 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 53 transitions. [2025-03-03 14:40:09,029 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 53 transitions. Word has length 15 [2025-03-03 14:40:09,030 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:40:09,030 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 53 transitions. [2025-03-03 14:40:09,030 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (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) [2025-03-03 14:40:09,030 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 53 transitions. [2025-03-03 14:40:09,030 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2025-03-03 14:40:09,030 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:40:09,030 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:40:09,030 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-03 14:40:09,031 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:40:09,031 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:40:09,031 INFO L85 PathProgramCache]: Analyzing trace with hash -1087449418, now seen corresponding path program 1 times [2025-03-03 14:40:09,031 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:40:09,031 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [425865352] [2025-03-03 14:40:09,031 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:09,031 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:40:09,041 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-03 14:40:09,054 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-03 14:40:09,057 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:09,057 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:40:09,059 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [902426656] [2025-03-03 14:40:09,059 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:09,059 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:40:09,059 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:40:09,061 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) [2025-03-03 14:40:09,062 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-03 14:40:09,113 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-03 14:40:09,140 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-03 14:40:09,140 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:09,140 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:40:09,145 INFO L256 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 45 conjuncts are in the unsatisfiable core [2025-03-03 14:40:09,149 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:40:09,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 15 treesize of output 11 [2025-03-03 14:40:09,184 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 [2025-03-03 14:40:09,189 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 [2025-03-03 14:40:09,491 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-03 14:40:09,491 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:40:09,604 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-03 14:40:09,604 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:40:09,604 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [425865352] [2025-03-03 14:40:09,605 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:40:09,605 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [902426656] [2025-03-03 14:40:09,605 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [902426656] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-03 14:40:09,605 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:40:09,605 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 13 [2025-03-03 14:40:09,605 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [966085814] [2025-03-03 14:40:09,605 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:40:09,605 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-03 14:40:09,605 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:40:09,606 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-03 14:40:09,606 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2025-03-03 14:40:09,606 INFO L87 Difference]: Start difference. First operand 45 states and 53 transitions. Second operand has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-03 14:40:09,764 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:40:09,764 INFO L93 Difference]: Finished difference Result 56 states and 66 transitions. [2025-03-03 14:40:09,765 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-03 14:40:09,765 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2025-03-03 14:40:09,765 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:40:09,767 INFO L225 Difference]: With dead ends: 56 [2025-03-03 14:40:09,767 INFO L226 Difference]: Without dead ends: 54 [2025-03-03 14:40:09,767 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 24 SyntacticMatches, 5 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=44, Invalid=196, Unknown=0, NotChecked=0, Total=240 [2025-03-03 14:40:09,767 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 15 mSDsluCounter, 177 mSDsCounter, 0 mSdLazyCounter, 103 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 218 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 103 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:40:09,768 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 218 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 103 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:40:09,768 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2025-03-03 14:40:09,775 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 49. [2025-03-03 14:40:09,775 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 34 states have internal predecessors, (35), 11 states have call successors, (11), 6 states have call predecessors, (11), 6 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-03 14:40:09,775 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 56 transitions. [2025-03-03 14:40:09,775 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 56 transitions. Word has length 21 [2025-03-03 14:40:09,776 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:40:09,776 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 56 transitions. [2025-03-03 14:40:09,776 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2025-03-03 14:40:09,776 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 56 transitions. [2025-03-03 14:40:09,776 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2025-03-03 14:40:09,776 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:40:09,776 INFO L218 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] [2025-03-03 14:40:09,783 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-03-03 14:40:09,978 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 [2025-03-03 14:40:09,979 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:40:09,979 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:40:09,979 INFO L85 PathProgramCache]: Analyzing trace with hash -635210381, now seen corresponding path program 1 times [2025-03-03 14:40:09,979 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:40:09,979 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1813177907] [2025-03-03 14:40:09,979 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:09,979 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:40:09,990 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-03 14:40:10,005 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-03 14:40:10,005 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:10,005 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:40:10,006 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [596715364] [2025-03-03 14:40:10,006 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:10,006 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:40:10,006 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:40:10,008 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) [2025-03-03 14:40:10,009 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-03 14:40:10,074 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-03 14:40:10,109 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-03 14:40:10,109 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:10,109 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:40:10,111 INFO L256 TraceCheckSpWp]: Trace formula consists of 296 conjuncts, 57 conjuncts are in the unsatisfiable core [2025-03-03 14:40:10,114 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:40:10,125 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 [2025-03-03 14:40:10,129 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 [2025-03-03 14:40:10,134 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 [2025-03-03 14:40:10,330 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 [2025-03-03 14:40:10,332 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 [2025-03-03 14:40:10,356 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 14:40:10,357 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:40:10,445 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 14:40:10,445 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:40:10,445 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1813177907] [2025-03-03 14:40:10,445 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:40:10,445 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [596715364] [2025-03-03 14:40:10,445 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [596715364] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-03 14:40:10,445 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:40:10,445 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 9 [2025-03-03 14:40:10,445 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2031105672] [2025-03-03 14:40:10,445 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:40:10,445 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-03 14:40:10,445 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:40:10,446 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-03 14:40:10,446 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2025-03-03 14:40:10,446 INFO L87 Difference]: Start difference. First operand 49 states and 56 transitions. Second operand has 8 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 14:40:10,571 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:40:10,571 INFO L93 Difference]: Finished difference Result 69 states and 82 transitions. [2025-03-03 14:40:10,571 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-03 14:40:10,571 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 33 [2025-03-03 14:40:10,572 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:40:10,573 INFO L225 Difference]: With dead ends: 69 [2025-03-03 14:40:10,573 INFO L226 Difference]: Without dead ends: 67 [2025-03-03 14:40:10,573 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 53 SyntacticMatches, 4 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2025-03-03 14:40:10,573 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 19 mSDsluCounter, 208 mSDsCounter, 0 mSdLazyCounter, 107 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 250 SdHoareTripleChecker+Invalid, 115 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 107 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:40:10,573 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 250 Invalid, 115 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 107 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:40:10,574 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2025-03-03 14:40:10,580 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 66. [2025-03-03 14:40:10,580 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 42 states have (on average 1.1428571428571428) internal successors, (48), 46 states have internal predecessors, (48), 14 states have call successors, (14), 8 states have call predecessors, (14), 9 states have return successors, (17), 13 states have call predecessors, (17), 13 states have call successors, (17) [2025-03-03 14:40:10,581 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 79 transitions. [2025-03-03 14:40:10,581 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 79 transitions. Word has length 33 [2025-03-03 14:40:10,581 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:40:10,582 INFO L471 AbstractCegarLoop]: Abstraction has 66 states and 79 transitions. [2025-03-03 14:40:10,582 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 14:40:10,582 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 79 transitions. [2025-03-03 14:40:10,582 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2025-03-03 14:40:10,582 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:40:10,582 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:40:10,590 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-03 14:40:10,783 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 [2025-03-03 14:40:10,783 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:40:10,783 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:40:10,783 INFO L85 PathProgramCache]: Analyzing trace with hash 144365348, now seen corresponding path program 1 times [2025-03-03 14:40:10,783 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:40:10,783 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [217831896] [2025-03-03 14:40:10,783 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:10,784 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:40:10,792 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 39 statements into 1 equivalence classes. [2025-03-03 14:40:10,810 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 39 of 39 statements. [2025-03-03 14:40:10,810 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:10,810 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:40:10,811 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1441939025] [2025-03-03 14:40:10,811 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:10,811 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:40:10,811 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:40:10,813 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) [2025-03-03 14:40:10,815 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-03 14:40:10,872 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 39 statements into 1 equivalence classes. [2025-03-03 14:40:10,905 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 39 of 39 statements. [2025-03-03 14:40:10,905 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:10,906 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:40:10,908 INFO L256 TraceCheckSpWp]: Trace formula consists of 311 conjuncts, 57 conjuncts are in the unsatisfiable core [2025-03-03 14:40:10,910 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:40:10,917 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 [2025-03-03 14:40:10,922 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 [2025-03-03 14:40:10,927 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 [2025-03-03 14:40:11,187 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 14:40:11,188 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:40:15,465 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:40:15,465 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [217831896] [2025-03-03 14:40:15,465 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:40:15,465 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1441939025] [2025-03-03 14:40:15,465 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1441939025] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:40:15,465 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:40:15,466 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2025-03-03 14:40:15,466 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [43385465] [2025-03-03 14:40:15,466 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:40:15,466 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-03 14:40:15,466 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:40:15,466 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-03 14:40:15,467 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=197, Unknown=1, NotChecked=0, Total=240 [2025-03-03 14:40:15,467 INFO L87 Difference]: Start difference. First operand 66 states and 79 transitions. Second operand has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 4 states have call successors, (7), 5 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-03 14:40:15,895 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:40:15,895 INFO L93 Difference]: Finished difference Result 123 states and 140 transitions. [2025-03-03 14:40:15,896 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-03 14:40:15,896 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 4 states have call successors, (7), 5 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 39 [2025-03-03 14:40:15,896 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:40:15,897 INFO L225 Difference]: With dead ends: 123 [2025-03-03 14:40:15,897 INFO L226 Difference]: Without dead ends: 121 [2025-03-03 14:40:15,897 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 39 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=102, Invalid=359, Unknown=1, NotChecked=0, Total=462 [2025-03-03 14:40:15,898 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 78 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 263 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 85 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 304 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 263 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-03 14:40:15,898 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [85 Valid, 125 Invalid, 304 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 263 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-03 14:40:15,898 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2025-03-03 14:40:15,912 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 119. [2025-03-03 14:40:15,912 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 119 states, 77 states have (on average 1.1168831168831168) internal successors, (86), 81 states have internal predecessors, (86), 22 states have call successors, (22), 16 states have call predecessors, (22), 19 states have return successors, (29), 21 states have call predecessors, (29), 20 states have call successors, (29) [2025-03-03 14:40:15,913 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 137 transitions. [2025-03-03 14:40:15,913 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 137 transitions. Word has length 39 [2025-03-03 14:40:15,913 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:40:15,913 INFO L471 AbstractCegarLoop]: Abstraction has 119 states and 137 transitions. [2025-03-03 14:40:15,914 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 4 states have call successors, (7), 5 states have call predecessors, (7), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-03 14:40:15,914 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 137 transitions. [2025-03-03 14:40:15,914 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2025-03-03 14:40:15,915 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:40:15,915 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:40:15,921 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-03 14:40:16,115 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 [2025-03-03 14:40:16,115 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:40:16,116 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:40:16,116 INFO L85 PathProgramCache]: Analyzing trace with hash -1799433998, now seen corresponding path program 1 times [2025-03-03 14:40:16,116 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:40:16,116 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [761748773] [2025-03-03 14:40:16,116 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:16,116 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:40:16,124 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-03-03 14:40:16,142 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-03-03 14:40:16,142 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:16,142 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:40:16,143 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1716513148] [2025-03-03 14:40:16,143 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:16,143 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:40:16,143 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:40:16,146 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) [2025-03-03 14:40:16,147 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-03 14:40:16,203 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-03-03 14:40:16,234 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-03-03 14:40:16,234 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:16,234 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:40:16,236 INFO L256 TraceCheckSpWp]: Trace formula consists of 334 conjuncts, 29 conjuncts are in the unsatisfiable core [2025-03-03 14:40:16,239 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:40:16,244 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 [2025-03-03 14:40:16,247 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 [2025-03-03 14:40:16,251 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 [2025-03-03 14:40:16,409 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-03 14:40:16,465 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 [2025-03-03 14:40:16,467 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 [2025-03-03 14:40:16,496 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 4 proven. 30 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-03-03 14:40:16,496 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:40:20,686 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:40:20,686 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [761748773] [2025-03-03 14:40:20,686 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:40:20,686 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1716513148] [2025-03-03 14:40:20,686 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1716513148] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:40:20,686 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:40:20,686 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2025-03-03 14:40:20,687 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [736243406] [2025-03-03 14:40:20,687 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:40:20,688 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-03 14:40:20,688 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:40:20,689 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-03 14:40:20,689 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=105, Unknown=1, NotChecked=0, Total=132 [2025-03-03 14:40:20,689 INFO L87 Difference]: Start difference. First operand 119 states and 137 transitions. Second operand has 9 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-03-03 14:40:21,015 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:40:21,015 INFO L93 Difference]: Finished difference Result 137 states and 156 transitions. [2025-03-03 14:40:21,016 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-03 14:40:21,016 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 49 [2025-03-03 14:40:21,016 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:40:21,017 INFO L225 Difference]: With dead ends: 137 [2025-03-03 14:40:21,017 INFO L226 Difference]: Without dead ends: 133 [2025-03-03 14:40:21,017 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 48 SyntacticMatches, 3 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=55, Invalid=184, Unknown=1, NotChecked=0, Total=240 [2025-03-03 14:40:21,018 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 56 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 229 mSolverCounterSat, 43 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 273 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 229 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 14:40:21,018 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [58 Valid, 83 Invalid, 273 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 229 Invalid, 1 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 14:40:21,018 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 133 states. [2025-03-03 14:40:21,041 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 133 to 129. [2025-03-03 14:40:21,043 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 129 states, 84 states have (on average 1.1071428571428572) internal successors, (93), 87 states have internal predecessors, (93), 24 states have call successors, (24), 18 states have call predecessors, (24), 20 states have return successors, (30), 23 states have call predecessors, (30), 21 states have call successors, (30) [2025-03-03 14:40:21,045 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 147 transitions. [2025-03-03 14:40:21,046 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 147 transitions. Word has length 49 [2025-03-03 14:40:21,046 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:40:21,047 INFO L471 AbstractCegarLoop]: Abstraction has 129 states and 147 transitions. [2025-03-03 14:40:21,047 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-03-03 14:40:21,047 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 147 transitions. [2025-03-03 14:40:21,048 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2025-03-03 14:40:21,048 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:40:21,048 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:40:21,056 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-03 14:40:21,249 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 [2025-03-03 14:40:21,249 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:40:21,249 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:40:21,249 INFO L85 PathProgramCache]: Analyzing trace with hash -869008365, now seen corresponding path program 1 times [2025-03-03 14:40:21,250 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:40:21,250 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1676826995] [2025-03-03 14:40:21,250 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:21,250 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:40:21,259 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 50 statements into 1 equivalence classes. [2025-03-03 14:40:21,265 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 50 of 50 statements. [2025-03-03 14:40:21,266 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:21,266 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:40:21,439 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2025-03-03 14:40:21,439 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:40:21,439 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1676826995] [2025-03-03 14:40:21,439 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1676826995] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:40:21,439 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:40:21,439 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-03 14:40:21,440 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1045171376] [2025-03-03 14:40:21,440 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:40:21,440 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-03 14:40:21,440 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:40:21,440 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-03 14:40:21,440 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2025-03-03 14:40:21,441 INFO L87 Difference]: Start difference. First operand 129 states and 147 transitions. Second operand has 7 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2025-03-03 14:40:21,580 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:40:21,580 INFO L93 Difference]: Finished difference Result 177 states and 204 transitions. [2025-03-03 14:40:21,581 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-03 14:40:21,581 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 50 [2025-03-03 14:40:21,581 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:40:21,582 INFO L225 Difference]: With dead ends: 177 [2025-03-03 14:40:21,582 INFO L226 Difference]: Without dead ends: 129 [2025-03-03 14:40:21,583 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2025-03-03 14:40:21,583 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 28 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 146 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 166 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 146 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:40:21,583 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 103 Invalid, 166 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 146 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:40:21,584 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2025-03-03 14:40:21,602 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 127. [2025-03-03 14:40:21,602 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 83 states have (on average 1.0963855421686748) internal successors, (91), 86 states have internal predecessors, (91), 24 states have call successors, (24), 18 states have call predecessors, (24), 19 states have return successors, (26), 23 states have call predecessors, (26), 21 states have call successors, (26) [2025-03-03 14:40:21,603 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 141 transitions. [2025-03-03 14:40:21,603 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 141 transitions. Word has length 50 [2025-03-03 14:40:21,603 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:40:21,603 INFO L471 AbstractCegarLoop]: Abstraction has 127 states and 141 transitions. [2025-03-03 14:40:21,604 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2025-03-03 14:40:21,604 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 141 transitions. [2025-03-03 14:40:21,604 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-03 14:40:21,605 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:40:21,605 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:40:21,605 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2025-03-03 14:40:21,605 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:40:21,605 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:40:21,605 INFO L85 PathProgramCache]: Analyzing trace with hash 1311463013, now seen corresponding path program 1 times [2025-03-03 14:40:21,605 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:40:21,605 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1702946617] [2025-03-03 14:40:21,605 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:21,605 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:40:21,624 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-03 14:40:21,632 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-03 14:40:21,633 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:21,633 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:40:21,807 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2025-03-03 14:40:21,808 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:40:21,808 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1702946617] [2025-03-03 14:40:21,808 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1702946617] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:40:21,808 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:40:21,808 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-03 14:40:21,808 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1239635990] [2025-03-03 14:40:21,808 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:40:21,808 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-03 14:40:21,809 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:40:21,809 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-03 14:40:21,809 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2025-03-03 14:40:21,809 INFO L87 Difference]: Start difference. First operand 127 states and 141 transitions. Second operand has 7 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-03 14:40:21,938 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:40:21,938 INFO L93 Difference]: Finished difference Result 131 states and 145 transitions. [2025-03-03 14:40:21,938 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-03 14:40:21,938 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 55 [2025-03-03 14:40:21,939 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:40:21,940 INFO L225 Difference]: With dead ends: 131 [2025-03-03 14:40:21,940 INFO L226 Difference]: Without dead ends: 99 [2025-03-03 14:40:21,940 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2025-03-03 14:40:21,940 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 6 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 134 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 146 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 134 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:40:21,941 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 118 Invalid, 146 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 134 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:40:21,941 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2025-03-03 14:40:21,951 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 97. [2025-03-03 14:40:21,951 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 63 states have (on average 1.1111111111111112) internal successors, (70), 66 states have internal predecessors, (70), 19 states have call successors, (19), 13 states have call predecessors, (19), 14 states have return successors, (21), 18 states have call predecessors, (21), 17 states have call successors, (21) [2025-03-03 14:40:21,952 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 110 transitions. [2025-03-03 14:40:21,952 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 110 transitions. Word has length 55 [2025-03-03 14:40:21,952 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:40:21,952 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 110 transitions. [2025-03-03 14:40:21,952 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 3 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-03 14:40:21,952 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 110 transitions. [2025-03-03 14:40:21,953 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2025-03-03 14:40:21,953 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:40:21,953 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:40:21,953 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2025-03-03 14:40:21,953 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:40:21,953 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:40:21,953 INFO L85 PathProgramCache]: Analyzing trace with hash -968594917, now seen corresponding path program 1 times [2025-03-03 14:40:21,954 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:40:21,954 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1374560031] [2025-03-03 14:40:21,954 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:21,954 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:40:21,977 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 63 statements into 1 equivalence classes. [2025-03-03 14:40:21,994 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 63 of 63 statements. [2025-03-03 14:40:21,994 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:21,994 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:40:21,995 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [993129851] [2025-03-03 14:40:21,995 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:40:21,995 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:40:21,996 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:40:21,997 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) [2025-03-03 14:40:21,999 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-03 14:40:22,054 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 63 statements into 1 equivalence classes. [2025-03-03 14:40:22,096 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 63 of 63 statements. [2025-03-03 14:40:22,096 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:40:22,096 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:40:22,098 INFO L256 TraceCheckSpWp]: Trace formula consists of 417 conjuncts, 85 conjuncts are in the unsatisfiable core [2025-03-03 14:40:22,101 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:40:22,106 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 [2025-03-03 14:40:22,109 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 [2025-03-03 14:40:22,113 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 [2025-03-03 14:40:22,395 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 [2025-03-03 14:40:22,402 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 [2025-03-03 14:40:22,605 INFO L134 CoverageAnalysis]: Checked inductivity of 109 backedges. 24 proven. 24 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2025-03-03 14:40:22,605 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:40:22,899 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:40:22,899 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1374560031] [2025-03-03 14:40:22,899 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:40:22,899 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [993129851] [2025-03-03 14:40:22,899 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [993129851] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:40:22,899 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:40:22,899 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2025-03-03 14:40:22,899 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1885744668] [2025-03-03 14:40:22,899 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:40:22,900 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-03 14:40:22,900 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:40:22,900 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-03 14:40:22,900 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=320, Unknown=0, NotChecked=0, Total=380 [2025-03-03 14:40:22,901 INFO L87 Difference]: Start difference. First operand 97 states and 110 transitions. Second operand has 15 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 12 states have internal predecessors, (28), 7 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2025-03-03 14:40:23,462 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:40:23,463 INFO L93 Difference]: Finished difference Result 131 states and 149 transitions. [2025-03-03 14:40:23,463 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-03 14:40:23,463 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 12 states have internal predecessors, (28), 7 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) Word has length 63 [2025-03-03 14:40:23,463 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:40:23,464 INFO L225 Difference]: With dead ends: 131 [2025-03-03 14:40:23,464 INFO L226 Difference]: Without dead ends: 129 [2025-03-03 14:40:23,465 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 58 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 143 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=120, Invalid=530, Unknown=0, NotChecked=0, Total=650 [2025-03-03 14:40:23,465 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 51 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 407 mSolverCounterSat, 27 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 137 SdHoareTripleChecker+Invalid, 435 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 407 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-03 14:40:23,465 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 137 Invalid, 435 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 407 Invalid, 1 Unknown, 0 Unchecked, 0.4s Time] [2025-03-03 14:40:23,465 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2025-03-03 14:40:23,478 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 127. [2025-03-03 14:40:23,479 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 82 states have (on average 1.1097560975609757) internal successors, (91), 85 states have internal predecessors, (91), 24 states have call successors, (24), 17 states have call predecessors, (24), 20 states have return successors, (31), 24 states have call predecessors, (31), 21 states have call successors, (31) [2025-03-03 14:40:23,479 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 146 transitions. [2025-03-03 14:40:23,480 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 146 transitions. Word has length 63 [2025-03-03 14:40:23,480 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:40:23,480 INFO L471 AbstractCegarLoop]: Abstraction has 127 states and 146 transitions. [2025-03-03 14:40:23,480 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 12 states have internal predecessors, (28), 7 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2025-03-03 14:40:23,480 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 146 transitions. [2025-03-03 14:40:23,481 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2025-03-03 14:40:23,481 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:40:23,481 INFO L218 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:40:23,487 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-03 14:40:23,681 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:40:23,682 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:40:23,682 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:40:23,682 INFO L85 PathProgramCache]: Analyzing trace with hash -1368586926, now seen corresponding path program 2 times [2025-03-03 14:40:23,682 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:40:23,682 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1873846931] [2025-03-03 14:40:23,682 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:40:23,682 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:40:23,691 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 87 statements into 2 equivalence classes. [2025-03-03 14:40:23,708 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 87 of 87 statements. [2025-03-03 14:40:23,709 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:40:23,709 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:40:23,710 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [160414835] [2025-03-03 14:40:23,710 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:40:23,710 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:40:23,710 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:40:23,716 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) [2025-03-03 14:40:23,716 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-03 14:40:23,783 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 87 statements into 2 equivalence classes. [2025-03-03 14:40:23,835 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 87 of 87 statements. [2025-03-03 14:40:23,835 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:40:23,835 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:40:23,852 INFO L256 TraceCheckSpWp]: Trace formula consists of 523 conjuncts, 149 conjuncts are in the unsatisfiable core [2025-03-03 14:40:23,860 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:40:23,868 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 [2025-03-03 14:40:23,872 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 [2025-03-03 14:40:23,878 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 [2025-03-03 14:40:23,891 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 [2025-03-03 14:40:23,898 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 [2025-03-03 14:40:24,690 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 [2025-03-03 14:40:24,695 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 [2025-03-03 14:40:44,947 INFO L134 CoverageAnalysis]: Checked inductivity of 234 backedges. 3 proven. 75 refuted. 33 times theorem prover too weak. 123 trivial. 0 not checked. [2025-03-03 14:40:44,947 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:40:45,759 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:40:45,759 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1873846931] [2025-03-03 14:40:45,759 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:40:45,759 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [160414835] [2025-03-03 14:40:45,759 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [160414835] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:40:45,759 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:40:45,759 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2025-03-03 14:40:45,759 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [823791844] [2025-03-03 14:40:45,759 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:40:45,760 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-03 14:40:45,760 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:40:45,760 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-03 14:40:45,761 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=771, Unknown=4, NotChecked=0, Total=870 [2025-03-03 14:40:45,761 INFO L87 Difference]: Start difference. First operand 127 states and 146 transitions. Second operand has 21 states, 16 states have (on average 2.375) internal successors, (38), 18 states have internal predecessors, (38), 11 states have call successors, (15), 5 states have call predecessors, (15), 6 states have return successors, (13), 8 states have call predecessors, (13), 9 states have call successors, (13) [2025-03-03 14:41:11,085 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-03 14:41:11,086 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:41:11,086 INFO L93 Difference]: Finished difference Result 161 states and 183 transitions. [2025-03-03 14:41:11,088 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-03-03 14:41:11,088 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 16 states have (on average 2.375) internal successors, (38), 18 states have internal predecessors, (38), 11 states have call successors, (15), 5 states have call predecessors, (15), 6 states have return successors, (13), 8 states have call predecessors, (13), 9 states have call successors, (13) Word has length 87 [2025-03-03 14:41:11,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:41:11,089 INFO L225 Difference]: With dead ends: 161 [2025-03-03 14:41:11,089 INFO L226 Difference]: Without dead ends: 159 [2025-03-03 14:41:11,090 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 72 SyntacticMatches, 3 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 373 ImplicationChecksByTransitivity, 41.1s TimeCoverageRelationStatistics Valid=237, Invalid=1734, Unknown=9, NotChecked=0, Total=1980 [2025-03-03 14:41:11,090 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 50 mSDsluCounter, 249 mSDsCounter, 0 mSdLazyCounter, 860 mSolverCounterSat, 30 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 283 SdHoareTripleChecker+Invalid, 893 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 860 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.8s IncrementalHoareTripleChecker+Time [2025-03-03 14:41:11,090 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 283 Invalid, 893 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 860 Invalid, 3 Unknown, 0 Unchecked, 4.8s Time] [2025-03-03 14:41:11,091 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 159 states. [2025-03-03 14:41:11,109 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 159 to 129. [2025-03-03 14:41:11,109 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 129 states, 83 states have (on average 1.108433734939759) internal successors, (92), 86 states have internal predecessors, (92), 24 states have call successors, (24), 17 states have call predecessors, (24), 21 states have return successors, (33), 25 states have call predecessors, (33), 21 states have call successors, (33) [2025-03-03 14:41:11,110 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 149 transitions. [2025-03-03 14:41:11,110 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 149 transitions. Word has length 87 [2025-03-03 14:41:11,110 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:41:11,110 INFO L471 AbstractCegarLoop]: Abstraction has 129 states and 149 transitions. [2025-03-03 14:41:11,110 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 16 states have (on average 2.375) internal successors, (38), 18 states have internal predecessors, (38), 11 states have call successors, (15), 5 states have call predecessors, (15), 6 states have return successors, (13), 8 states have call predecessors, (13), 9 states have call successors, (13) [2025-03-03 14:41:11,110 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 149 transitions. [2025-03-03 14:41:11,111 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2025-03-03 14:41:11,111 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:41:11,111 INFO L218 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:41:11,119 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-03-03 14:41:11,311 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:41:11,312 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:41:11,312 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:41:11,312 INFO L85 PathProgramCache]: Analyzing trace with hash -1361733431, now seen corresponding path program 3 times [2025-03-03 14:41:11,312 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:41:11,312 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [760861487] [2025-03-03 14:41:11,312 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:41:11,312 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:41:11,325 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 111 statements into 6 equivalence classes. [2025-03-03 14:41:11,394 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 111 of 111 statements. [2025-03-03 14:41:11,394 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-03 14:41:11,394 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:41:11,397 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2101704479] [2025-03-03 14:41:11,397 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:41:11,397 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:41:11,398 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:41:11,399 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) [2025-03-03 14:41:11,401 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-03 14:41:11,477 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 111 statements into 6 equivalence classes. [2025-03-03 14:41:11,629 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 83 of 111 statements. [2025-03-03 14:41:11,629 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-03 14:41:11,629 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:41:11,633 INFO L256 TraceCheckSpWp]: Trace formula consists of 571 conjuncts, 178 conjuncts are in the unsatisfiable core [2025-03-03 14:41:11,638 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:41:11,646 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 [2025-03-03 14:41:11,649 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 [2025-03-03 14:41:11,656 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 [2025-03-03 14:41:11,660 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 [2025-03-03 14:41:12,573 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 [2025-03-03 14:41:12,581 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 [2025-03-03 14:41:12,799 INFO L134 CoverageAnalysis]: Checked inductivity of 407 backedges. 0 proven. 112 refuted. 0 times theorem prover too weak. 295 trivial. 0 not checked. [2025-03-03 14:41:12,799 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:41:13,910 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:41:13,910 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [760861487] [2025-03-03 14:41:13,910 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:41:13,910 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2101704479] [2025-03-03 14:41:13,910 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2101704479] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:41:13,910 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:41:13,910 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2025-03-03 14:41:13,911 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [84849727] [2025-03-03 14:41:13,911 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:41:13,911 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-03 14:41:13,911 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:41:13,911 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-03 14:41:13,911 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=616, Unknown=0, NotChecked=0, Total=702 [2025-03-03 14:41:13,912 INFO L87 Difference]: Start difference. First operand 129 states and 149 transitions. Second operand has 19 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 16 states have internal predecessors, (31), 8 states have call successors, (12), 5 states have call predecessors, (12), 6 states have return successors, (11), 7 states have call predecessors, (11), 6 states have call successors, (11) [2025-03-03 14:41:15,074 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:41:15,075 INFO L93 Difference]: Finished difference Result 163 states and 186 transitions. [2025-03-03 14:41:15,075 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-03-03 14:41:15,075 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 16 states have internal predecessors, (31), 8 states have call successors, (12), 5 states have call predecessors, (12), 6 states have return successors, (11), 7 states have call predecessors, (11), 6 states have call successors, (11) Word has length 111 [2025-03-03 14:41:15,075 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:41:15,076 INFO L225 Difference]: With dead ends: 163 [2025-03-03 14:41:15,076 INFO L226 Difference]: Without dead ends: 161 [2025-03-03 14:41:15,077 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 101 SyntacticMatches, 1 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 270 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=166, Invalid=1024, Unknown=0, NotChecked=0, Total=1190 [2025-03-03 14:41:15,077 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 59 mSDsluCounter, 232 mSDsCounter, 0 mSdLazyCounter, 831 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 268 SdHoareTripleChecker+Invalid, 861 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 831 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2025-03-03 14:41:15,077 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 268 Invalid, 861 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 831 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2025-03-03 14:41:15,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2025-03-03 14:41:15,094 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 131. [2025-03-03 14:41:15,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 84 states have (on average 1.1071428571428572) internal successors, (93), 87 states have internal predecessors, (93), 24 states have call successors, (24), 17 states have call predecessors, (24), 22 states have return successors, (35), 26 states have call predecessors, (35), 21 states have call successors, (35) [2025-03-03 14:41:15,094 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 152 transitions. [2025-03-03 14:41:15,095 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 152 transitions. Word has length 111 [2025-03-03 14:41:15,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:41:15,095 INFO L471 AbstractCegarLoop]: Abstraction has 131 states and 152 transitions. [2025-03-03 14:41:15,095 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 16 states have internal predecessors, (31), 8 states have call successors, (12), 5 states have call predecessors, (12), 6 states have return successors, (11), 7 states have call predecessors, (11), 6 states have call successors, (11) [2025-03-03 14:41:15,095 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 152 transitions. [2025-03-03 14:41:15,096 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2025-03-03 14:41:15,096 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:41:15,096 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:41:15,103 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2025-03-03 14:41:15,296 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:41:15,296 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:41:15,297 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:41:15,297 INFO L85 PathProgramCache]: Analyzing trace with hash -1027402624, now seen corresponding path program 4 times [2025-03-03 14:41:15,297 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:41:15,297 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [30680904] [2025-03-03 14:41:15,297 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-03 14:41:15,297 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:41:15,314 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 135 statements into 2 equivalence classes. [2025-03-03 14:41:15,346 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 135 of 135 statements. [2025-03-03 14:41:15,346 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-03 14:41:15,346 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:41:15,347 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1167021575] [2025-03-03 14:41:15,347 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-03 14:41:15,347 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:41:15,347 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:41:15,349 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) [2025-03-03 14:41:15,351 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-03 14:41:15,431 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 135 statements into 2 equivalence classes. [2025-03-03 14:41:15,544 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 133 of 135 statements. [2025-03-03 14:41:15,545 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-03 14:41:15,545 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:41:15,548 INFO L256 TraceCheckSpWp]: Trace formula consists of 612 conjuncts, 205 conjuncts are in the unsatisfiable core [2025-03-03 14:41:15,553 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:41:15,701 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 17 treesize of output 9 [2025-03-03 14:41:16,016 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 35 treesize of output 23 [2025-03-03 14:41:16,060 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 15 [2025-03-03 14:41:16,062 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 11 [2025-03-03 14:41:16,306 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 46 treesize of output 30 [2025-03-03 14:41:16,665 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 49 treesize of output 33 [2025-03-03 14:41:16,668 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 [2025-03-03 14:41:16,671 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 [2025-03-03 14:41:16,757 INFO L134 CoverageAnalysis]: Checked inductivity of 628 backedges. 223 proven. 46 refuted. 0 times theorem prover too weak. 359 trivial. 0 not checked. [2025-03-03 14:41:16,757 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:41:18,762 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 14:41:18,763 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 102 treesize of output 101 [2025-03-03 14:41:18,780 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 14:41:18,780 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 128 treesize of output 119 [2025-03-03 14:41:18,977 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:41:18,977 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [30680904] [2025-03-03 14:41:18,977 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:41:18,977 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1167021575] [2025-03-03 14:41:18,977 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1167021575] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:41:18,977 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:41:18,977 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2025-03-03 14:41:18,978 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1708916457] [2025-03-03 14:41:18,978 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:41:18,978 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-03-03 14:41:18,978 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:41:18,978 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-03-03 14:41:18,978 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=884, Unknown=0, NotChecked=0, Total=992 [2025-03-03 14:41:18,979 INFO L87 Difference]: Start difference. First operand 131 states and 152 transitions. Second operand has 26 states, 19 states have (on average 2.263157894736842) internal successors, (43), 21 states have internal predecessors, (43), 12 states have call successors, (18), 6 states have call predecessors, (18), 7 states have return successors, (16), 10 states have call predecessors, (16), 10 states have call successors, (16) [2025-03-03 14:41:20,502 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:41:20,502 INFO L93 Difference]: Finished difference Result 186 states and 211 transitions. [2025-03-03 14:41:20,503 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2025-03-03 14:41:20,503 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 19 states have (on average 2.263157894736842) internal successors, (43), 21 states have internal predecessors, (43), 12 states have call successors, (18), 6 states have call predecessors, (18), 7 states have return successors, (16), 10 states have call predecessors, (16), 10 states have call successors, (16) Word has length 135 [2025-03-03 14:41:20,504 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:41:20,504 INFO L225 Difference]: With dead ends: 186 [2025-03-03 14:41:20,505 INFO L226 Difference]: Without dead ends: 184 [2025-03-03 14:41:20,505 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 119 SyntacticMatches, 3 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 517 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=269, Invalid=2083, Unknown=0, NotChecked=0, Total=2352 [2025-03-03 14:41:20,505 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 62 mSDsluCounter, 359 mSDsCounter, 0 mSdLazyCounter, 1136 mSolverCounterSat, 47 mSolverCounterUnsat, 6 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 402 SdHoareTripleChecker+Invalid, 1189 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 1136 IncrementalHoareTripleChecker+Invalid, 6 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:41:20,506 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 402 Invalid, 1189 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 1136 Invalid, 6 Unknown, 0 Unchecked, 1.0s Time] [2025-03-03 14:41:20,506 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2025-03-03 14:41:20,539 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 124. [2025-03-03 14:41:20,539 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 81 states have (on average 1.1111111111111112) internal successors, (90), 84 states have internal predecessors, (90), 23 states have call successors, (23), 17 states have call predecessors, (23), 19 states have return successors, (26), 22 states have call predecessors, (26), 20 states have call successors, (26) [2025-03-03 14:41:20,540 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 139 transitions. [2025-03-03 14:41:20,541 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 139 transitions. Word has length 135 [2025-03-03 14:41:20,542 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:41:20,542 INFO L471 AbstractCegarLoop]: Abstraction has 124 states and 139 transitions. [2025-03-03 14:41:20,542 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 19 states have (on average 2.263157894736842) internal successors, (43), 21 states have internal predecessors, (43), 12 states have call successors, (18), 6 states have call predecessors, (18), 7 states have return successors, (16), 10 states have call predecessors, (16), 10 states have call successors, (16) [2025-03-03 14:41:20,542 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 139 transitions. [2025-03-03 14:41:20,543 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2025-03-03 14:41:20,544 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:41:20,544 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:41:20,552 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-03-03 14:41:20,744 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2025-03-03 14:41:20,744 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:41:20,745 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:41:20,745 INFO L85 PathProgramCache]: Analyzing trace with hash 700603177, now seen corresponding path program 1 times [2025-03-03 14:41:20,745 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:41:20,745 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1539398990] [2025-03-03 14:41:20,745 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:41:20,745 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:41:20,753 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-03-03 14:41:20,761 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-03-03 14:41:20,761 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:41:20,761 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:41:20,945 INFO L134 CoverageAnalysis]: Checked inductivity of 139 backedges. 17 proven. 10 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2025-03-03 14:41:20,946 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:41:20,946 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1539398990] [2025-03-03 14:41:20,946 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1539398990] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:41:20,946 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1643654954] [2025-03-03 14:41:20,946 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:41:20,946 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:41:20,946 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:41:20,948 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:41:20,949 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-03 14:41:21,025 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 73 statements into 1 equivalence classes. [2025-03-03 14:41:21,060 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 73 of 73 statements. [2025-03-03 14:41:21,060 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:41:21,060 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:41:21,064 INFO L256 TraceCheckSpWp]: Trace formula consists of 440 conjuncts, 42 conjuncts are in the unsatisfiable core [2025-03-03 14:41:21,067 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:41:21,070 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 [2025-03-03 14:41:21,170 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 [2025-03-03 14:41:21,230 INFO L134 CoverageAnalysis]: Checked inductivity of 139 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2025-03-03 14:41:21,230 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:41:21,425 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1643654954] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:41:21,425 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:41:21,425 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 17 [2025-03-03 14:41:21,425 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1989448627] [2025-03-03 14:41:21,425 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:41:21,425 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-03 14:41:21,425 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:41:21,426 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-03 14:41:21,426 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=343, Unknown=0, NotChecked=0, Total=420 [2025-03-03 14:41:21,426 INFO L87 Difference]: Start difference. First operand 124 states and 139 transitions. Second operand has 17 states, 12 states have (on average 3.3333333333333335) internal successors, (40), 15 states have internal predecessors, (40), 11 states have call successors, (18), 3 states have call predecessors, (18), 6 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) [2025-03-03 14:41:21,666 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:41:21,667 INFO L93 Difference]: Finished difference Result 129 states and 147 transitions. [2025-03-03 14:41:21,667 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-03 14:41:21,667 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 12 states have (on average 3.3333333333333335) internal successors, (40), 15 states have internal predecessors, (40), 11 states have call successors, (18), 3 states have call predecessors, (18), 6 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) Word has length 73 [2025-03-03 14:41:21,667 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:41:21,668 INFO L225 Difference]: With dead ends: 129 [2025-03-03 14:41:21,668 INFO L226 Difference]: Without dead ends: 117 [2025-03-03 14:41:21,668 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 96 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 127 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=113, Invalid=487, Unknown=0, NotChecked=0, Total=600 [2025-03-03 14:41:21,668 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 20 mSDsluCounter, 183 mSDsCounter, 0 mSdLazyCounter, 408 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 218 SdHoareTripleChecker+Invalid, 427 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 408 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 14:41:21,669 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 218 Invalid, 427 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 408 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 14:41:21,669 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2025-03-03 14:41:21,686 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 114. [2025-03-03 14:41:21,687 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 114 states, 75 states have (on average 1.0933333333333333) internal successors, (82), 77 states have internal predecessors, (82), 21 states have call successors, (21), 16 states have call predecessors, (21), 17 states have return successors, (24), 20 states have call predecessors, (24), 19 states have call successors, (24) [2025-03-03 14:41:21,687 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 127 transitions. [2025-03-03 14:41:21,687 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 127 transitions. Word has length 73 [2025-03-03 14:41:21,687 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:41:21,688 INFO L471 AbstractCegarLoop]: Abstraction has 114 states and 127 transitions. [2025-03-03 14:41:21,688 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 12 states have (on average 3.3333333333333335) internal successors, (40), 15 states have internal predecessors, (40), 11 states have call successors, (18), 3 states have call predecessors, (18), 6 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) [2025-03-03 14:41:21,688 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 127 transitions. [2025-03-03 14:41:21,688 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-03-03 14:41:21,688 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:41:21,688 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:41:21,694 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-03 14:41:21,888 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-03-03 14:41:21,889 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:41:21,889 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:41:21,889 INFO L85 PathProgramCache]: Analyzing trace with hash -677267268, now seen corresponding path program 1 times [2025-03-03 14:41:21,889 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:41:21,889 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [652034587] [2025-03-03 14:41:21,889 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:41:21,889 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:41:21,899 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-03-03 14:41:21,919 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-03-03 14:41:21,919 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:41:21,919 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:41:21,920 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [492729096] [2025-03-03 14:41:21,921 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:41:21,921 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:41:21,921 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:41:21,923 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:41:21,925 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-03 14:41:22,007 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 74 statements into 1 equivalence classes. [2025-03-03 14:41:22,066 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 74 of 74 statements. [2025-03-03 14:41:22,066 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:41:22,066 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:41:22,070 INFO L256 TraceCheckSpWp]: Trace formula consists of 514 conjuncts, 224 conjuncts are in the unsatisfiable core [2025-03-03 14:41:22,074 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:41:22,078 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 [2025-03-03 14:41:22,083 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 [2025-03-03 14:41:22,085 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 [2025-03-03 14:41:22,090 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 [2025-03-03 14:41:22,096 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 [2025-03-03 14:41:22,100 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 [2025-03-03 14:41:22,569 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2025-03-03 14:41:23,022 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 [2025-03-03 14:41:23,031 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 [2025-03-03 14:41:23,716 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 [2025-03-03 14:41:23,722 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 [2025-03-03 14:41:23,837 INFO L349 Elim1Store]: treesize reduction 60, result has 41.7 percent of original size [2025-03-03 14:41:23,837 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 65 treesize of output 79 [2025-03-03 14:41:23,890 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2025-03-03 14:41:23,890 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 29 [2025-03-03 14:41:24,193 INFO L134 CoverageAnalysis]: Checked inductivity of 142 backedges. 54 proven. 38 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2025-03-03 14:41:24,193 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:41:25,877 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:41:25,877 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [652034587] [2025-03-03 14:41:25,877 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:41:25,877 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [492729096] [2025-03-03 14:41:25,877 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [492729096] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:41:25,877 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:41:25,877 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2025-03-03 14:41:25,877 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1324625220] [2025-03-03 14:41:25,877 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:41:25,878 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-03-03 14:41:25,878 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:41:25,878 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-03-03 14:41:25,878 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=1012, Unknown=0, NotChecked=0, Total=1122 [2025-03-03 14:41:25,878 INFO L87 Difference]: Start difference. First operand 114 states and 127 transitions. Second operand has 26 states, 21 states have (on average 1.7142857142857142) internal successors, (36), 21 states have internal predecessors, (36), 10 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (10), 6 states have call predecessors, (10), 7 states have call successors, (10) [2025-03-03 14:41:28,152 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:41:28,152 INFO L93 Difference]: Finished difference Result 156 states and 183 transitions. [2025-03-03 14:41:28,152 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2025-03-03 14:41:28,153 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 21 states have (on average 1.7142857142857142) internal successors, (36), 21 states have internal predecessors, (36), 10 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (10), 6 states have call predecessors, (10), 7 states have call successors, (10) Word has length 74 [2025-03-03 14:41:28,153 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:41:28,153 INFO L225 Difference]: With dead ends: 156 [2025-03-03 14:41:28,153 INFO L226 Difference]: Without dead ends: 154 [2025-03-03 14:41:28,154 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 59 SyntacticMatches, 7 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 629 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=231, Invalid=2219, Unknown=0, NotChecked=0, Total=2450 [2025-03-03 14:41:28,154 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 72 mSDsluCounter, 244 mSDsCounter, 0 mSdLazyCounter, 1105 mSolverCounterSat, 33 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 75 SdHoareTripleChecker+Valid, 275 SdHoareTripleChecker+Invalid, 1140 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 1105 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2025-03-03 14:41:28,154 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [75 Valid, 275 Invalid, 1140 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 1105 Invalid, 2 Unknown, 0 Unchecked, 1.3s Time] [2025-03-03 14:41:28,155 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 154 states. [2025-03-03 14:41:28,183 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 154 to 150. [2025-03-03 14:41:28,183 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 150 states, 99 states have (on average 1.101010101010101) internal successors, (109), 101 states have internal predecessors, (109), 27 states have call successors, (27), 21 states have call predecessors, (27), 23 states have return successors, (36), 27 states have call predecessors, (36), 25 states have call successors, (36) [2025-03-03 14:41:28,184 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 150 states to 150 states and 172 transitions. [2025-03-03 14:41:28,184 INFO L78 Accepts]: Start accepts. Automaton has 150 states and 172 transitions. Word has length 74 [2025-03-03 14:41:28,184 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:41:28,184 INFO L471 AbstractCegarLoop]: Abstraction has 150 states and 172 transitions. [2025-03-03 14:41:28,184 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 21 states have (on average 1.7142857142857142) internal successors, (36), 21 states have internal predecessors, (36), 10 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (10), 6 states have call predecessors, (10), 7 states have call successors, (10) [2025-03-03 14:41:28,184 INFO L276 IsEmpty]: Start isEmpty. Operand 150 states and 172 transitions. [2025-03-03 14:41:28,187 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2025-03-03 14:41:28,187 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:41:28,187 INFO L218 NwaCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:41:28,194 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-03 14:41:28,391 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-03-03 14:41:28,391 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:41:28,391 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:41:28,391 INFO L85 PathProgramCache]: Analyzing trace with hash -54213339, now seen corresponding path program 2 times [2025-03-03 14:41:28,391 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:41:28,391 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1898182235] [2025-03-03 14:41:28,391 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:41:28,391 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:41:28,401 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 98 statements into 2 equivalence classes. [2025-03-03 14:41:28,418 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 98 of 98 statements. [2025-03-03 14:41:28,418 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:41:28,418 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:41:28,419 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1438916370] [2025-03-03 14:41:28,419 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:41:28,419 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:41:28,419 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:41:28,422 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:41:28,423 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-03 14:41:28,509 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 98 statements into 2 equivalence classes. [2025-03-03 14:41:28,583 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 98 of 98 statements. [2025-03-03 14:41:28,583 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:41:28,583 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:41:28,587 INFO L256 TraceCheckSpWp]: Trace formula consists of 620 conjuncts, 211 conjuncts are in the unsatisfiable core [2025-03-03 14:41:28,591 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:41:28,595 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 [2025-03-03 14:41:28,598 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 [2025-03-03 14:41:28,602 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 [2025-03-03 14:41:28,606 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 [2025-03-03 14:41:28,611 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 [2025-03-03 14:41:28,615 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 [2025-03-03 14:41:29,213 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 [2025-03-03 14:41:29,220 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 [2025-03-03 14:41:29,657 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 [2025-03-03 14:41:29,663 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 [2025-03-03 14:41:29,717 INFO L349 Elim1Store]: treesize reduction 18, result has 60.9 percent of original size [2025-03-03 14:41:29,718 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 40 treesize of output 51 [2025-03-03 14:41:29,747 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2025-03-03 14:41:29,747 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 29 [2025-03-03 14:41:29,945 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 14:41:29,945 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 92 treesize of output 184 [2025-03-03 14:41:29,973 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 14:41:29,973 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 140 treesize of output 168 [2025-03-03 14:41:30,134 INFO L134 CoverageAnalysis]: Checked inductivity of 279 backedges. 75 proven. 48 refuted. 0 times theorem prover too weak. 156 trivial. 0 not checked. [2025-03-03 14:41:30,134 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:41:36,499 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:41:36,500 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1898182235] [2025-03-03 14:41:36,500 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:41:36,500 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1438916370] [2025-03-03 14:41:36,500 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1438916370] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:41:36,500 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:41:36,500 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2025-03-03 14:41:36,500 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [259915531] [2025-03-03 14:41:36,500 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:41:36,500 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-03 14:41:36,500 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:41:36,500 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-03 14:41:36,501 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=952, Unknown=1, NotChecked=0, Total=1056 [2025-03-03 14:41:36,501 INFO L87 Difference]: Start difference. First operand 150 states and 172 transitions. Second operand has 21 states, 17 states have (on average 2.235294117647059) internal successors, (38), 17 states have internal predecessors, (38), 9 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) [2025-03-03 14:41:38,351 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:41:38,351 INFO L93 Difference]: Finished difference Result 192 states and 228 transitions. [2025-03-03 14:41:38,352 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-03 14:41:38,352 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 17 states have (on average 2.235294117647059) internal successors, (38), 17 states have internal predecessors, (38), 9 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) Word has length 98 [2025-03-03 14:41:38,352 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:41:38,353 INFO L225 Difference]: With dead ends: 192 [2025-03-03 14:41:38,353 INFO L226 Difference]: Without dead ends: 190 [2025-03-03 14:41:38,353 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 91 SyntacticMatches, 3 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 407 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=167, Invalid=1472, Unknown=1, NotChecked=0, Total=1640 [2025-03-03 14:41:38,354 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 48 mSDsluCounter, 272 mSDsCounter, 0 mSdLazyCounter, 1009 mSolverCounterSat, 21 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 315 SdHoareTripleChecker+Invalid, 1032 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 1009 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2025-03-03 14:41:38,354 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 315 Invalid, 1032 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 1009 Invalid, 2 Unknown, 0 Unchecked, 1.2s Time] [2025-03-03 14:41:38,354 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 190 states. [2025-03-03 14:41:38,394 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 190 to 152. [2025-03-03 14:41:38,395 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 100 states have (on average 1.1) internal successors, (110), 102 states have internal predecessors, (110), 27 states have call successors, (27), 21 states have call predecessors, (27), 24 states have return successors, (38), 28 states have call predecessors, (38), 25 states have call successors, (38) [2025-03-03 14:41:38,395 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 175 transitions. [2025-03-03 14:41:38,395 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 175 transitions. Word has length 98 [2025-03-03 14:41:38,396 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:41:38,396 INFO L471 AbstractCegarLoop]: Abstraction has 152 states and 175 transitions. [2025-03-03 14:41:38,396 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 17 states have (on average 2.235294117647059) internal successors, (38), 17 states have internal predecessors, (38), 9 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) [2025-03-03 14:41:38,396 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 175 transitions. [2025-03-03 14:41:38,396 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2025-03-03 14:41:38,396 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:41:38,396 INFO L218 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:41:38,403 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-03-03 14:41:38,597 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2025-03-03 14:41:38,597 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:41:38,597 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:41:38,597 INFO L85 PathProgramCache]: Analyzing trace with hash -1058655922, now seen corresponding path program 3 times [2025-03-03 14:41:38,597 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:41:38,597 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1265851993] [2025-03-03 14:41:38,597 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:41:38,597 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:41:38,608 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 122 statements into 7 equivalence classes. [2025-03-03 14:41:38,672 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) and asserted 122 of 122 statements. [2025-03-03 14:41:38,672 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2025-03-03 14:41:38,672 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:41:38,674 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [957800140] [2025-03-03 14:41:38,674 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:41:38,675 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:41:38,675 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:41:38,676 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:41:38,678 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-03 14:41:38,773 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 122 statements into 7 equivalence classes. [2025-03-03 14:41:39,030 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 86 of 122 statements. [2025-03-03 14:41:39,030 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-03 14:41:39,030 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:41:39,036 INFO L256 TraceCheckSpWp]: Trace formula consists of 651 conjuncts, 295 conjuncts are in the unsatisfiable core [2025-03-03 14:41:39,043 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:41:39,048 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 [2025-03-03 14:41:39,052 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 [2025-03-03 14:41:39,056 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 [2025-03-03 14:41:39,061 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 [2025-03-03 14:41:39,067 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 [2025-03-03 14:41:39,074 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 [2025-03-03 14:41:40,398 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 [2025-03-03 14:41:40,415 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 [2025-03-03 14:41:40,966 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 [2025-03-03 14:41:40,987 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 [2025-03-03 14:41:41,065 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2025-03-03 14:41:41,066 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 29 [2025-03-03 14:41:41,090 INFO L349 Elim1Store]: treesize reduction 14, result has 58.8 percent of original size [2025-03-03 14:41:41,090 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 40 treesize of output 43 [2025-03-03 14:41:41,275 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 14:41:41,275 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 72 treesize of output 112 [2025-03-03 14:41:41,289 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 14:41:41,289 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 44 treesize of output 52 [2025-03-03 14:41:41,384 INFO L134 CoverageAnalysis]: Checked inductivity of 464 backedges. 108 proven. 106 refuted. 0 times theorem prover too weak. 250 trivial. 0 not checked. [2025-03-03 14:41:41,384 INFO L312 TraceCheckSpWp]: Computing backward predicates...