./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/verifythis/duplets.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version e2fb8bed 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/verifythis/duplets.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 ac76721ba91522692e2c3e4d1ea27df0200031dd012c5066cc7280e0ae6e2244 --- Real Ultimate output --- This is Ultimate 0.3.0-?-e2fb8be-m [2025-03-08 05:21:08,041 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-08 05:21:08,081 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-08 05:21:08,089 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-08 05:21:08,089 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-08 05:21:08,110 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-08 05:21:08,111 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-08 05:21:08,111 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-08 05:21:08,111 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-08 05:21:08,111 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-08 05:21:08,111 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-08 05:21:08,111 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-08 05:21:08,112 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-08 05:21:08,112 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-08 05:21:08,112 INFO L153 SettingsManager]: * Use SBE=true [2025-03-08 05:21:08,112 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-08 05:21:08,112 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-08 05:21:08,112 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-08 05:21:08,112 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-08 05:21:08,112 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-08 05:21:08,112 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-08 05:21:08,113 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-08 05:21:08,113 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-08 05:21:08,113 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-08 05:21:08,113 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-08 05:21:08,113 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-08 05:21:08,113 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-08 05:21:08,113 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-08 05:21:08,113 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-08 05:21:08,113 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-08 05:21:08,113 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-08 05:21:08,113 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-08 05:21:08,113 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:21:08,113 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-08 05:21:08,113 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-08 05:21:08,114 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-08 05:21:08,114 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-08 05:21:08,114 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-08 05:21:08,114 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-08 05:21:08,114 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-08 05:21:08,114 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-08 05:21:08,114 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-08 05:21:08,114 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-08 05:21:08,114 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 -> ac76721ba91522692e2c3e4d1ea27df0200031dd012c5066cc7280e0ae6e2244 [2025-03-08 05:21:08,329 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-08 05:21:08,337 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-08 05:21:08,339 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-08 05:21:08,340 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-08 05:21:08,340 INFO L274 PluginConnector]: CDTParser initialized [2025-03-08 05:21:08,341 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/verifythis/duplets.c [2025-03-08 05:21:09,512 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e1aab7985/aa1e909f32664836aa6ff9e62964dbcc/FLAG45e7b1064 [2025-03-08 05:21:09,731 INFO L384 CDTParser]: Found 1 translation units. [2025-03-08 05:21:09,732 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/verifythis/duplets.c [2025-03-08 05:21:09,739 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e1aab7985/aa1e909f32664836aa6ff9e62964dbcc/FLAG45e7b1064 [2025-03-08 05:21:09,749 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e1aab7985/aa1e909f32664836aa6ff9e62964dbcc [2025-03-08 05:21:09,751 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-08 05:21:09,752 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-08 05:21:09,753 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-08 05:21:09,753 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-08 05:21:09,755 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-08 05:21:09,756 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:09,756 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@543a3ee4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09, skipping insertion in model container [2025-03-08 05:21:09,756 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:09,766 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-08 05:21:09,873 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/verifythis/duplets.c[485,498] [2025-03-08 05:21:09,895 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:21:09,904 INFO L200 MainTranslator]: Completed pre-run [2025-03-08 05:21:09,912 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/verifythis/duplets.c[485,498] [2025-03-08 05:21:09,922 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:21:09,938 INFO L204 MainTranslator]: Completed translation [2025-03-08 05:21:09,939 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09 WrapperNode [2025-03-08 05:21:09,939 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-08 05:21:09,940 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-08 05:21:09,940 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-08 05:21:09,940 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-08 05:21:09,944 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:09,949 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:09,968 INFO L138 Inliner]: procedures = 21, calls = 43, calls flagged for inlining = 5, calls inlined = 5, statements flattened = 118 [2025-03-08 05:21:09,970 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-08 05:21:09,971 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-08 05:21:09,971 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-08 05:21:09,971 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-08 05:21:09,978 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:09,978 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:09,980 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:09,996 INFO L175 MemorySlicer]: Split 19 memory accesses to 4 slices as follows [2, 7, 5, 5]. 37 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0]. The 5 writes are split as follows [0, 3, 1, 1]. [2025-03-08 05:21:10,000 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:10,000 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:10,008 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:10,011 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:10,012 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:10,013 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:10,015 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-08 05:21:10,019 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-08 05:21:10,019 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-08 05:21:10,019 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-08 05:21:10,020 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09" (1/1) ... [2025-03-08 05:21:10,028 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:21:10,037 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:21:10,048 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-08 05:21:10,053 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-08 05:21:10,069 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-08 05:21:10,069 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-08 05:21:10,069 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-08 05:21:10,069 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-08 05:21:10,069 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-08 05:21:10,070 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-03-08 05:21:10,070 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2025-03-08 05:21:10,070 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-03-08 05:21:10,070 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-03-08 05:21:10,070 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-03-08 05:21:10,070 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-03-08 05:21:10,070 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2025-03-08 05:21:10,070 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2025-03-08 05:21:10,070 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-08 05:21:10,070 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-08 05:21:10,071 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-03-08 05:21:10,071 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-03-08 05:21:10,071 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-03-08 05:21:10,071 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2025-03-08 05:21:10,071 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-08 05:21:10,072 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-08 05:21:10,072 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-08 05:21:10,151 INFO L256 CfgBuilder]: Building ICFG [2025-03-08 05:21:10,153 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-08 05:21:10,313 INFO L1307 $ProcedureCfgBuilder]: dead code at ProgramPoint L56: call ULTIMATE.dealloc(main_~#i~2#1.base, main_~#i~2#1.offset);havoc main_~#i~2#1.base, main_~#i~2#1.offset;call ULTIMATE.dealloc(main_~#j~2#1.base, main_~#j~2#1.offset);havoc main_~#j~2#1.base, main_~#j~2#1.offset; [2025-03-08 05:21:10,336 INFO L? ?]: Removed 46 outVars from TransFormulas that were not future-live. [2025-03-08 05:21:10,336 INFO L307 CfgBuilder]: Performing block encoding [2025-03-08 05:21:10,343 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-08 05:21:10,343 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-08 05:21:10,343 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:21:10 BoogieIcfgContainer [2025-03-08 05:21:10,344 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-08 05:21:10,345 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-08 05:21:10,345 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-08 05:21:10,348 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-08 05:21:10,349 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.03 05:21:09" (1/3) ... [2025-03-08 05:21:10,349 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@73ea6d3d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:21:10, skipping insertion in model container [2025-03-08 05:21:10,349 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:21:09" (2/3) ... [2025-03-08 05:21:10,349 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@73ea6d3d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:21:10, skipping insertion in model container [2025-03-08 05:21:10,349 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:21:10" (3/3) ... [2025-03-08 05:21:10,350 INFO L128 eAbstractionObserver]: Analyzing ICFG duplets.c [2025-03-08 05:21:10,359 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-08 05:21:10,360 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG duplets.c that has 3 procedures, 39 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-08 05:21:10,393 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-08 05:21:10,400 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;@2ff5238, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-08 05:21:10,401 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-08 05:21:10,403 INFO L276 IsEmpty]: Start isEmpty. Operand has 39 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 27 states have internal predecessors, (34), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-08 05:21:10,407 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-08 05:21:10,408 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:10,408 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:21:10,408 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:10,411 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:10,412 INFO L85 PathProgramCache]: Analyzing trace with hash -1179486165, now seen corresponding path program 1 times [2025-03-08 05:21:10,417 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:10,417 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1022740502] [2025-03-08 05:21:10,417 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:10,418 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:10,483 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-08 05:21:10,494 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 05:21:10,494 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:10,494 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:10,553 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-08 05:21:10,554 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:10,554 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1022740502] [2025-03-08 05:21:10,555 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1022740502] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:21:10,555 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1073242099] [2025-03-08 05:21:10,555 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:10,555 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:21:10,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:21:10,557 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-08 05:21:10,558 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-08 05:21:10,616 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-08 05:21:10,645 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 05:21:10,645 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:10,646 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:10,647 INFO L256 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-08 05:21:10,650 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:21:10,658 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-08 05:21:10,660 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:21:10,661 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1073242099] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:21:10,661 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:21:10,661 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-08 05:21:10,662 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2016970778] [2025-03-08 05:21:10,663 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:21:10,665 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-08 05:21:10,665 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:10,679 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-08 05:21:10,680 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 05:21:10,681 INFO L87 Difference]: Start difference. First operand has 39 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 27 states have internal predecessors, (34), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 2 states, 2 states have (on average 8.0) internal successors, (16), 2 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-08 05:21:10,692 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:10,692 INFO L93 Difference]: Finished difference Result 75 states and 109 transitions. [2025-03-08 05:21:10,693 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-08 05:21:10,693 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 8.0) internal successors, (16), 2 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 32 [2025-03-08 05:21:10,694 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:10,697 INFO L225 Difference]: With dead ends: 75 [2025-03-08 05:21:10,697 INFO L226 Difference]: Without dead ends: 35 [2025-03-08 05:21:10,699 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 05:21:10,701 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 50 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:10,701 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:21:10,709 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2025-03-08 05:21:10,717 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2025-03-08 05:21:10,718 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 24 states have internal predecessors, (29), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-08 05:21:10,723 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 46 transitions. [2025-03-08 05:21:10,724 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 46 transitions. Word has length 32 [2025-03-08 05:21:10,724 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:10,724 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 46 transitions. [2025-03-08 05:21:10,725 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 8.0) internal successors, (16), 2 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-08 05:21:10,725 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 46 transitions. [2025-03-08 05:21:10,725 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-08 05:21:10,725 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:10,726 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:21:10,733 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-08 05:21:10,926 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2025-03-08 05:21:10,927 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:10,927 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:10,927 INFO L85 PathProgramCache]: Analyzing trace with hash 764609963, now seen corresponding path program 1 times [2025-03-08 05:21:10,927 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:10,927 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [166803857] [2025-03-08 05:21:10,927 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:10,927 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:10,942 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-08 05:21:10,980 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 05:21:10,980 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:10,980 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:11,284 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-08 05:21:11,284 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:11,284 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [166803857] [2025-03-08 05:21:11,284 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [166803857] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:21:11,284 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2113129009] [2025-03-08 05:21:11,285 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:11,285 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:21:11,285 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:21:11,287 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-08 05:21:11,288 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-08 05:21:11,342 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-08 05:21:11,371 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 05:21:11,371 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:11,372 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:11,376 INFO L256 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-08 05:21:11,379 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:21:11,435 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-08 05:21:11,435 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:21:11,598 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-08 05:21:11,598 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2113129009] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:21:11,598 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:21:11,598 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 12 [2025-03-08 05:21:11,598 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [659942716] [2025-03-08 05:21:11,598 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:21:11,599 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-08 05:21:11,599 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:11,599 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-08 05:21:11,600 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2025-03-08 05:21:11,600 INFO L87 Difference]: Start difference. First operand 35 states and 46 transitions. Second operand has 12 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 12 states have internal predecessors, (25), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 5 states have call predecessors, (8), 5 states have call successors, (8) [2025-03-08 05:21:11,716 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:11,716 INFO L93 Difference]: Finished difference Result 61 states and 82 transitions. [2025-03-08 05:21:11,717 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-08 05:21:11,718 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 12 states have internal predecessors, (25), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 5 states have call predecessors, (8), 5 states have call successors, (8) Word has length 32 [2025-03-08 05:21:11,718 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:11,718 INFO L225 Difference]: With dead ends: 61 [2025-03-08 05:21:11,718 INFO L226 Difference]: Without dead ends: 43 [2025-03-08 05:21:11,719 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 58 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=49, Invalid=161, Unknown=0, NotChecked=0, Total=210 [2025-03-08 05:21:11,719 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 27 mSDsluCounter, 192 mSDsCounter, 0 mSdLazyCounter, 91 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 230 SdHoareTripleChecker+Invalid, 97 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 91 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:11,719 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 230 Invalid, 97 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 91 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:21:11,720 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2025-03-08 05:21:11,724 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 36. [2025-03-08 05:21:11,724 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 24 states have (on average 1.25) internal successors, (30), 25 states have internal predecessors, (30), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-08 05:21:11,725 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 47 transitions. [2025-03-08 05:21:11,725 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 47 transitions. Word has length 32 [2025-03-08 05:21:11,725 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:11,725 INFO L471 AbstractCegarLoop]: Abstraction has 36 states and 47 transitions. [2025-03-08 05:21:11,725 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 12 states have internal predecessors, (25), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 5 states have call predecessors, (8), 5 states have call successors, (8) [2025-03-08 05:21:11,725 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 47 transitions. [2025-03-08 05:21:11,727 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2025-03-08 05:21:11,727 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:11,727 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:21:11,734 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-08 05:21:11,928 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,SelfDestructingSolverStorable1 [2025-03-08 05:21:11,928 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:11,929 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:11,930 INFO L85 PathProgramCache]: Analyzing trace with hash -1221149500, now seen corresponding path program 1 times [2025-03-08 05:21:11,930 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:11,930 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1538119226] [2025-03-08 05:21:11,930 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:11,930 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:11,941 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 34 statements into 1 equivalence classes. [2025-03-08 05:21:11,962 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 34 of 34 statements. [2025-03-08 05:21:11,962 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:11,962 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:12,339 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-08 05:21:12,339 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:12,339 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1538119226] [2025-03-08 05:21:12,339 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1538119226] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:21:12,339 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:21:12,339 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2025-03-08 05:21:12,339 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1378466216] [2025-03-08 05:21:12,339 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:21:12,340 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-08 05:21:12,340 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:12,341 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-08 05:21:12,341 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=89, Unknown=0, NotChecked=0, Total=110 [2025-03-08 05:21:12,342 INFO L87 Difference]: Start difference. First operand 36 states and 47 transitions. Second operand has 11 states, 8 states have (on average 2.375) internal successors, (19), 8 states have internal predecessors, (19), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-08 05:21:12,589 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:12,589 INFO L93 Difference]: Finished difference Result 65 states and 89 transitions. [2025-03-08 05:21:12,589 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-08 05:21:12,589 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 8 states have (on average 2.375) internal successors, (19), 8 states have internal predecessors, (19), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 34 [2025-03-08 05:21:12,589 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:12,590 INFO L225 Difference]: With dead ends: 65 [2025-03-08 05:21:12,590 INFO L226 Difference]: Without dead ends: 44 [2025-03-08 05:21:12,590 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=217, Unknown=0, NotChecked=0, Total=272 [2025-03-08 05:21:12,591 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 26 mSDsluCounter, 270 mSDsCounter, 0 mSdLazyCounter, 153 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 309 SdHoareTripleChecker+Invalid, 159 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 153 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:12,591 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 309 Invalid, 159 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 153 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:21:12,591 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2025-03-08 05:21:12,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2025-03-08 05:21:12,595 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 25 states have (on average 1.24) internal successors, (31), 26 states have internal predecessors, (31), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-08 05:21:12,596 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 48 transitions. [2025-03-08 05:21:12,596 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 48 transitions. Word has length 34 [2025-03-08 05:21:12,596 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:12,596 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 48 transitions. [2025-03-08 05:21:12,596 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 8 states have (on average 2.375) internal successors, (19), 8 states have internal predecessors, (19), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-08 05:21:12,597 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 48 transitions. [2025-03-08 05:21:12,597 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2025-03-08 05:21:12,597 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:12,597 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:21:12,597 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-08 05:21:12,597 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:12,598 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:12,598 INFO L85 PathProgramCache]: Analyzing trace with hash -76578106, now seen corresponding path program 1 times [2025-03-08 05:21:12,598 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:12,598 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2109480996] [2025-03-08 05:21:12,598 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:12,598 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:12,610 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 34 statements into 1 equivalence classes. [2025-03-08 05:21:12,617 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 34 of 34 statements. [2025-03-08 05:21:12,617 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:12,617 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:12,674 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:21:12,675 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:12,675 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2109480996] [2025-03-08 05:21:12,675 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2109480996] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:21:12,675 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:21:12,675 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-03-08 05:21:12,675 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [148771818] [2025-03-08 05:21:12,675 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:21:12,676 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-08 05:21:12,676 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:12,676 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-08 05:21:12,676 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-08 05:21:12,677 INFO L87 Difference]: Start difference. First operand 37 states and 48 transitions. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:21:12,713 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:12,713 INFO L93 Difference]: Finished difference Result 55 states and 71 transitions. [2025-03-08 05:21:12,713 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-08 05:21:12,714 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 34 [2025-03-08 05:21:12,715 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:12,715 INFO L225 Difference]: With dead ends: 55 [2025-03-08 05:21:12,715 INFO L226 Difference]: Without dead ends: 53 [2025-03-08 05:21:12,716 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-08 05:21:12,717 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 11 mSDsluCounter, 169 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 214 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:12,717 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 214 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:21:12,718 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2025-03-08 05:21:12,726 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 43. [2025-03-08 05:21:12,726 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 29 states have (on average 1.206896551724138) internal successors, (35), 31 states have internal predecessors, (35), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-08 05:21:12,727 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 54 transitions. [2025-03-08 05:21:12,727 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 54 transitions. Word has length 34 [2025-03-08 05:21:12,728 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:12,728 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 54 transitions. [2025-03-08 05:21:12,728 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:21:12,728 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 54 transitions. [2025-03-08 05:21:12,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2025-03-08 05:21:12,728 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:12,732 INFO L218 NwaCegarLoop]: trace histogram [4, 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] [2025-03-08 05:21:12,733 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2025-03-08 05:21:12,733 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:12,733 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:12,733 INFO L85 PathProgramCache]: Analyzing trace with hash 279007717, now seen corresponding path program 1 times [2025-03-08 05:21:12,733 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:12,733 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [475363018] [2025-03-08 05:21:12,733 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:12,733 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:12,749 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 36 statements into 1 equivalence classes. [2025-03-08 05:21:12,756 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 36 of 36 statements. [2025-03-08 05:21:12,756 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:12,756 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:12,805 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:21:12,806 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:12,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [475363018] [2025-03-08 05:21:12,806 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [475363018] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:21:12,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1638667351] [2025-03-08 05:21:12,806 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:12,806 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:21:12,806 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:21:12,808 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-08 05:21:12,809 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-08 05:21:12,862 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 36 statements into 1 equivalence classes. [2025-03-08 05:21:12,880 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 36 of 36 statements. [2025-03-08 05:21:12,881 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:12,881 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:12,881 INFO L256 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-08 05:21:12,883 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:21:12,894 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:21:12,895 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:21:12,921 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:21:12,921 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1638667351] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:21:12,921 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:21:12,921 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 5 [2025-03-08 05:21:12,922 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [566635985] [2025-03-08 05:21:12,922 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:21:12,922 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:21:12,922 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:12,922 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:21:12,922 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:21:12,922 INFO L87 Difference]: Start difference. First operand 43 states and 54 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 5 states have internal predecessors, (18), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:21:12,971 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:12,972 INFO L93 Difference]: Finished difference Result 63 states and 81 transitions. [2025-03-08 05:21:12,973 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:21:12,973 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 5 states have internal predecessors, (18), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 36 [2025-03-08 05:21:12,974 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:12,975 INFO L225 Difference]: With dead ends: 63 [2025-03-08 05:21:12,976 INFO L226 Difference]: Without dead ends: 45 [2025-03-08 05:21:12,976 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 69 SyntacticMatches, 3 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2025-03-08 05:21:12,977 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 1 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:12,977 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 118 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:21:12,977 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2025-03-08 05:21:12,986 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2025-03-08 05:21:12,987 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 31 states have (on average 1.2258064516129032) internal successors, (38), 33 states have internal predecessors, (38), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-08 05:21:12,987 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 57 transitions. [2025-03-08 05:21:12,987 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 57 transitions. Word has length 36 [2025-03-08 05:21:12,988 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:12,988 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 57 transitions. [2025-03-08 05:21:12,988 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 5 states have internal predecessors, (18), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:21:12,988 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 57 transitions. [2025-03-08 05:21:12,988 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2025-03-08 05:21:12,988 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:12,988 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:21:13,001 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-08 05:21:13,189 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-08 05:21:13,189 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:13,189 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:13,189 INFO L85 PathProgramCache]: Analyzing trace with hash 266527358, now seen corresponding path program 2 times [2025-03-08 05:21:13,189 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:13,189 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1702606572] [2025-03-08 05:21:13,189 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:21:13,190 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:13,199 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 38 statements into 2 equivalence classes. [2025-03-08 05:21:13,236 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 38 of 38 statements. [2025-03-08 05:21:13,236 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:21:13,236 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:13,948 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 13 proven. 1 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-03-08 05:21:13,948 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:13,948 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1702606572] [2025-03-08 05:21:13,948 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1702606572] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:21:13,948 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [950053795] [2025-03-08 05:21:13,948 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:21:13,948 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:21:13,948 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:21:13,950 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-08 05:21:13,952 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-08 05:21:14,008 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 38 statements into 2 equivalence classes. [2025-03-08 05:21:14,031 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 38 of 38 statements. [2025-03-08 05:21:14,031 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:21:14,031 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:14,032 INFO L256 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 48 conjuncts are in the unsatisfiable core [2025-03-08 05:21:14,035 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:21:14,232 INFO L349 Elim1Store]: treesize reduction 29, result has 39.6 percent of original size [2025-03-08 05:21:14,233 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 1 case distinctions, treesize of input 38 treesize of output 19 [2025-03-08 05:21:14,511 INFO L349 Elim1Store]: treesize reduction 8, result has 82.2 percent of original size [2025-03-08 05:21:14,512 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 43 treesize of output 46 [2025-03-08 05:21:14,864 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-08 05:21:14,865 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:21:19,066 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-08 05:21:19,067 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 503 treesize of output 435 [2025-03-08 05:21:22,110 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-08 05:21:22,111 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [950053795] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:21:22,111 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:21:22,111 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 15, 15] total 37 [2025-03-08 05:21:22,111 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [29453387] [2025-03-08 05:21:22,111 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:21:22,112 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2025-03-08 05:21:22,112 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:22,112 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2025-03-08 05:21:22,113 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=133, Invalid=1198, Unknown=1, NotChecked=0, Total=1332 [2025-03-08 05:21:22,113 INFO L87 Difference]: Start difference. First operand 45 states and 57 transitions. Second operand has 37 states, 28 states have (on average 1.6428571428571428) internal successors, (46), 28 states have internal predecessors, (46), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-08 05:21:24,965 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:24,966 INFO L93 Difference]: Finished difference Result 91 states and 125 transitions. [2025-03-08 05:21:24,966 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2025-03-08 05:21:24,966 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 28 states have (on average 1.6428571428571428) internal successors, (46), 28 states have internal predecessors, (46), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 38 [2025-03-08 05:21:24,966 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:24,967 INFO L225 Difference]: With dead ends: 91 [2025-03-08 05:21:24,967 INFO L226 Difference]: Without dead ends: 62 [2025-03-08 05:21:24,968 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 57 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 415 ImplicationChecksByTransitivity, 7.6s TimeCoverageRelationStatistics Valid=318, Invalid=2131, Unknown=1, NotChecked=0, Total=2450 [2025-03-08 05:21:24,969 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 128 mSDsluCounter, 555 mSDsCounter, 0 mSdLazyCounter, 504 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 128 SdHoareTripleChecker+Valid, 586 SdHoareTripleChecker+Invalid, 529 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 504 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:24,969 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [128 Valid, 586 Invalid, 529 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 504 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-08 05:21:24,969 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2025-03-08 05:21:24,975 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 50. [2025-03-08 05:21:24,975 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 36 states have (on average 1.2777777777777777) internal successors, (46), 38 states have internal predecessors, (46), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-08 05:21:24,976 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 65 transitions. [2025-03-08 05:21:24,976 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 65 transitions. Word has length 38 [2025-03-08 05:21:24,976 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:24,976 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 65 transitions. [2025-03-08 05:21:24,976 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 37 states, 28 states have (on average 1.6428571428571428) internal successors, (46), 28 states have internal predecessors, (46), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-08 05:21:24,976 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 65 transitions. [2025-03-08 05:21:24,977 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2025-03-08 05:21:24,977 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:24,977 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 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] [2025-03-08 05:21:24,983 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-08 05:21:25,181 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-08 05:21:25,181 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:25,181 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:25,181 INFO L85 PathProgramCache]: Analyzing trace with hash 470473606, now seen corresponding path program 1 times [2025-03-08 05:21:25,181 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:25,181 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1572884856] [2025-03-08 05:21:25,182 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:25,182 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:25,191 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 41 statements into 1 equivalence classes. [2025-03-08 05:21:25,197 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 41 of 41 statements. [2025-03-08 05:21:25,198 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:25,198 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:25,409 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:21:25,409 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:25,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1572884856] [2025-03-08 05:21:25,409 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1572884856] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:21:25,409 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:21:25,409 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2025-03-08 05:21:25,409 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [659939412] [2025-03-08 05:21:25,409 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:21:25,410 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-08 05:21:25,410 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:25,410 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-08 05:21:25,410 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=90, Unknown=0, NotChecked=0, Total=110 [2025-03-08 05:21:25,411 INFO L87 Difference]: Start difference. First operand 50 states and 65 transitions. Second operand has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 10 states have internal predecessors, (21), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-08 05:21:25,570 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:25,570 INFO L93 Difference]: Finished difference Result 79 states and 103 transitions. [2025-03-08 05:21:25,571 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-08 05:21:25,571 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 10 states have internal predecessors, (21), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 41 [2025-03-08 05:21:25,571 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:25,572 INFO L225 Difference]: With dead ends: 79 [2025-03-08 05:21:25,572 INFO L226 Difference]: Without dead ends: 65 [2025-03-08 05:21:25,572 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2025-03-08 05:21:25,573 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 18 mSDsluCounter, 236 mSDsCounter, 0 mSdLazyCounter, 189 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 274 SdHoareTripleChecker+Invalid, 197 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 189 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:25,573 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 274 Invalid, 197 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 189 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:21:25,573 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2025-03-08 05:21:25,580 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 59. [2025-03-08 05:21:25,580 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 42 states have (on average 1.2380952380952381) internal successors, (52), 45 states have internal predecessors, (52), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (11), 9 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-08 05:21:25,580 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 75 transitions. [2025-03-08 05:21:25,581 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 75 transitions. Word has length 41 [2025-03-08 05:21:25,581 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:25,581 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 75 transitions. [2025-03-08 05:21:25,581 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 10 states have internal predecessors, (21), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-08 05:21:25,581 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 75 transitions. [2025-03-08 05:21:25,581 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2025-03-08 05:21:25,581 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:25,582 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:21:25,582 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2025-03-08 05:21:25,582 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:25,582 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:25,582 INFO L85 PathProgramCache]: Analyzing trace with hash 957819192, now seen corresponding path program 3 times [2025-03-08 05:21:25,582 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:25,582 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [815981181] [2025-03-08 05:21:25,582 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 05:21:25,582 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:25,590 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 42 statements into 4 equivalence classes. [2025-03-08 05:21:25,597 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 42 of 42 statements. [2025-03-08 05:21:25,598 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-08 05:21:25,598 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:25,633 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2025-03-08 05:21:25,633 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:25,633 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [815981181] [2025-03-08 05:21:25,634 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [815981181] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:21:25,634 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:21:25,634 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-08 05:21:25,634 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [325519811] [2025-03-08 05:21:25,634 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:21:25,634 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-08 05:21:25,634 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:25,634 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-08 05:21:25,635 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-08 05:21:25,635 INFO L87 Difference]: Start difference. First operand 59 states and 75 transitions. Second operand has 4 states, 4 states have (on average 5.5) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:21:25,659 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:25,659 INFO L93 Difference]: Finished difference Result 91 states and 118 transitions. [2025-03-08 05:21:25,659 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-08 05:21:25,659 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 5.5) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 42 [2025-03-08 05:21:25,660 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:25,660 INFO L225 Difference]: With dead ends: 91 [2025-03-08 05:21:25,660 INFO L226 Difference]: Without dead ends: 61 [2025-03-08 05:21:25,661 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-08 05:21:25,661 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 1 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:25,661 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 118 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:21:25,661 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2025-03-08 05:21:25,668 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 60. [2025-03-08 05:21:25,668 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 46 states have internal predecessors, (52), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (11), 9 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-08 05:21:25,669 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 75 transitions. [2025-03-08 05:21:25,670 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 75 transitions. Word has length 42 [2025-03-08 05:21:25,671 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:25,671 INFO L471 AbstractCegarLoop]: Abstraction has 60 states and 75 transitions. [2025-03-08 05:21:25,671 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 5.5) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:21:25,671 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 75 transitions. [2025-03-08 05:21:25,671 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2025-03-08 05:21:25,671 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:25,671 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:21:25,671 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2025-03-08 05:21:25,672 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:25,672 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:25,672 INFO L85 PathProgramCache]: Analyzing trace with hash -2029420711, now seen corresponding path program 4 times [2025-03-08 05:21:25,672 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:25,672 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [384487731] [2025-03-08 05:21:25,672 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 05:21:25,672 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:25,684 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 44 statements into 2 equivalence classes. [2025-03-08 05:21:25,698 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 44 of 44 statements. [2025-03-08 05:21:25,699 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-08 05:21:25,699 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:26,762 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 18 proven. 14 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-03-08 05:21:26,762 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:26,762 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [384487731] [2025-03-08 05:21:26,762 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [384487731] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:21:26,762 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2029541706] [2025-03-08 05:21:26,762 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 05:21:26,762 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:21:26,763 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:21:26,766 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-08 05:21:26,767 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-08 05:21:26,815 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 44 statements into 2 equivalence classes. [2025-03-08 05:21:26,838 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 44 of 44 statements. [2025-03-08 05:21:26,838 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-08 05:21:26,838 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:26,840 INFO L256 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 71 conjuncts are in the unsatisfiable core [2025-03-08 05:21:26,842 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:21:26,846 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 7 treesize of output 6 [2025-03-08 05:21:27,189 INFO L349 Elim1Store]: treesize reduction 41, result has 18.0 percent of original size [2025-03-08 05:21:27,190 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 43 treesize of output 45 [2025-03-08 05:21:27,998 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 67 treesize of output 49 [2025-03-08 05:21:28,121 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 24 proven. 16 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-03-08 05:21:28,121 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:21:28,633 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2029541706] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:21:28,633 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:21:28,633 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 19] total 34 [2025-03-08 05:21:28,633 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [225809654] [2025-03-08 05:21:28,633 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:21:28,634 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2025-03-08 05:21:28,634 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:28,634 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2025-03-08 05:21:28,635 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=188, Invalid=1792, Unknown=0, NotChecked=0, Total=1980 [2025-03-08 05:21:28,635 INFO L87 Difference]: Start difference. First operand 60 states and 75 transitions. Second operand has 34 states, 31 states have (on average 1.5161290322580645) internal successors, (47), 31 states have internal predecessors, (47), 6 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2025-03-08 05:21:30,748 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:30,748 INFO L93 Difference]: Finished difference Result 107 states and 139 transitions. [2025-03-08 05:21:30,749 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2025-03-08 05:21:30,749 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 31 states have (on average 1.5161290322580645) internal successors, (47), 31 states have internal predecessors, (47), 6 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) Word has length 44 [2025-03-08 05:21:30,749 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:30,750 INFO L225 Difference]: With dead ends: 107 [2025-03-08 05:21:30,750 INFO L226 Difference]: Without dead ends: 78 [2025-03-08 05:21:30,751 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 37 SyntacticMatches, 2 SemanticMatches, 62 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 886 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=487, Invalid=3545, Unknown=0, NotChecked=0, Total=4032 [2025-03-08 05:21:30,751 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 71 mSDsluCounter, 343 mSDsCounter, 0 mSdLazyCounter, 610 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 78 SdHoareTripleChecker+Valid, 379 SdHoareTripleChecker+Invalid, 622 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 610 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:30,752 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [78 Valid, 379 Invalid, 622 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 610 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-08 05:21:30,752 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2025-03-08 05:21:30,763 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 71. [2025-03-08 05:21:30,763 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 53 states have (on average 1.2264150943396226) internal successors, (65), 56 states have internal predecessors, (65), 12 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (11), 9 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-08 05:21:30,764 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 88 transitions. [2025-03-08 05:21:30,764 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 88 transitions. Word has length 44 [2025-03-08 05:21:30,764 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:30,764 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 88 transitions. [2025-03-08 05:21:30,764 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 31 states have (on average 1.5161290322580645) internal successors, (47), 31 states have internal predecessors, (47), 6 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2025-03-08 05:21:30,764 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 88 transitions. [2025-03-08 05:21:30,766 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2025-03-08 05:21:30,766 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:30,767 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:21:30,773 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-03-08 05:21:30,967 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-08 05:21:30,967 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:30,967 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:30,967 INFO L85 PathProgramCache]: Analyzing trace with hash 109382406, now seen corresponding path program 1 times [2025-03-08 05:21:30,968 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:30,968 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1883900726] [2025-03-08 05:21:30,968 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:30,968 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:30,974 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 48 statements into 1 equivalence classes. [2025-03-08 05:21:30,984 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 48 of 48 statements. [2025-03-08 05:21:30,984 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:30,984 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:31,183 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-03-08 05:21:31,183 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:31,183 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1883900726] [2025-03-08 05:21:31,183 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1883900726] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:21:31,183 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:21:31,184 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2025-03-08 05:21:31,184 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [614458505] [2025-03-08 05:21:31,184 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:21:31,184 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-08 05:21:31,184 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:31,185 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-08 05:21:31,185 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:21:31,185 INFO L87 Difference]: Start difference. First operand 71 states and 88 transitions. Second operand has 9 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 8 states have internal predecessors, (23), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2025-03-08 05:21:31,316 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:31,316 INFO L93 Difference]: Finished difference Result 88 states and 110 transitions. [2025-03-08 05:21:31,316 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-08 05:21:31,316 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 8 states have internal predecessors, (23), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 48 [2025-03-08 05:21:31,317 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:31,317 INFO L225 Difference]: With dead ends: 88 [2025-03-08 05:21:31,317 INFO L226 Difference]: Without dead ends: 86 [2025-03-08 05:21:31,317 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2025-03-08 05:21:31,318 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 10 mSDsluCounter, 210 mSDsCounter, 0 mSdLazyCounter, 162 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 162 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 162 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:31,318 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 249 Invalid, 162 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 162 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:21:31,318 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2025-03-08 05:21:31,337 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 81. [2025-03-08 05:21:31,337 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 60 states have (on average 1.2333333333333334) internal successors, (74), 63 states have internal predecessors, (74), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 11 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-08 05:21:31,340 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 101 transitions. [2025-03-08 05:21:31,341 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 101 transitions. Word has length 48 [2025-03-08 05:21:31,341 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:31,341 INFO L471 AbstractCegarLoop]: Abstraction has 81 states and 101 transitions. [2025-03-08 05:21:31,341 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 8 states have internal predecessors, (23), 4 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2025-03-08 05:21:31,341 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 101 transitions. [2025-03-08 05:21:31,342 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2025-03-08 05:21:31,342 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:31,342 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:21:31,342 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2025-03-08 05:21:31,342 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:31,342 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:31,342 INFO L85 PathProgramCache]: Analyzing trace with hash 110305927, now seen corresponding path program 1 times [2025-03-08 05:21:31,342 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:31,342 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [152918884] [2025-03-08 05:21:31,342 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:31,342 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:31,356 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 48 statements into 1 equivalence classes. [2025-03-08 05:21:31,366 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 48 of 48 statements. [2025-03-08 05:21:31,366 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:31,366 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:31,508 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-03-08 05:21:31,508 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:31,508 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [152918884] [2025-03-08 05:21:31,508 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [152918884] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:21:31,508 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:21:31,508 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-03-08 05:21:31,508 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [706242714] [2025-03-08 05:21:31,508 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:21:31,509 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-08 05:21:31,509 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:31,509 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-08 05:21:31,509 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2025-03-08 05:21:31,509 INFO L87 Difference]: Start difference. First operand 81 states and 101 transitions. Second operand has 6 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-08 05:21:31,565 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:31,565 INFO L93 Difference]: Finished difference Result 98 states and 122 transitions. [2025-03-08 05:21:31,565 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-08 05:21:31,565 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 48 [2025-03-08 05:21:31,566 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:31,566 INFO L225 Difference]: With dead ends: 98 [2025-03-08 05:21:31,566 INFO L226 Difference]: Without dead ends: 87 [2025-03-08 05:21:31,566 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2025-03-08 05:21:31,567 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 4 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:31,567 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 133 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:21:31,567 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2025-03-08 05:21:31,576 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 83. [2025-03-08 05:21:31,576 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 62 states have (on average 1.2258064516129032) internal successors, (76), 64 states have internal predecessors, (76), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-08 05:21:31,577 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 103 transitions. [2025-03-08 05:21:31,577 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 103 transitions. Word has length 48 [2025-03-08 05:21:31,577 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:31,577 INFO L471 AbstractCegarLoop]: Abstraction has 83 states and 103 transitions. [2025-03-08 05:21:31,578 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.8333333333333335) internal successors, (23), 6 states have internal predecessors, (23), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-08 05:21:31,578 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 103 transitions. [2025-03-08 05:21:31,578 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-03-08 05:21:31,578 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:31,578 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 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] [2025-03-08 05:21:31,578 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10 [2025-03-08 05:21:31,578 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:31,579 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:31,579 INFO L85 PathProgramCache]: Analyzing trace with hash -764261173, now seen corresponding path program 1 times [2025-03-08 05:21:31,579 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:31,579 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [154187010] [2025-03-08 05:21:31,579 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:31,579 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:31,585 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-08 05:21:31,590 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-08 05:21:31,590 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:31,590 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:31,771 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 5 proven. 2 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2025-03-08 05:21:31,772 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:31,772 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [154187010] [2025-03-08 05:21:31,772 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [154187010] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:21:31,772 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1797436233] [2025-03-08 05:21:31,772 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:31,772 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:21:31,772 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:21:31,774 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-08 05:21:31,777 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-08 05:21:31,827 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-08 05:21:31,850 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-08 05:21:31,851 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:31,851 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:31,855 INFO L256 TraceCheckSpWp]: Trace formula consists of 234 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-03-08 05:21:31,857 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:21:31,947 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-08 05:21:31,967 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2025-03-08 05:21:31,988 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 3 proven. 9 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:21:31,989 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:21:32,030 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 28 treesize of output 24 [2025-03-08 05:21:32,151 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:21:32,151 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1797436233] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:21:32,151 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:21:32,151 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 11, 11] total 20 [2025-03-08 05:21:32,151 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2089689347] [2025-03-08 05:21:32,151 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:21:32,152 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-08 05:21:32,152 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:32,152 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-08 05:21:32,152 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2025-03-08 05:21:32,152 INFO L87 Difference]: Start difference. First operand 83 states and 103 transitions. Second operand has 20 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 18 states have internal predecessors, (49), 4 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2025-03-08 05:21:32,415 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:32,416 INFO L93 Difference]: Finished difference Result 116 states and 147 transitions. [2025-03-08 05:21:32,416 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-08 05:21:32,416 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 18 states have internal predecessors, (49), 4 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 47 [2025-03-08 05:21:32,416 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:32,417 INFO L225 Difference]: With dead ends: 116 [2025-03-08 05:21:32,418 INFO L226 Difference]: Without dead ends: 97 [2025-03-08 05:21:32,418 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 81 SyntacticMatches, 2 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 148 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=152, Invalid=604, Unknown=0, NotChecked=0, Total=756 [2025-03-08 05:21:32,418 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 17 mSDsluCounter, 406 mSDsCounter, 0 mSdLazyCounter, 301 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 448 SdHoareTripleChecker+Invalid, 310 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 301 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:32,418 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 448 Invalid, 310 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 301 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 05:21:32,419 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2025-03-08 05:21:32,434 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 92. [2025-03-08 05:21:32,435 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 69 states have (on average 1.2318840579710144) internal successors, (85), 72 states have internal predecessors, (85), 15 states have call successors, (15), 7 states have call predecessors, (15), 7 states have return successors, (14), 12 states have call predecessors, (14), 14 states have call successors, (14) [2025-03-08 05:21:32,435 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 114 transitions. [2025-03-08 05:21:32,436 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 114 transitions. Word has length 47 [2025-03-08 05:21:32,436 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:32,436 INFO L471 AbstractCegarLoop]: Abstraction has 92 states and 114 transitions. [2025-03-08 05:21:32,436 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 18 states have internal predecessors, (49), 4 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2025-03-08 05:21:32,436 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 114 transitions. [2025-03-08 05:21:32,437 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-03-08 05:21:32,437 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:32,437 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 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] [2025-03-08 05:21:32,443 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-08 05:21:32,640 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:21:32,640 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:32,640 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:32,640 INFO L85 PathProgramCache]: Analyzing trace with hash -763337652, now seen corresponding path program 1 times [2025-03-08 05:21:32,640 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:32,640 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1481972172] [2025-03-08 05:21:32,641 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:32,641 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:32,647 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-08 05:21:32,655 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-08 05:21:32,655 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:32,655 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:32,744 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-03-08 05:21:32,744 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:32,744 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1481972172] [2025-03-08 05:21:32,745 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1481972172] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:21:32,745 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [605090839] [2025-03-08 05:21:32,745 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:32,745 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:21:32,745 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:21:32,747 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-08 05:21:32,748 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-08 05:21:32,802 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-08 05:21:32,823 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-08 05:21:32,823 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:32,823 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:32,824 INFO L256 TraceCheckSpWp]: Trace formula consists of 231 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-03-08 05:21:32,828 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:21:32,880 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-08 05:21:32,903 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-08 05:21:32,905 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-03-08 05:21:32,905 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:21:32,905 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [605090839] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:21:32,905 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:21:32,905 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [6] total 8 [2025-03-08 05:21:32,905 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [333548475] [2025-03-08 05:21:32,905 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:21:32,906 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-08 05:21:32,906 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:32,906 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-08 05:21:32,906 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2025-03-08 05:21:32,906 INFO L87 Difference]: Start difference. First operand 92 states and 114 transitions. Second operand has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 7 states have internal predecessors, (25), 3 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-08 05:21:36,933 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-08 05:21:37,007 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:37,007 INFO L93 Difference]: Finished difference Result 130 states and 154 transitions. [2025-03-08 05:21:37,008 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-08 05:21:37,008 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 7 states have internal predecessors, (25), 3 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 47 [2025-03-08 05:21:37,008 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:37,009 INFO L225 Difference]: With dead ends: 130 [2025-03-08 05:21:37,009 INFO L226 Difference]: Without dead ends: 111 [2025-03-08 05:21:37,009 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 45 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:21:37,009 INFO L435 NwaCegarLoop]: 55 mSDtfsCounter, 20 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 78 mSolverCounterSat, 3 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 82 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 78 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:37,009 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 193 Invalid, 82 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 78 Invalid, 1 Unknown, 0 Unchecked, 4.1s Time] [2025-03-08 05:21:37,010 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2025-03-08 05:21:37,020 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 109. [2025-03-08 05:21:37,021 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 80 states have (on average 1.2) internal successors, (96), 84 states have internal predecessors, (96), 18 states have call successors, (18), 10 states have call predecessors, (18), 10 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-08 05:21:37,021 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 130 transitions. [2025-03-08 05:21:37,022 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 130 transitions. Word has length 47 [2025-03-08 05:21:37,022 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:37,022 INFO L471 AbstractCegarLoop]: Abstraction has 109 states and 130 transitions. [2025-03-08 05:21:37,022 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 7 states have internal predecessors, (25), 3 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-08 05:21:37,022 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 130 transitions. [2025-03-08 05:21:37,022 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-08 05:21:37,023 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:37,023 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:21:37,029 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-08 05:21:37,223 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:21:37,223 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:37,224 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:37,224 INFO L85 PathProgramCache]: Analyzing trace with hash 151576953, now seen corresponding path program 1 times [2025-03-08 05:21:37,224 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:37,224 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [404658229] [2025-03-08 05:21:37,224 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:37,224 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:37,231 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-08 05:21:37,235 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-08 05:21:37,236 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:37,236 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:37,506 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-03-08 05:21:37,506 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:37,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [404658229] [2025-03-08 05:21:37,506 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [404658229] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:21:37,506 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:21:37,506 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2025-03-08 05:21:37,507 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [23792622] [2025-03-08 05:21:37,507 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:21:37,507 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-08 05:21:37,507 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:37,507 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-08 05:21:37,507 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:21:37,507 INFO L87 Difference]: Start difference. First operand 109 states and 130 transitions. Second operand has 9 states, 8 states have (on average 3.0) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-03-08 05:21:37,614 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:37,614 INFO L93 Difference]: Finished difference Result 118 states and 139 transitions. [2025-03-08 05:21:37,614 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-08 05:21:37,614 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 3.0) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 54 [2025-03-08 05:21:37,615 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:37,615 INFO L225 Difference]: With dead ends: 118 [2025-03-08 05:21:37,615 INFO L226 Difference]: Without dead ends: 116 [2025-03-08 05:21:37,616 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-03-08 05:21:37,616 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 6 mSDsluCounter, 212 mSDsCounter, 0 mSdLazyCounter, 140 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 247 SdHoareTripleChecker+Invalid, 143 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 140 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:37,616 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 247 Invalid, 143 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 140 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:21:37,616 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2025-03-08 05:21:37,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 115. [2025-03-08 05:21:37,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 84 states have (on average 1.1904761904761905) internal successors, (100), 88 states have internal predecessors, (100), 19 states have call successors, (19), 11 states have call predecessors, (19), 11 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2025-03-08 05:21:37,636 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 136 transitions. [2025-03-08 05:21:37,637 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 136 transitions. Word has length 54 [2025-03-08 05:21:37,637 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:37,637 INFO L471 AbstractCegarLoop]: Abstraction has 115 states and 136 transitions. [2025-03-08 05:21:37,637 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 3.0) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-03-08 05:21:37,637 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 136 transitions. [2025-03-08 05:21:37,638 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-08 05:21:37,638 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:37,638 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 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, 1, 1, 1, 1] [2025-03-08 05:21:37,638 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13 [2025-03-08 05:21:37,638 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:37,639 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:37,639 INFO L85 PathProgramCache]: Analyzing trace with hash 46901666, now seen corresponding path program 1 times [2025-03-08 05:21:37,639 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:37,639 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [728096157] [2025-03-08 05:21:37,639 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:37,639 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:37,646 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-08 05:21:37,650 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-08 05:21:37,651 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:37,651 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:37,773 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2025-03-08 05:21:37,773 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:37,774 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [728096157] [2025-03-08 05:21:37,774 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [728096157] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:21:37,774 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [900393128] [2025-03-08 05:21:37,774 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:21:37,774 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:21:37,774 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:21:37,776 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-08 05:21:37,777 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-08 05:21:37,854 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-08 05:21:37,881 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-08 05:21:37,882 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:21:37,882 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:37,883 INFO L256 TraceCheckSpWp]: Trace formula consists of 247 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-03-08 05:21:37,885 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:21:37,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 15 treesize of output 1 [2025-03-08 05:21:37,970 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-08 05:21:37,972 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 5 proven. 5 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2025-03-08 05:21:37,972 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:21:37,996 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 32 treesize of output 28 [2025-03-08 05:21:38,065 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 5 proven. 5 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2025-03-08 05:21:38,066 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [900393128] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:21:38,066 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:21:38,066 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8, 7] total 13 [2025-03-08 05:21:38,066 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1149750245] [2025-03-08 05:21:38,066 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:21:38,066 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-08 05:21:38,066 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:38,066 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-08 05:21:38,067 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=121, Unknown=0, NotChecked=0, Total=156 [2025-03-08 05:21:38,067 INFO L87 Difference]: Start difference. First operand 115 states and 136 transitions. Second operand has 13 states, 13 states have (on average 3.6153846153846154) internal successors, (47), 13 states have internal predecessors, (47), 4 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2025-03-08 05:21:42,096 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-08 05:21:42,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:21:42,259 INFO L93 Difference]: Finished difference Result 128 states and 148 transitions. [2025-03-08 05:21:42,259 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-08 05:21:42,260 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 3.6153846153846154) internal successors, (47), 13 states have internal predecessors, (47), 4 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 54 [2025-03-08 05:21:42,260 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:21:42,260 INFO L225 Difference]: With dead ends: 128 [2025-03-08 05:21:42,260 INFO L226 Difference]: Without dead ends: 117 [2025-03-08 05:21:42,261 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 99 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=61, Invalid=211, Unknown=0, NotChecked=0, Total=272 [2025-03-08 05:21:42,261 INFO L435 NwaCegarLoop]: 49 mSDtfsCounter, 18 mSDsluCounter, 356 mSDsCounter, 0 mSdLazyCounter, 244 mSolverCounterSat, 4 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 405 SdHoareTripleChecker+Invalid, 249 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 244 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:21:42,261 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 405 Invalid, 249 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 244 Invalid, 1 Unknown, 0 Unchecked, 4.1s Time] [2025-03-08 05:21:42,261 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2025-03-08 05:21:42,272 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 114. [2025-03-08 05:21:42,273 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 114 states, 84 states have (on average 1.1785714285714286) internal successors, (99), 87 states have internal predecessors, (99), 18 states have call successors, (18), 11 states have call predecessors, (18), 11 states have return successors, (16), 15 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-08 05:21:42,273 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 133 transitions. [2025-03-08 05:21:42,274 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 133 transitions. Word has length 54 [2025-03-08 05:21:42,274 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:21:42,274 INFO L471 AbstractCegarLoop]: Abstraction has 114 states and 133 transitions. [2025-03-08 05:21:42,274 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 3.6153846153846154) internal successors, (47), 13 states have internal predecessors, (47), 4 states have call successors, (11), 3 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2025-03-08 05:21:42,274 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 133 transitions. [2025-03-08 05:21:42,274 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2025-03-08 05:21:42,275 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:21:42,275 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:21:42,281 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-08 05:21:42,475 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,SelfDestructingSolverStorable14 [2025-03-08 05:21:42,475 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:21:42,476 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:21:42,476 INFO L85 PathProgramCache]: Analyzing trace with hash -1606025451, now seen corresponding path program 5 times [2025-03-08 05:21:42,476 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:21:42,476 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1618656416] [2025-03-08 05:21:42,476 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-08 05:21:42,476 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:21:42,482 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 52 statements into 9 equivalence classes. [2025-03-08 05:21:42,503 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) and asserted 52 of 52 statements. [2025-03-08 05:21:42,503 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2025-03-08 05:21:42,503 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:44,801 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 43 proven. 30 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2025-03-08 05:21:44,802 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:21:44,802 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1618656416] [2025-03-08 05:21:44,802 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1618656416] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:21:44,802 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [57327918] [2025-03-08 05:21:44,802 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-08 05:21:44,802 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:21:44,802 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:21:44,804 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-08 05:21:44,806 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-08 05:21:44,863 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 52 statements into 9 equivalence classes. [2025-03-08 05:21:44,890 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) and asserted 52 of 52 statements. [2025-03-08 05:21:44,890 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2025-03-08 05:21:44,890 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:21:44,892 INFO L256 TraceCheckSpWp]: Trace formula consists of 251 conjuncts, 81 conjuncts are in the unsatisfiable core [2025-03-08 05:21:44,894 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:21:44,897 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 7 treesize of output 6 [2025-03-08 05:21:45,291 INFO L349 Elim1Store]: treesize reduction 49, result has 15.5 percent of original size [2025-03-08 05:21:45,291 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 51 treesize of output 53 [2025-03-08 05:21:46,213 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 57 proven. 17 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2025-03-08 05:21:46,213 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:21:48,005 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [57327918] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:21:48,005 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:21:48,005 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 19] total 37 [2025-03-08 05:21:48,005 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1875424558] [2025-03-08 05:21:48,005 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:21:48,006 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2025-03-08 05:21:48,006 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:21:48,006 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2025-03-08 05:21:48,007 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=364, Invalid=2716, Unknown=0, NotChecked=0, Total=3080 [2025-03-08 05:21:48,007 INFO L87 Difference]: Start difference. First operand 114 states and 133 transitions. Second operand has 37 states, 35 states have (on average 1.5714285714285714) internal successors, (55), 35 states have internal predecessors, (55), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 3 states have call successors, (7) [2025-03-08 05:22:00,573 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-08 05:22:00,609 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:22:00,609 INFO L93 Difference]: Finished difference Result 186 states and 228 transitions. [2025-03-08 05:22:00,609 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2025-03-08 05:22:00,609 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 35 states have (on average 1.5714285714285714) internal successors, (55), 35 states have internal predecessors, (55), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 3 states have call successors, (7) Word has length 52 [2025-03-08 05:22:00,610 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:22:00,610 INFO L225 Difference]: With dead ends: 186 [2025-03-08 05:22:00,610 INFO L226 Difference]: Without dead ends: 130 [2025-03-08 05:22:00,612 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 44 SyntacticMatches, 4 SemanticMatches, 83 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1838 ImplicationChecksByTransitivity, 10.7s TimeCoverageRelationStatistics Valid=1098, Invalid=6042, Unknown=0, NotChecked=0, Total=7140 [2025-03-08 05:22:00,613 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 152 mSDsluCounter, 398 mSDsCounter, 0 mSdLazyCounter, 818 mSolverCounterSat, 16 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 156 SdHoareTripleChecker+Valid, 432 SdHoareTripleChecker+Invalid, 835 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 818 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.3s IncrementalHoareTripleChecker+Time [2025-03-08 05:22:00,613 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [156 Valid, 432 Invalid, 835 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 818 Invalid, 1 Unknown, 0 Unchecked, 5.3s Time] [2025-03-08 05:22:00,614 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2025-03-08 05:22:00,636 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 124. [2025-03-08 05:22:00,637 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 94 states have (on average 1.2340425531914894) internal successors, (116), 97 states have internal predecessors, (116), 18 states have call successors, (18), 11 states have call predecessors, (18), 11 states have return successors, (16), 15 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-08 05:22:00,638 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 150 transitions. [2025-03-08 05:22:00,638 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 150 transitions. Word has length 52 [2025-03-08 05:22:00,638 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:22:00,638 INFO L471 AbstractCegarLoop]: Abstraction has 124 states and 150 transitions. [2025-03-08 05:22:00,638 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 37 states, 35 states have (on average 1.5714285714285714) internal successors, (55), 35 states have internal predecessors, (55), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 3 states have call successors, (7) [2025-03-08 05:22:00,638 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 150 transitions. [2025-03-08 05:22:00,639 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2025-03-08 05:22:00,639 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:22:00,639 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:22:00,646 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-03-08 05:22:00,839 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,SelfDestructingSolverStorable15 [2025-03-08 05:22:00,840 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:22:00,840 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:22:00,840 INFO L85 PathProgramCache]: Analyzing trace with hash 314182830, now seen corresponding path program 1 times [2025-03-08 05:22:00,840 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:22:00,841 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1947795289] [2025-03-08 05:22:00,841 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:22:00,841 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:22:00,849 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 60 statements into 1 equivalence classes. [2025-03-08 05:22:00,859 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 60 of 60 statements. [2025-03-08 05:22:00,860 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:22:00,860 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:22:01,595 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-08 05:22:01,596 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:22:01,596 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1947795289] [2025-03-08 05:22:01,596 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1947795289] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:22:01,596 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:22:01,596 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2025-03-08 05:22:01,596 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1051267217] [2025-03-08 05:22:01,596 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:22:01,597 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-08 05:22:01,597 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:22:01,597 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-08 05:22:01,597 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=108, Unknown=0, NotChecked=0, Total=132 [2025-03-08 05:22:01,597 INFO L87 Difference]: Start difference. First operand 124 states and 150 transitions. Second operand has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2025-03-08 05:22:01,922 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:22:01,922 INFO L93 Difference]: Finished difference Result 132 states and 157 transitions. [2025-03-08 05:22:01,922 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-08 05:22:01,922 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 60 [2025-03-08 05:22:01,923 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:22:01,923 INFO L225 Difference]: With dead ends: 132 [2025-03-08 05:22:01,923 INFO L226 Difference]: Without dead ends: 98 [2025-03-08 05:22:01,923 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=38, Invalid=172, Unknown=0, NotChecked=0, Total=210 [2025-03-08 05:22:01,924 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 28 mSDsluCounter, 207 mSDsCounter, 0 mSdLazyCounter, 264 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 240 SdHoareTripleChecker+Invalid, 268 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 264 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 05:22:01,924 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 240 Invalid, 268 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 264 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 05:22:01,924 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2025-03-08 05:22:01,942 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 98. [2025-03-08 05:22:01,942 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 76 states have (on average 1.236842105263158) internal successors, (94), 78 states have internal predecessors, (94), 14 states have call successors, (14), 7 states have call predecessors, (14), 7 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2025-03-08 05:22:01,943 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 120 transitions. [2025-03-08 05:22:01,943 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 120 transitions. Word has length 60 [2025-03-08 05:22:01,943 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:22:01,943 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 120 transitions. [2025-03-08 05:22:01,943 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2025-03-08 05:22:01,943 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 120 transitions. [2025-03-08 05:22:01,944 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2025-03-08 05:22:01,944 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:22:01,944 INFO L218 NwaCegarLoop]: trace histogram [8, 8, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:22:01,944 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16 [2025-03-08 05:22:01,944 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:22:01,944 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:22:01,945 INFO L85 PathProgramCache]: Analyzing trace with hash -728098153, now seen corresponding path program 6 times [2025-03-08 05:22:01,945 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:22:01,945 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1436382370] [2025-03-08 05:22:01,945 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-08 05:22:01,945 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:22:01,955 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 56 statements into 11 equivalence classes. [2025-03-08 05:22:01,985 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) and asserted 54 of 56 statements. [2025-03-08 05:22:01,986 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) [2025-03-08 05:22:01,986 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:22:05,469 INFO L134 CoverageAnalysis]: Checked inductivity of 128 backedges. 9 proven. 101 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-08 05:22:05,469 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:22:05,469 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1436382370] [2025-03-08 05:22:05,469 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1436382370] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:22:05,469 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [969798896] [2025-03-08 05:22:05,469 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-08 05:22:05,469 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:22:05,469 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:22:05,472 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-08 05:22:05,472 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-08 05:22:05,534 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 56 statements into 11 equivalence classes. [2025-03-08 05:22:05,572 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) and asserted 54 of 56 statements. [2025-03-08 05:22:05,572 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) [2025-03-08 05:22:05,572 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:22:05,573 INFO L256 TraceCheckSpWp]: Trace formula consists of 259 conjuncts, 78 conjuncts are in the unsatisfiable core [2025-03-08 05:22:05,576 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:22:05,580 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 7 treesize of output 6 [2025-03-08 05:22:05,883 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 45 treesize of output 40 [2025-03-08 05:22:11,221 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 103 treesize of output 77 [2025-03-08 05:22:11,327 INFO L134 CoverageAnalysis]: Checked inductivity of 128 backedges. 43 proven. 66 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2025-03-08 05:22:11,327 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:22:12,751 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [969798896] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:22:12,751 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:22:12,751 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 21] total 46 [2025-03-08 05:22:12,751 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [408137808] [2025-03-08 05:22:12,751 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:22:12,753 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2025-03-08 05:22:12,753 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:22:12,753 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2025-03-08 05:22:12,754 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=503, Invalid=3656, Unknown=1, NotChecked=0, Total=4160 [2025-03-08 05:22:12,754 INFO L87 Difference]: Start difference. First operand 98 states and 120 transitions. Second operand has 46 states, 45 states have (on average 1.511111111111111) internal successors, (68), 45 states have internal predecessors, (68), 4 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2025-03-08 05:22:17,598 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-08 05:22:20,417 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:22:20,417 INFO L93 Difference]: Finished difference Result 138 states and 164 transitions. [2025-03-08 05:22:20,418 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2025-03-08 05:22:20,418 INFO L78 Accepts]: Start accepts. Automaton has has 46 states, 45 states have (on average 1.511111111111111) internal successors, (68), 45 states have internal predecessors, (68), 4 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) Word has length 56 [2025-03-08 05:22:20,418 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:22:20,419 INFO L225 Difference]: With dead ends: 138 [2025-03-08 05:22:20,419 INFO L226 Difference]: Without dead ends: 75 [2025-03-08 05:22:20,420 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 50 SyntacticMatches, 5 SemanticMatches, 86 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2222 ImplicationChecksByTransitivity, 9.7s TimeCoverageRelationStatistics Valid=1137, Invalid=6518, Unknown=1, NotChecked=0, Total=7656 [2025-03-08 05:22:20,420 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 87 mSDsluCounter, 402 mSDsCounter, 0 mSdLazyCounter, 851 mSolverCounterSat, 15 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 91 SdHoareTripleChecker+Valid, 434 SdHoareTripleChecker+Invalid, 867 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 851 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.4s IncrementalHoareTripleChecker+Time [2025-03-08 05:22:20,420 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [91 Valid, 434 Invalid, 867 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 851 Invalid, 1 Unknown, 0 Unchecked, 5.4s Time] [2025-03-08 05:22:20,421 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2025-03-08 05:22:20,435 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 69. [2025-03-08 05:22:20,436 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 53 states have (on average 1.150943396226415) internal successors, (61), 54 states have internal predecessors, (61), 9 states have call successors, (9), 6 states have call predecessors, (9), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-08 05:22:20,436 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 78 transitions. [2025-03-08 05:22:20,436 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 78 transitions. Word has length 56 [2025-03-08 05:22:20,436 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:22:20,436 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 78 transitions. [2025-03-08 05:22:20,437 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 46 states, 45 states have (on average 1.511111111111111) internal successors, (68), 45 states have internal predecessors, (68), 4 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2025-03-08 05:22:20,437 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 78 transitions. [2025-03-08 05:22:20,437 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2025-03-08 05:22:20,437 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:22:20,437 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:22:20,444 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-03-08 05:22:20,637 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,SelfDestructingSolverStorable17 [2025-03-08 05:22:20,638 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:22:20,638 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:22:20,638 INFO L85 PathProgramCache]: Analyzing trace with hash -121083820, now seen corresponding path program 1 times [2025-03-08 05:22:20,638 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:22:20,638 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1395453588] [2025-03-08 05:22:20,638 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:22:20,638 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:22:20,645 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 60 statements into 1 equivalence classes. [2025-03-08 05:22:20,649 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 60 of 60 statements. [2025-03-08 05:22:20,649 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:22:20,649 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:22:20,823 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2025-03-08 05:22:20,823 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:22:20,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1395453588] [2025-03-08 05:22:20,823 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1395453588] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:22:20,823 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:22:20,823 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2025-03-08 05:22:20,824 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1222215279] [2025-03-08 05:22:20,824 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:22:20,824 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-08 05:22:20,824 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:22:20,824 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-08 05:22:20,824 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:22:20,825 INFO L87 Difference]: Start difference. First operand 69 states and 78 transitions. Second operand has 9 states, 8 states have (on average 3.5) internal successors, (28), 8 states have internal predecessors, (28), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-03-08 05:22:20,937 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:22:20,937 INFO L93 Difference]: Finished difference Result 75 states and 83 transitions. [2025-03-08 05:22:20,937 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-08 05:22:20,938 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 3.5) internal successors, (28), 8 states have internal predecessors, (28), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 60 [2025-03-08 05:22:20,938 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:22:20,938 INFO L225 Difference]: With dead ends: 75 [2025-03-08 05:22:20,938 INFO L226 Difference]: Without dead ends: 71 [2025-03-08 05:22:20,939 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-03-08 05:22:20,939 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 8 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 100 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:22:20,939 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 193 Invalid, 100 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:22:20,939 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2025-03-08 05:22:20,953 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2025-03-08 05:22:20,953 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 55 states have (on average 1.1272727272727272) internal successors, (62), 55 states have internal predecessors, (62), 9 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-08 05:22:20,953 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 79 transitions. [2025-03-08 05:22:20,954 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 79 transitions. Word has length 60 [2025-03-08 05:22:20,954 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:22:20,954 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 79 transitions. [2025-03-08 05:22:20,954 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 3.5) internal successors, (28), 8 states have internal predecessors, (28), 4 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2025-03-08 05:22:20,954 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 79 transitions. [2025-03-08 05:22:20,954 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2025-03-08 05:22:20,954 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:22:20,955 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:22:20,955 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18 [2025-03-08 05:22:20,955 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:22:20,955 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:22:20,955 INFO L85 PathProgramCache]: Analyzing trace with hash -1154366647, now seen corresponding path program 1 times [2025-03-08 05:22:20,955 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:22:20,955 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [25174537] [2025-03-08 05:22:20,955 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:22:20,956 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:22:20,964 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 66 statements into 1 equivalence classes. [2025-03-08 05:22:20,974 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 66 of 66 statements. [2025-03-08 05:22:20,974 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:22:20,974 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:22:24,564 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 9 proven. 9 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-08 05:22:24,564 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:22:24,564 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [25174537] [2025-03-08 05:22:24,564 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [25174537] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:22:24,564 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1303555091] [2025-03-08 05:22:24,564 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:22:24,564 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:22:24,565 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:22:24,566 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-08 05:22:24,567 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-08 05:22:24,629 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 66 statements into 1 equivalence classes. [2025-03-08 05:22:24,653 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 66 of 66 statements. [2025-03-08 05:22:24,653 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:22:24,653 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:22:24,656 INFO L256 TraceCheckSpWp]: Trace formula consists of 280 conjuncts, 105 conjuncts are in the unsatisfiable core [2025-03-08 05:22:24,659 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:22:24,662 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 7 treesize of output 6 [2025-03-08 05:22:25,230 INFO L349 Elim1Store]: treesize reduction 49, result has 15.5 percent of original size [2025-03-08 05:22:25,231 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 51 treesize of output 53 [2025-03-08 05:22:26,509 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-08 05:22:26,539 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-08 05:22:28,818 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 84 treesize of output 66 [2025-03-08 05:22:29,081 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 12 proven. 18 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-03-08 05:22:29,081 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:22:29,278 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 84 treesize of output 80 [2025-03-08 05:22:29,280 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 138 treesize of output 130 [2025-03-08 05:22:32,196 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 8 proven. 10 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-08 05:22:32,197 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1303555091] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:22:32,197 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:22:32,197 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 24, 14] total 49 [2025-03-08 05:22:32,197 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1669178199] [2025-03-08 05:22:32,197 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:22:32,197 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 49 states [2025-03-08 05:22:32,197 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:22:32,198 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2025-03-08 05:22:32,198 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=243, Invalid=2109, Unknown=0, NotChecked=0, Total=2352 [2025-03-08 05:22:32,198 INFO L87 Difference]: Start difference. First operand 71 states and 79 transitions. Second operand has 49 states, 43 states have (on average 1.8372093023255813) internal successors, (79), 42 states have internal predecessors, (79), 11 states have call successors, (25), 5 states have call predecessors, (25), 3 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22)