./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/hard-u_valuebound1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 798a7b37 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/hard-u_valuebound1.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 2205701c87619eed0a8a76ebf684289d4e97e42556aa5e531d0e97f394ad4619 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 14:01:15,667 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 14:01:15,715 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-03 14:01:15,722 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 14:01:15,722 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 14:01:15,746 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 14:01:15,747 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 14:01:15,747 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 14:01:15,747 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 14:01:15,747 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 14:01:15,748 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 14:01:15,748 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 14:01:15,748 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 14:01:15,748 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 14:01:15,748 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 14:01:15,748 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 14:01:15,748 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 14:01:15,748 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 14:01:15,748 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 14:01:15,748 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 14:01:15,749 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 14:01:15,749 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 14:01:15,749 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 14:01:15,749 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 14:01:15,749 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 14:01:15,749 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 14:01:15,749 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 14:01:15,749 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 14:01:15,749 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 14:01:15,749 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 14:01:15,750 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 14:01:15,750 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 14:01:15,750 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:01:15,750 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 14:01:15,750 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 14:01:15,750 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 14:01:15,750 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 14:01:15,750 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 14:01:15,750 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 14:01:15,750 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 14:01:15,750 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 14:01:15,750 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 14:01:15,751 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 14:01:15,751 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 -> 2205701c87619eed0a8a76ebf684289d4e97e42556aa5e531d0e97f394ad4619 [2025-03-03 14:01:15,995 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 14:01:16,005 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 14:01:16,007 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 14:01:16,008 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 14:01:16,008 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 14:01:16,009 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/hard-u_valuebound1.c [2025-03-03 14:01:17,146 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4bcb99014/1068022dac92457b92f017ed7ccc92c0/FLAGfedbe4a53 [2025-03-03 14:01:17,351 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 14:01:17,351 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard-u_valuebound1.c [2025-03-03 14:01:17,356 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4bcb99014/1068022dac92457b92f017ed7ccc92c0/FLAGfedbe4a53 [2025-03-03 14:01:17,706 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4bcb99014/1068022dac92457b92f017ed7ccc92c0 [2025-03-03 14:01:17,708 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 14:01:17,709 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 14:01:17,709 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 14:01:17,710 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 14:01:17,712 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 14:01:17,713 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,713 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@59ade09f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17, skipping insertion in model container [2025-03-03 14:01:17,713 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,722 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 14:01:17,819 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/nla-digbench-scaling/hard-u_valuebound1.c[537,550] [2025-03-03 14:01:17,833 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:01:17,840 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 14:01:17,848 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/nla-digbench-scaling/hard-u_valuebound1.c[537,550] [2025-03-03 14:01:17,855 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:01:17,867 INFO L204 MainTranslator]: Completed translation [2025-03-03 14:01:17,868 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17 WrapperNode [2025-03-03 14:01:17,869 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 14:01:17,870 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 14:01:17,870 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 14:01:17,870 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 14:01:17,874 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,879 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,891 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 50 [2025-03-03 14:01:17,891 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 14:01:17,892 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 14:01:17,893 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 14:01:17,893 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 14:01:17,898 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,898 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,899 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,905 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2025-03-03 14:01:17,906 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,906 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,908 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,910 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,911 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,911 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,912 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 14:01:17,912 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 14:01:17,912 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 14:01:17,912 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 14:01:17,913 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17" (1/1) ... [2025-03-03 14:01:17,916 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:01:17,924 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:01:17,934 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-03 14:01:17,938 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-03 14:01:17,954 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 14:01:17,954 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-03 14:01:17,954 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-03 14:01:17,954 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 14:01:17,954 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 14:01:17,954 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 14:01:17,955 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-03 14:01:17,955 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-03 14:01:17,994 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 14:01:17,995 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 14:01:18,124 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2025-03-03 14:01:18,124 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 14:01:18,129 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 14:01:18,129 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 14:01:18,130 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:01:18 BoogieIcfgContainer [2025-03-03 14:01:18,130 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 14:01:18,132 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 14:01:18,132 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 14:01:18,135 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 14:01:18,135 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 02:01:17" (1/3) ... [2025-03-03 14:01:18,136 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5998ac34 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:01:18, skipping insertion in model container [2025-03-03 14:01:18,136 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:01:17" (2/3) ... [2025-03-03 14:01:18,136 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5998ac34 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:01:18, skipping insertion in model container [2025-03-03 14:01:18,136 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:01:18" (3/3) ... [2025-03-03 14:01:18,137 INFO L128 eAbstractionObserver]: Analyzing ICFG hard-u_valuebound1.c [2025-03-03 14:01:18,147 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 14:01:18,148 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG hard-u_valuebound1.c that has 3 procedures, 31 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-03 14:01:18,189 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 14:01:18,196 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;@1e22bbe0, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 14:01:18,197 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-03 14:01:18,203 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 18 states have internal predecessors, (25), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-03-03 14:01:18,207 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-03 14:01:18,208 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:01:18,208 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:01:18,208 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:01:18,213 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:01:18,213 INFO L85 PathProgramCache]: Analyzing trace with hash -1866426684, now seen corresponding path program 1 times [2025-03-03 14:01:18,218 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:01:18,218 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [443998415] [2025-03-03 14:01:18,219 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:18,220 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:01:18,268 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-03 14:01:18,279 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-03 14:01:18,279 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:18,279 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:01:18,311 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-03-03 14:01:18,311 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:01:18,311 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [443998415] [2025-03-03 14:01:18,312 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [443998415] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:01:18,312 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [393601012] [2025-03-03 14:01:18,312 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:18,312 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:01:18,312 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:01:18,315 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:01:18,316 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-03 14:01:18,351 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-03 14:01:18,367 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-03 14:01:18,367 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:18,368 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:01:18,369 INFO L256 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-03 14:01:18,371 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:01:18,378 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-03-03 14:01:18,378 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 14:01:18,378 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [393601012] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:01:18,378 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:01:18,378 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-03 14:01:18,380 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [794594403] [2025-03-03 14:01:18,380 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:01:18,382 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-03 14:01:18,382 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:01:18,393 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-03 14:01:18,394 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-03 14:01:18,395 INFO L87 Difference]: Start difference. First operand has 31 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 18 states have internal predecessors, (25), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-03 14:01:18,405 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:01:18,406 INFO L93 Difference]: Finished difference Result 59 states and 96 transitions. [2025-03-03 14:01:18,406 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-03 14:01:18,407 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2025-03-03 14:01:18,407 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:01:18,411 INFO L225 Difference]: With dead ends: 59 [2025-03-03 14:01:18,411 INFO L226 Difference]: Without dead ends: 27 [2025-03-03 14:01:18,413 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 24 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-03 14:01:18,414 INFO L435 NwaCegarLoop]: 41 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, 41 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-03 14:01:18,415 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:01:18,425 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2025-03-03 14:01:18,433 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2025-03-03 14:01:18,434 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 15 states have internal predecessors, (18), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-03 14:01:18,436 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 37 transitions. [2025-03-03 14:01:18,440 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 37 transitions. Word has length 23 [2025-03-03 14:01:18,440 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:01:18,440 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 37 transitions. [2025-03-03 14:01:18,440 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-03 14:01:18,440 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 37 transitions. [2025-03-03 14:01:18,441 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-03 14:01:18,441 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:01:18,441 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:01:18,447 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-03 14:01:18,642 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-03 14:01:18,642 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:01:18,642 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:01:18,642 INFO L85 PathProgramCache]: Analyzing trace with hash -1261491227, now seen corresponding path program 1 times [2025-03-03 14:01:18,642 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:01:18,642 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1322757456] [2025-03-03 14:01:18,643 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:18,643 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:01:18,647 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-03 14:01:18,657 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-03 14:01:18,657 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:18,657 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:01:18,824 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 14:01:18,824 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:01:18,824 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1322757456] [2025-03-03 14:01:18,824 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1322757456] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:01:18,824 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:01:18,824 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 14:01:18,824 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1248148727] [2025-03-03 14:01:18,824 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:01:18,825 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 14:01:18,825 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:01:18,825 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 14:01:18,825 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 14:01:18,826 INFO L87 Difference]: Start difference. First operand 27 states and 37 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2025-03-03 14:01:18,880 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:01:18,880 INFO L93 Difference]: Finished difference Result 39 states and 53 transitions. [2025-03-03 14:01:18,881 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 14:01:18,882 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 23 [2025-03-03 14:01:18,882 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:01:18,883 INFO L225 Difference]: With dead ends: 39 [2025-03-03 14:01:18,883 INFO L226 Difference]: Without dead ends: 37 [2025-03-03 14:01:18,883 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-03 14:01:18,884 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 8 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:01:18,885 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 119 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:01:18,885 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2025-03-03 14:01:18,891 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 31. [2025-03-03 14:01:18,892 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-03 14:01:18,893 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 40 transitions. [2025-03-03 14:01:18,893 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 40 transitions. Word has length 23 [2025-03-03 14:01:18,893 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:01:18,893 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 40 transitions. [2025-03-03 14:01:18,893 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2025-03-03 14:01:18,893 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 40 transitions. [2025-03-03 14:01:18,893 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-03 14:01:18,893 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:01:18,893 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:01:18,894 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-03 14:01:18,894 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:01:18,894 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:01:18,895 INFO L85 PathProgramCache]: Analyzing trace with hash 443892832, now seen corresponding path program 1 times [2025-03-03 14:01:18,895 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:01:18,895 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1624238937] [2025-03-03 14:01:18,895 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:18,895 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:01:18,902 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 14:01:18,921 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 14:01:18,921 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:18,922 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:01:19,184 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 14:01:19,184 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:01:19,184 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1624238937] [2025-03-03 14:01:19,184 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1624238937] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:01:19,184 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:01:19,185 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 14:01:19,185 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [208594993] [2025-03-03 14:01:19,185 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:01:19,185 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 14:01:19,185 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:01:19,186 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 14:01:19,186 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 14:01:19,186 INFO L87 Difference]: Start difference. First operand 31 states and 40 transitions. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 14:01:19,263 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:01:19,263 INFO L93 Difference]: Finished difference Result 43 states and 56 transitions. [2025-03-03 14:01:19,264 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 14:01:19,264 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2025-03-03 14:01:19,264 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:01:19,264 INFO L225 Difference]: With dead ends: 43 [2025-03-03 14:01:19,264 INFO L226 Difference]: Without dead ends: 41 [2025-03-03 14:01:19,265 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-03-03 14:01:19,265 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 8 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:01:19,266 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 116 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:01:19,266 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2025-03-03 14:01:19,270 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 35. [2025-03-03 14:01:19,270 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-03 14:01:19,271 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 43 transitions. [2025-03-03 14:01:19,271 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 43 transitions. Word has length 28 [2025-03-03 14:01:19,271 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:01:19,271 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 43 transitions. [2025-03-03 14:01:19,271 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-03 14:01:19,271 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 43 transitions. [2025-03-03 14:01:19,273 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2025-03-03 14:01:19,273 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:01:19,273 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:01:19,273 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-03 14:01:19,274 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:01:19,274 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:01:19,274 INFO L85 PathProgramCache]: Analyzing trace with hash 312813829, now seen corresponding path program 1 times [2025-03-03 14:01:19,274 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:01:19,274 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [447583600] [2025-03-03 14:01:19,274 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:19,274 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:01:19,280 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-03 14:01:19,295 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-03 14:01:19,295 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:19,295 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:01:19,296 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [754887561] [2025-03-03 14:01:19,297 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:19,297 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:01:19,297 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:01:19,299 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:01:19,302 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-03 14:01:19,327 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-03-03 14:01:19,343 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-03-03 14:01:19,343 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:19,343 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:01:19,345 INFO L256 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-03-03 14:01:19,346 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:01:19,477 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2025-03-03 14:01:19,478 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 14:01:19,478 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:01:19,478 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [447583600] [2025-03-03 14:01:19,478 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:01:19,479 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [754887561] [2025-03-03 14:01:19,479 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [754887561] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:01:19,479 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:01:19,479 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2025-03-03 14:01:19,479 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1457092681] [2025-03-03 14:01:19,479 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:01:19,479 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-03 14:01:19,479 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:01:19,480 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-03 14:01:19,480 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2025-03-03 14:01:19,480 INFO L87 Difference]: Start difference. First operand 35 states and 43 transitions. Second operand has 9 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-03 14:01:19,574 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:01:19,574 INFO L93 Difference]: Finished difference Result 58 states and 77 transitions. [2025-03-03 14:01:19,574 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-03 14:01:19,575 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) Word has length 33 [2025-03-03 14:01:19,575 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:01:19,575 INFO L225 Difference]: With dead ends: 58 [2025-03-03 14:01:19,575 INFO L226 Difference]: Without dead ends: 46 [2025-03-03 14:01:19,576 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2025-03-03 14:01:19,576 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 13 mSDsluCounter, 129 mSDsCounter, 0 mSdLazyCounter, 100 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 100 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:01:19,576 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 157 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 100 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:01:19,577 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2025-03-03 14:01:19,582 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2025-03-03 14:01:19,582 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 25 states have (on average 1.2) internal successors, (30), 26 states have internal predecessors, (30), 15 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2025-03-03 14:01:19,585 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 59 transitions. [2025-03-03 14:01:19,585 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 59 transitions. Word has length 33 [2025-03-03 14:01:19,585 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:01:19,585 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 59 transitions. [2025-03-03 14:01:19,586 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-03 14:01:19,586 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 59 transitions. [2025-03-03 14:01:19,586 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2025-03-03 14:01:19,587 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:01:19,587 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 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-03 14:01:19,593 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-03 14:01:19,791 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2025-03-03 14:01:19,791 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:01:19,791 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:01:19,791 INFO L85 PathProgramCache]: Analyzing trace with hash 987889245, now seen corresponding path program 1 times [2025-03-03 14:01:19,791 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:01:19,791 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1256764304] [2025-03-03 14:01:19,792 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:19,792 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:01:19,796 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 39 statements into 1 equivalence classes. [2025-03-03 14:01:19,805 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 39 of 39 statements. [2025-03-03 14:01:19,805 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:19,805 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:01:19,805 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2070023803] [2025-03-03 14:01:19,806 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:19,806 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:01:19,806 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:01:19,807 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:01:19,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-03 14:01:19,828 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 39 statements into 1 equivalence classes. [2025-03-03 14:01:19,838 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 39 of 39 statements. [2025-03-03 14:01:19,839 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:19,839 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:01:19,840 INFO L256 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 23 conjuncts are in the unsatisfiable core [2025-03-03 14:01:19,841 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:01:20,067 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 13 proven. 5 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 14:01:20,067 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:01:20,930 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-03 14:01:20,931 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:01:20,931 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1256764304] [2025-03-03 14:01:20,931 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:01:20,931 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2070023803] [2025-03-03 14:01:20,933 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2070023803] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:01:20,933 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:01:20,933 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 18 [2025-03-03 14:01:20,933 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [619449780] [2025-03-03 14:01:20,933 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:01:20,934 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2025-03-03 14:01:20,934 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:01:20,934 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2025-03-03 14:01:20,934 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=249, Unknown=0, NotChecked=0, Total=306 [2025-03-03 14:01:20,934 INFO L87 Difference]: Start difference. First operand 46 states and 59 transitions. Second operand has 18 states, 12 states have (on average 2.0) internal successors, (24), 12 states have internal predecessors, (24), 8 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 8 states have call predecessors, (11), 6 states have call successors, (11) [2025-03-03 14:01:25,750 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-03 14:01:29,804 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-03 14:01:30,065 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:01:30,065 INFO L93 Difference]: Finished difference Result 66 states and 81 transitions. [2025-03-03 14:01:30,065 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-03 14:01:30,066 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 12 states have (on average 2.0) internal successors, (24), 12 states have internal predecessors, (24), 8 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 8 states have call predecessors, (11), 6 states have call successors, (11) Word has length 39 [2025-03-03 14:01:30,066 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:01:30,067 INFO L225 Difference]: With dead ends: 66 [2025-03-03 14:01:30,067 INFO L226 Difference]: Without dead ends: 59 [2025-03-03 14:01:30,068 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 58 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 83 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=122, Invalid=430, Unknown=0, NotChecked=0, Total=552 [2025-03-03 14:01:30,068 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 33 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 255 mSolverCounterSat, 77 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 148 SdHoareTripleChecker+Invalid, 334 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 77 IncrementalHoareTripleChecker+Valid, 255 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.9s IncrementalHoareTripleChecker+Time [2025-03-03 14:01:30,068 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 148 Invalid, 334 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [77 Valid, 255 Invalid, 2 Unknown, 0 Unchecked, 8.9s Time] [2025-03-03 14:01:30,069 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-03-03 14:01:30,077 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 56. [2025-03-03 14:01:30,078 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 33 states have (on average 1.121212121212121) internal successors, (37), 35 states have internal predecessors, (37), 14 states have call successors, (14), 8 states have call predecessors, (14), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-03 14:01:30,079 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 64 transitions. [2025-03-03 14:01:30,080 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 64 transitions. Word has length 39 [2025-03-03 14:01:30,080 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:01:30,080 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 64 transitions. [2025-03-03 14:01:30,081 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 12 states have (on average 2.0) internal successors, (24), 12 states have internal predecessors, (24), 8 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 8 states have call predecessors, (11), 6 states have call successors, (11) [2025-03-03 14:01:30,081 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 64 transitions. [2025-03-03 14:01:30,081 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2025-03-03 14:01:30,081 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:01:30,081 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:01:30,087 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-03 14:01:30,282 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:01:30,282 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:01:30,282 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:01:30,282 INFO L85 PathProgramCache]: Analyzing trace with hash 251057081, now seen corresponding path program 1 times [2025-03-03 14:01:30,282 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:01:30,282 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [286887307] [2025-03-03 14:01:30,282 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:30,283 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:01:30,286 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-03-03 14:01:30,302 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-03-03 14:01:30,303 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:30,303 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:01:30,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [321499910] [2025-03-03 14:01:30,304 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:30,304 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:01:30,304 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:01:30,306 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:01:30,309 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-03 14:01:30,329 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-03-03 14:01:30,352 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-03-03 14:01:30,352 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:30,352 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:01:30,353 INFO L256 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 14:01:30,355 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:01:30,403 INFO L134 CoverageAnalysis]: Checked inductivity of 65 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2025-03-03 14:01:30,403 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:01:30,492 INFO L134 CoverageAnalysis]: Checked inductivity of 65 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2025-03-03 14:01:30,492 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:01:30,492 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [286887307] [2025-03-03 14:01:30,492 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:01:30,492 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [321499910] [2025-03-03 14:01:30,493 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [321499910] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-03 14:01:30,493 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:01:30,493 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 8 [2025-03-03 14:01:30,493 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1934251808] [2025-03-03 14:01:30,493 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:01:30,493 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-03 14:01:30,493 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:01:30,493 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-03 14:01:30,494 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2025-03-03 14:01:30,494 INFO L87 Difference]: Start difference. First operand 56 states and 64 transitions. Second operand has 6 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 3 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-03 14:01:31,120 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:01:31,120 INFO L93 Difference]: Finished difference Result 65 states and 75 transitions. [2025-03-03 14:01:31,121 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 14:01:31,121 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 3 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 49 [2025-03-03 14:01:31,121 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:01:31,122 INFO L225 Difference]: With dead ends: 65 [2025-03-03 14:01:31,123 INFO L226 Difference]: Without dead ends: 63 [2025-03-03 14:01:31,123 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 88 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2025-03-03 14:01:31,124 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 5 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-03 14:01:31,124 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 110 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-03 14:01:31,125 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2025-03-03 14:01:31,137 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2025-03-03 14:01:31,138 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 36 states have (on average 1.1111111111111112) internal successors, (40), 39 states have internal predecessors, (40), 16 states have call successors, (16), 9 states have call predecessors, (16), 9 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-03 14:01:31,138 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 71 transitions. [2025-03-03 14:01:31,139 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 71 transitions. Word has length 49 [2025-03-03 14:01:31,139 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:01:31,140 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 71 transitions. [2025-03-03 14:01:31,140 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 3 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-03 14:01:31,140 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 71 transitions. [2025-03-03 14:01:31,141 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2025-03-03 14:01:31,141 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:01:31,141 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:01:31,148 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-03 14:01:31,342 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:01:31,342 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:01:31,342 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:01:31,343 INFO L85 PathProgramCache]: Analyzing trace with hash -727564275, now seen corresponding path program 1 times [2025-03-03 14:01:31,343 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:01:31,343 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [540670617] [2025-03-03 14:01:31,343 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:31,343 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:01:31,348 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 66 statements into 1 equivalence classes. [2025-03-03 14:01:31,353 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 66 of 66 statements. [2025-03-03 14:01:31,353 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:31,354 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:01:31,448 INFO L134 CoverageAnalysis]: Checked inductivity of 144 backedges. 16 proven. 4 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2025-03-03 14:01:31,448 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:01:31,448 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [540670617] [2025-03-03 14:01:31,448 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [540670617] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:01:31,448 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [908045887] [2025-03-03 14:01:31,448 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:31,448 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:01:31,448 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:01:31,452 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:01:31,454 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-03 14:01:31,476 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 66 statements into 1 equivalence classes. [2025-03-03 14:01:31,492 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 66 of 66 statements. [2025-03-03 14:01:31,492 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:31,492 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:01:31,493 INFO L256 TraceCheckSpWp]: Trace formula consists of 147 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-03 14:01:31,494 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:01:31,562 INFO L134 CoverageAnalysis]: Checked inductivity of 144 backedges. 33 proven. 4 refuted. 0 times theorem prover too weak. 107 trivial. 0 not checked. [2025-03-03 14:01:31,562 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:01:31,616 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [908045887] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:01:31,617 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:01:31,617 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 8] total 10 [2025-03-03 14:01:31,617 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1427106402] [2025-03-03 14:01:31,617 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:01:31,618 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-03 14:01:31,618 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:01:31,618 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-03 14:01:31,619 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2025-03-03 14:01:31,619 INFO L87 Difference]: Start difference. First operand 62 states and 71 transitions. Second operand has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2025-03-03 14:01:31,787 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:01:31,788 INFO L93 Difference]: Finished difference Result 91 states and 111 transitions. [2025-03-03 14:01:31,788 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-03 14:01:31,788 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 66 [2025-03-03 14:01:31,789 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:01:31,789 INFO L225 Difference]: With dead ends: 91 [2025-03-03 14:01:31,789 INFO L226 Difference]: Without dead ends: 83 [2025-03-03 14:01:31,790 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 64 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2025-03-03 14:01:31,790 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 11 mSDsluCounter, 184 mSDsCounter, 0 mSdLazyCounter, 176 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 213 SdHoareTripleChecker+Invalid, 191 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 176 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:01:31,790 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 213 Invalid, 191 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 176 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:01:31,790 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2025-03-03 14:01:31,802 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 82. [2025-03-03 14:01:31,803 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 46 states have (on average 1.1521739130434783) internal successors, (53), 50 states have internal predecessors, (53), 24 states have call successors, (24), 11 states have call predecessors, (24), 11 states have return successors, (23), 20 states have call predecessors, (23), 23 states have call successors, (23) [2025-03-03 14:01:31,803 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 100 transitions. [2025-03-03 14:01:31,804 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 100 transitions. Word has length 66 [2025-03-03 14:01:31,804 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:01:31,804 INFO L471 AbstractCegarLoop]: Abstraction has 82 states and 100 transitions. [2025-03-03 14:01:31,804 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2025-03-03 14:01:31,804 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 100 transitions. [2025-03-03 14:01:31,804 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2025-03-03 14:01:31,806 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:01:31,806 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:01:31,812 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-03 14:01:32,006 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:01:32,007 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:01:32,007 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:01:32,007 INFO L85 PathProgramCache]: Analyzing trace with hash -1056327704, now seen corresponding path program 1 times [2025-03-03 14:01:32,007 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:01:32,007 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [512765365] [2025-03-03 14:01:32,007 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:32,007 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:01:32,011 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 67 statements into 1 equivalence classes. [2025-03-03 14:01:32,049 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 67 of 67 statements. [2025-03-03 14:01:32,049 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:32,049 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:01:32,050 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1589580557] [2025-03-03 14:01:32,050 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:01:32,050 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:01:32,050 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:01:32,054 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:01:32,055 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-03 14:01:32,076 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 67 statements into 1 equivalence classes. [2025-03-03 14:01:32,130 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 67 of 67 statements. [2025-03-03 14:01:32,130 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:01:32,130 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:01:32,132 INFO L256 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 55 conjuncts are in the unsatisfiable core [2025-03-03 14:01:32,134 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:01:32,708 INFO L134 CoverageAnalysis]: Checked inductivity of 145 backedges. 43 proven. 23 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2025-03-03 14:01:32,709 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:02:05,905 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 29 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-03 14:02:30,022 WARN L286 SmtUtils]: Spent 16.02s on a formula simplification that was a NOOP. DAG size: 10 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2025-03-03 14:02:51,401 WARN L286 SmtUtils]: Spent 21.38s on a formula simplification that was a NOOP. DAG size: 20 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2025-03-03 14:02:59,423 WARN L873 $PredicateComparison]: unable to prove that (let ((.cse1 (mod (* |c_ULTIMATE.start_main_~p~0#1| |c_ULTIMATE.start_main_~B~0#1|) 4294967296))) (let ((.cse2 (mod |c_ULTIMATE.start_main_~r~0#1| 4294967296)) (.cse3 (div .cse1 2)) (.cse0 (mod |c_ULTIMATE.start_main_~p~0#1| 4294967296))) (or (= .cse0 1) (< .cse1 (+ .cse2 1)) (< .cse2 .cse3) (= (mod |c_ULTIMATE.start_main_~A~0#1| 4294967296) (mod (+ (* 4294967295 .cse3) (* |c_ULTIMATE.start_main_~B~0#1| (div .cse0 2)) (* |c_ULTIMATE.start_main_~B~0#1| |c_ULTIMATE.start_main_~q~0#1|) |c_ULTIMATE.start_main_~r~0#1|) 4294967296))))) is different from true