./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version e2fb8bed Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.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 aa34b6970b46b2c3f1bda76d086482188f10831dd44cba913e5171769601c6f3 --- Real Ultimate output --- This is Ultimate 0.3.0-?-e2fb8be-m [2025-03-08 05:00:24,306 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-08 05:00:24,362 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-08 05:00:24,365 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-08 05:00:24,365 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-08 05:00:24,383 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-08 05:00:24,383 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-08 05:00:24,383 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-08 05:00:24,384 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-08 05:00:24,384 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-08 05:00:24,384 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-08 05:00:24,384 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-08 05:00:24,384 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-08 05:00:24,385 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-08 05:00:24,385 INFO L153 SettingsManager]: * Use SBE=true [2025-03-08 05:00:24,385 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-08 05:00:24,385 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-08 05:00:24,386 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-08 05:00:24,386 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-08 05:00:24,386 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-08 05:00:24,386 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-08 05:00:24,386 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-08 05:00:24,386 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-08 05:00:24,386 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-08 05:00:24,386 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-08 05:00:24,386 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-08 05:00:24,386 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-08 05:00:24,387 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-08 05:00:24,387 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-08 05:00:24,387 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-08 05:00:24,387 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-08 05:00:24,387 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-08 05:00:24,387 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:00:24,387 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-08 05:00:24,387 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-08 05:00:24,387 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-08 05:00:24,387 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-08 05:00:24,387 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-08 05:00:24,387 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-08 05:00:24,388 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-08 05:00:24,388 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-08 05:00:24,388 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-08 05:00:24,388 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-08 05:00:24,388 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 -> aa34b6970b46b2c3f1bda76d086482188f10831dd44cba913e5171769601c6f3 [2025-03-08 05:00:24,603 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-08 05:00:24,610 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-08 05:00:24,611 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-08 05:00:24,612 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-08 05:00:24,612 INFO L274 PluginConnector]: CDTParser initialized [2025-03-08 05:00:24,612 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c [2025-03-08 05:00:25,716 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a5723a0d9/19ee5be92b6f4676b133c19dcffae514/FLAG7512c37cc [2025-03-08 05:00:25,926 INFO L384 CDTParser]: Found 1 translation units. [2025-03-08 05:00:25,927 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c [2025-03-08 05:00:25,936 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a5723a0d9/19ee5be92b6f4676b133c19dcffae514/FLAG7512c37cc [2025-03-08 05:00:25,946 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a5723a0d9/19ee5be92b6f4676b133c19dcffae514 [2025-03-08 05:00:25,948 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-08 05:00:25,949 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-08 05:00:25,949 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-08 05:00:25,949 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-08 05:00:25,952 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-08 05:00:25,952 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:00:25" (1/1) ... [2025-03-08 05:00:25,953 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@27c4e706 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:25, skipping insertion in model container [2025-03-08 05:00:25,954 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.03 05:00:25" (1/1) ... [2025-03-08 05:00:25,964 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-08 05:00:26,061 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/egcd2-ll_unwindbound10.c[490,503] [2025-03-08 05:00:26,082 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:00:26,089 INFO L200 MainTranslator]: Completed pre-run [2025-03-08 05:00:26,095 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/egcd2-ll_unwindbound10.c[490,503] [2025-03-08 05:00:26,101 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-08 05:00:26,110 INFO L204 MainTranslator]: Completed translation [2025-03-08 05:00:26,111 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26 WrapperNode [2025-03-08 05:00:26,111 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-08 05:00:26,112 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-08 05:00:26,112 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-08 05:00:26,112 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-08 05:00:26,117 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26" (1/1) ... [2025-03-08 05:00:26,126 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26" (1/1) ... [2025-03-08 05:00:26,139 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 84 [2025-03-08 05:00:26,139 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-08 05:00:26,140 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-08 05:00:26,140 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-08 05:00:26,140 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-08 05:00:26,146 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26" (1/1) ... [2025-03-08 05:00:26,147 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26" (1/1) ... [2025-03-08 05:00:26,149 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26" (1/1) ... [2025-03-08 05:00:26,167 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-08 05:00:26,169 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26" (1/1) ... [2025-03-08 05:00:26,169 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26" (1/1) ... [2025-03-08 05:00:26,172 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26" (1/1) ... [2025-03-08 05:00:26,181 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26" (1/1) ... [2025-03-08 05:00:26,187 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26" (1/1) ... [2025-03-08 05:00:26,189 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26" (1/1) ... [2025-03-08 05:00:26,191 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-08 05:00:26,194 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-08 05:00:26,195 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-08 05:00:26,195 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-08 05:00:26,199 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26" (1/1) ... [2025-03-08 05:00:26,203 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-08 05:00:26,218 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:26,236 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-08 05:00:26,239 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-08 05:00:26,256 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-08 05:00:26,256 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-08 05:00:26,257 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-08 05:00:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-08 05:00:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-08 05:00:26,257 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-08 05:00:26,257 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-08 05:00:26,257 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-08 05:00:26,309 INFO L256 CfgBuilder]: Building ICFG [2025-03-08 05:00:26,310 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-08 05:00:26,433 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2025-03-08 05:00:26,433 INFO L307 CfgBuilder]: Performing block encoding [2025-03-08 05:00:26,438 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-08 05:00:26,439 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-08 05:00:26,439 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:00:26 BoogieIcfgContainer [2025-03-08 05:00:26,439 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-08 05:00:26,443 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-08 05:00:26,443 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-08 05:00:26,448 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-08 05:00:26,448 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.03 05:00:25" (1/3) ... [2025-03-08 05:00:26,449 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7aaf0fa8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:00:26, skipping insertion in model container [2025-03-08 05:00:26,449 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.03 05:00:26" (2/3) ... [2025-03-08 05:00:26,449 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7aaf0fa8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.03 05:00:26, skipping insertion in model container [2025-03-08 05:00:26,449 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 08.03 05:00:26" (3/3) ... [2025-03-08 05:00:26,450 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound10.c [2025-03-08 05:00:26,461 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-08 05:00:26,463 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd2-ll_unwindbound10.c that has 3 procedures, 34 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-08 05:00:26,504 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-08 05:00:26,516 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;@725d1a07, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-08 05:00:26,516 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-08 05:00:26,521 INFO L276 IsEmpty]: Start isEmpty. Operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 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-08 05:00:26,526 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-08 05:00:26,526 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:26,527 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:26,527 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:26,531 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:26,531 INFO L85 PathProgramCache]: Analyzing trace with hash 100709880, now seen corresponding path program 1 times [2025-03-08 05:00:26,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:26,537 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1018120840] [2025-03-08 05:00:26,537 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:26,539 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:26,593 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-08 05:00:26,606 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-08 05:00:26,607 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:26,607 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:26,657 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-08 05:00:26,658 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:26,658 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1018120840] [2025-03-08 05:00:26,658 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1018120840] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:26,658 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [771490413] [2025-03-08 05:00:26,659 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:26,659 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:26,659 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:26,661 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:26,663 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-08 05:00:26,697 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-08 05:00:26,720 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-08 05:00:26,720 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:26,720 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:26,722 INFO L256 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-08 05:00:26,724 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:26,735 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-03-08 05:00:26,737 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:26,738 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [771490413] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:26,738 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:26,738 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-08 05:00:26,740 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [289199704] [2025-03-08 05:00:26,740 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:26,743 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-08 05:00:26,743 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:26,756 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-08 05:00:26,757 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 05:00:26,758 INFO L87 Difference]: Start difference. First operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-08 05:00:26,771 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:26,771 INFO L93 Difference]: Finished difference Result 65 states and 104 transitions. [2025-03-08 05:00:26,772 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-08 05:00:26,773 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2025-03-08 05:00:26,773 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:26,777 INFO L225 Difference]: With dead ends: 65 [2025-03-08 05:00:26,777 INFO L226 Difference]: Without dead ends: 30 [2025-03-08 05:00:26,779 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-08 05:00:26,781 INFO L435 NwaCegarLoop]: 45 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, 45 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:26,781 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:26,794 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2025-03-08 05:00:26,802 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2025-03-08 05:00:26,803 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 19 states have internal predecessors, (22), 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-08 05:00:26,806 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 41 transitions. [2025-03-08 05:00:26,807 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 41 transitions. Word has length 28 [2025-03-08 05:00:26,807 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:26,807 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 41 transitions. [2025-03-08 05:00:26,807 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-08 05:00:26,807 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 41 transitions. [2025-03-08 05:00:26,808 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-08 05:00:26,808 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:26,808 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:26,814 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-08 05:00:27,009 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2025-03-08 05:00:27,009 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:27,011 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:27,011 INFO L85 PathProgramCache]: Analyzing trace with hash -1726789354, now seen corresponding path program 1 times [2025-03-08 05:00:27,011 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:27,011 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1792476696] [2025-03-08 05:00:27,011 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:27,011 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:27,028 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-08 05:00:27,042 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-08 05:00:27,043 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:27,043 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:27,143 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:00:27,144 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:27,144 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1792476696] [2025-03-08 05:00:27,144 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1792476696] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:27,144 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:27,144 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-08 05:00:27,144 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [913381152] [2025-03-08 05:00:27,144 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:27,144 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-08 05:00:27,145 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:27,145 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-08 05:00:27,145 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-08 05:00:27,145 INFO L87 Difference]: Start difference. First operand 30 states and 41 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:00:27,173 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:27,173 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2025-03-08 05:00:27,173 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-08 05:00:27,173 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2025-03-08 05:00:27,174 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:27,174 INFO L225 Difference]: With dead ends: 40 [2025-03-08 05:00:27,174 INFO L226 Difference]: Without dead ends: 32 [2025-03-08 05:00:27,174 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-08 05:00:27,175 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 7 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:27,175 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 100 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:27,175 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2025-03-08 05:00:27,181 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2025-03-08 05:00:27,183 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 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-08 05:00:27,185 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 43 transitions. [2025-03-08 05:00:27,185 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 43 transitions. Word has length 29 [2025-03-08 05:00:27,186 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:27,187 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 43 transitions. [2025-03-08 05:00:27,187 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:00:27,187 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 43 transitions. [2025-03-08 05:00:27,187 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-03-08 05:00:27,188 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:27,188 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:27,188 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-08 05:00:27,189 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:27,189 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:27,189 INFO L85 PathProgramCache]: Analyzing trace with hash -2044305484, now seen corresponding path program 1 times [2025-03-08 05:00:27,189 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:27,189 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1648091007] [2025-03-08 05:00:27,189 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:27,190 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:27,198 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-08 05:00:27,214 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-08 05:00:27,214 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:27,215 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:27,373 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-08 05:00:27,374 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:27,374 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1648091007] [2025-03-08 05:00:27,374 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1648091007] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:27,375 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [312944406] [2025-03-08 05:00:27,375 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:27,375 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:27,375 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:27,377 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:27,378 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-08 05:00:27,407 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-08 05:00:27,425 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-08 05:00:27,425 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:27,425 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:27,426 INFO L256 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-08 05:00:27,427 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:27,562 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:00:27,563 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:27,563 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [312944406] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:27,563 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:27,563 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2025-03-08 05:00:27,563 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1189390959] [2025-03-08 05:00:27,563 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:27,564 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-08 05:00:27,564 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:27,564 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-08 05:00:27,564 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2025-03-08 05:00:27,564 INFO L87 Difference]: Start difference. First operand 32 states and 43 transitions. Second operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 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-08 05:00:27,633 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:27,633 INFO L93 Difference]: Finished difference Result 49 states and 67 transitions. [2025-03-08 05:00:27,633 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-08 05:00:27,634 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 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 30 [2025-03-08 05:00:27,634 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:27,635 INFO L225 Difference]: With dead ends: 49 [2025-03-08 05:00:27,635 INFO L226 Difference]: Without dead ends: 47 [2025-03-08 05:00:27,635 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2025-03-08 05:00:27,635 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 9 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:27,636 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 146 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:27,636 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2025-03-08 05:00:27,641 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 45. [2025-03-08 05:00:27,641 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 28 states have internal predecessors, (34), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2025-03-08 05:00:27,641 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 63 transitions. [2025-03-08 05:00:27,642 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 63 transitions. Word has length 30 [2025-03-08 05:00:27,642 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:27,642 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 63 transitions. [2025-03-08 05:00:27,642 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 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-08 05:00:27,642 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 63 transitions. [2025-03-08 05:00:27,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-08 05:00:27,642 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:27,642 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:27,651 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-08 05:00:27,843 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,SelfDestructingSolverStorable2 [2025-03-08 05:00:27,843 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:27,844 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:27,844 INFO L85 PathProgramCache]: Analyzing trace with hash -886820372, now seen corresponding path program 1 times [2025-03-08 05:00:27,844 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:27,845 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [630679618] [2025-03-08 05:00:27,845 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:27,845 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:27,851 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-08 05:00:27,860 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 05:00:27,860 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:27,860 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:27,862 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [461942788] [2025-03-08 05:00:27,862 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:27,862 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:27,862 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:27,866 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:27,868 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-08 05:00:27,890 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-08 05:00:27,911 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-08 05:00:27,911 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:27,911 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:27,914 INFO L256 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-08 05:00:27,915 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:27,964 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:00:27,966 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:27,967 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:27,967 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [630679618] [2025-03-08 05:00:27,967 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:27,967 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [461942788] [2025-03-08 05:00:27,968 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [461942788] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:27,968 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:27,968 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:00:27,968 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2135088766] [2025-03-08 05:00:27,968 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:27,968 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:27,968 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:27,969 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:27,969 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:00:27,969 INFO L87 Difference]: Start difference. First operand 45 states and 63 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:00:28,015 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:28,016 INFO L93 Difference]: Finished difference Result 66 states and 95 transitions. [2025-03-08 05:00:28,016 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:00:28,016 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2025-03-08 05:00:28,016 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:28,018 INFO L225 Difference]: With dead ends: 66 [2025-03-08 05:00:28,018 INFO L226 Difference]: Without dead ends: 64 [2025-03-08 05:00:28,019 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 28 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-08 05:00:28,019 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 5 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:28,020 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 139 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:28,020 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2025-03-08 05:00:28,030 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 55. [2025-03-08 05:00:28,030 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 33 states have (on average 1.303030303030303) internal successors, (43), 37 states have internal predecessors, (43), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 13 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-08 05:00:28,031 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 76 transitions. [2025-03-08 05:00:28,031 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 76 transitions. Word has length 32 [2025-03-08 05:00:28,031 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:28,032 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 76 transitions. [2025-03-08 05:00:28,033 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:00:28,033 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 76 transitions. [2025-03-08 05:00:28,035 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-08 05:00:28,035 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:28,035 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:28,041 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-08 05:00:28,236 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:28,236 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:28,236 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:28,236 INFO L85 PathProgramCache]: Analyzing trace with hash -276176331, now seen corresponding path program 1 times [2025-03-08 05:00:28,237 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:28,237 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1432665413] [2025-03-08 05:00:28,237 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:28,237 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:28,241 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-08 05:00:28,246 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-08 05:00:28,246 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:28,246 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:28,330 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-08 05:00:28,331 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:28,331 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1432665413] [2025-03-08 05:00:28,333 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1432665413] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:28,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [747499618] [2025-03-08 05:00:28,333 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:28,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:28,333 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:28,335 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:28,336 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-08 05:00:28,360 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-08 05:00:28,372 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-08 05:00:28,372 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:28,372 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:28,373 INFO L256 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-08 05:00:28,374 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:28,462 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:00:28,462 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:28,462 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [747499618] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:28,462 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:28,463 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2025-03-08 05:00:28,463 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [203142078] [2025-03-08 05:00:28,463 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:28,463 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:28,463 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:28,463 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:28,463 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:00:28,463 INFO L87 Difference]: Start difference. First operand 55 states and 76 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-08 05:00:28,504 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:28,504 INFO L93 Difference]: Finished difference Result 63 states and 83 transitions. [2025-03-08 05:00:28,504 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:00:28,505 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 35 [2025-03-08 05:00:28,505 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:28,505 INFO L225 Difference]: With dead ends: 63 [2025-03-08 05:00:28,505 INFO L226 Difference]: Without dead ends: 59 [2025-03-08 05:00:28,508 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2025-03-08 05:00:28,509 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 9 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:28,509 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 142 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:28,511 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-03-08 05:00:28,519 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2025-03-08 05:00:28,521 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 36 states have (on average 1.25) internal successors, (45), 39 states have internal predecessors, (45), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-08 05:00:28,522 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 76 transitions. [2025-03-08 05:00:28,524 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 76 transitions. Word has length 35 [2025-03-08 05:00:28,524 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:28,524 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 76 transitions. [2025-03-08 05:00:28,525 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-03-08 05:00:28,525 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 76 transitions. [2025-03-08 05:00:28,525 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-08 05:00:28,525 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:28,525 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:28,532 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-08 05:00:28,729 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:28,729 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:28,730 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:28,730 INFO L85 PathProgramCache]: Analyzing trace with hash -247836027, now seen corresponding path program 1 times [2025-03-08 05:00:28,730 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:28,730 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1323527984] [2025-03-08 05:00:28,730 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:28,730 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:28,737 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-08 05:00:28,742 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-08 05:00:28,742 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:28,742 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:28,784 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-08 05:00:28,785 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:28,785 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1323527984] [2025-03-08 05:00:28,785 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1323527984] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:28,785 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:28,785 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:00:28,785 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1442636500] [2025-03-08 05:00:28,785 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:28,785 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:28,785 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:28,785 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:28,785 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:00:28,786 INFO L87 Difference]: Start difference. First operand 58 states and 76 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:00:28,804 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:28,804 INFO L93 Difference]: Finished difference Result 84 states and 111 transitions. [2025-03-08 05:00:28,804 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:00:28,804 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 35 [2025-03-08 05:00:28,804 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:28,805 INFO L225 Difference]: With dead ends: 84 [2025-03-08 05:00:28,805 INFO L226 Difference]: Without dead ends: 58 [2025-03-08 05:00:28,805 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:00:28,805 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 10 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:28,806 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 100 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:28,807 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2025-03-08 05:00:28,811 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2025-03-08 05:00:28,815 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 36 states have (on average 1.2222222222222223) internal successors, (44), 39 states have internal predecessors, (44), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-08 05:00:28,815 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2025-03-08 05:00:28,815 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 35 [2025-03-08 05:00:28,815 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:28,815 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2025-03-08 05:00:28,815 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-08 05:00:28,816 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2025-03-08 05:00:28,816 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-03-08 05:00:28,816 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:28,816 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:28,816 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2025-03-08 05:00:28,816 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:28,816 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:28,816 INFO L85 PathProgramCache]: Analyzing trace with hash -1535941731, now seen corresponding path program 1 times [2025-03-08 05:00:28,816 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:28,816 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [671783121] [2025-03-08 05:00:28,817 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:28,817 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:28,825 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-08 05:00:28,835 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-08 05:00:28,835 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:28,835 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:28,835 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1649306621] [2025-03-08 05:00:28,835 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:28,835 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:28,835 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:28,838 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:28,840 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-08 05:00:28,869 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-08 05:00:28,885 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-08 05:00:28,886 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:28,886 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:28,887 INFO L256 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-08 05:00:28,888 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:29,035 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-03-08 05:00:29,035 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-08 05:00:29,035 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:29,035 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [671783121] [2025-03-08 05:00:29,035 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:29,035 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1649306621] [2025-03-08 05:00:29,035 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1649306621] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:29,036 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:29,036 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:00:29,036 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [622346504] [2025-03-08 05:00:29,036 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:29,036 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:29,036 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:29,036 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:29,036 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:00:29,037 INFO L87 Difference]: Start difference. First operand 58 states and 75 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-03-08 05:00:29,083 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:29,083 INFO L93 Difference]: Finished difference Result 65 states and 81 transitions. [2025-03-08 05:00:29,084 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-08 05:00:29,084 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 47 [2025-03-08 05:00:29,084 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:29,085 INFO L225 Difference]: With dead ends: 65 [2025-03-08 05:00:29,085 INFO L226 Difference]: Without dead ends: 63 [2025-03-08 05:00:29,085 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 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-08 05:00:29,085 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 6 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:29,086 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 130 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:29,086 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2025-03-08 05:00:29,091 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2025-03-08 05:00:29,092 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 39 states have (on average 1.205128205128205) internal successors, (47), 42 states have internal predecessors, (47), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-08 05:00:29,092 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 78 transitions. [2025-03-08 05:00:29,092 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 78 transitions. Word has length 47 [2025-03-08 05:00:29,093 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:29,093 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 78 transitions. [2025-03-08 05:00:29,093 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-03-08 05:00:29,093 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 78 transitions. [2025-03-08 05:00:29,093 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-08 05:00:29,094 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:29,094 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:29,101 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-03-08 05:00:29,298 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-08 05:00:29,299 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:29,299 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:29,299 INFO L85 PathProgramCache]: Analyzing trace with hash 101798249, now seen corresponding path program 1 times [2025-03-08 05:00:29,299 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:29,299 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1309510119] [2025-03-08 05:00:29,299 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:29,299 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:29,304 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-08 05:00:29,323 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 05:00:29,323 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:29,323 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:29,324 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1323772483] [2025-03-08 05:00:29,324 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:29,324 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:29,324 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:29,327 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:29,331 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-08 05:00:29,358 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-08 05:00:29,379 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-08 05:00:29,379 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:29,379 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:29,380 INFO L256 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-08 05:00:29,381 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:29,457 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-08 05:00:29,457 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:29,565 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-08 05:00:29,565 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:29,565 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1309510119] [2025-03-08 05:00:29,565 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:29,565 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1323772483] [2025-03-08 05:00:29,565 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1323772483] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:29,565 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:00:29,565 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2025-03-08 05:00:29,565 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [857281599] [2025-03-08 05:00:29,566 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:29,566 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-08 05:00:29,566 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:29,566 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-08 05:00:29,566 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-08 05:00:29,566 INFO L87 Difference]: Start difference. First operand 62 states and 78 transitions. Second operand has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-08 05:00:29,649 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:29,649 INFO L93 Difference]: Finished difference Result 92 states and 127 transitions. [2025-03-08 05:00:29,649 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-08 05:00:29,649 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 55 [2025-03-08 05:00:29,649 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:29,650 INFO L225 Difference]: With dead ends: 92 [2025-03-08 05:00:29,650 INFO L226 Difference]: Without dead ends: 90 [2025-03-08 05:00:29,650 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 100 SyntacticMatches, 3 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-08 05:00:29,651 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 9 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 219 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:29,651 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 219 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:29,651 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2025-03-08 05:00:29,658 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 58. [2025-03-08 05:00:29,658 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 37 states have (on average 1.1891891891891893) internal successors, (44), 38 states have internal predecessors, (44), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-08 05:00:29,658 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 71 transitions. [2025-03-08 05:00:29,659 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 71 transitions. Word has length 55 [2025-03-08 05:00:29,659 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:29,659 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 71 transitions. [2025-03-08 05:00:29,659 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-08 05:00:29,659 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 71 transitions. [2025-03-08 05:00:29,659 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2025-03-08 05:00:29,659 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:29,659 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:29,665 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-03-08 05:00:29,863 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:29,863 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:29,864 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:29,864 INFO L85 PathProgramCache]: Analyzing trace with hash -1244697335, now seen corresponding path program 1 times [2025-03-08 05:00:29,864 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:29,864 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [317109015] [2025-03-08 05:00:29,864 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:29,864 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:29,871 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-08 05:00:29,879 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-08 05:00:29,881 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:29,881 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:29,961 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-08 05:00:29,962 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:29,962 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [317109015] [2025-03-08 05:00:29,962 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [317109015] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:29,962 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1723284154] [2025-03-08 05:00:29,962 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:29,962 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:29,962 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:29,964 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:29,966 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-08 05:00:29,991 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-08 05:00:30,008 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-08 05:00:30,008 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:30,009 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:30,010 INFO L256 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-08 05:00:30,011 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:30,069 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-08 05:00:30,069 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:30,149 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-08 05:00:30,150 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1723284154] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:30,150 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:00:30,150 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2025-03-08 05:00:30,150 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1302028083] [2025-03-08 05:00:30,150 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:30,151 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-08 05:00:30,151 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:30,151 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-08 05:00:30,151 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2025-03-08 05:00:30,151 INFO L87 Difference]: Start difference. First operand 58 states and 71 transitions. Second operand has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2025-03-08 05:00:30,314 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:30,314 INFO L93 Difference]: Finished difference Result 211 states and 250 transitions. [2025-03-08 05:00:30,315 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-08 05:00:30,315 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 56 [2025-03-08 05:00:30,316 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:30,317 INFO L225 Difference]: With dead ends: 211 [2025-03-08 05:00:30,317 INFO L226 Difference]: Without dead ends: 203 [2025-03-08 05:00:30,317 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 108 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2025-03-08 05:00:30,317 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 81 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 86 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 104 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 86 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:30,317 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [81 Valid, 194 Invalid, 104 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 86 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:30,318 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2025-03-08 05:00:30,345 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 195. [2025-03-08 05:00:30,346 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 195 states, 125 states have (on average 1.192) internal successors, (149), 129 states have internal predecessors, (149), 44 states have call successors, (44), 25 states have call predecessors, (44), 25 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2025-03-08 05:00:30,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 195 states to 195 states and 233 transitions. [2025-03-08 05:00:30,347 INFO L78 Accepts]: Start accepts. Automaton has 195 states and 233 transitions. Word has length 56 [2025-03-08 05:00:30,347 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:30,347 INFO L471 AbstractCegarLoop]: Abstraction has 195 states and 233 transitions. [2025-03-08 05:00:30,348 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2025-03-08 05:00:30,348 INFO L276 IsEmpty]: Start isEmpty. Operand 195 states and 233 transitions. [2025-03-08 05:00:30,348 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2025-03-08 05:00:30,348 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:30,348 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:30,354 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-08 05:00:30,549 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:30,549 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:30,549 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:30,550 INFO L85 PathProgramCache]: Analyzing trace with hash 15645217, now seen corresponding path program 1 times [2025-03-08 05:00:30,550 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:30,550 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2018847596] [2025-03-08 05:00:30,550 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:30,550 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:30,554 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-03-08 05:00:30,562 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-03-08 05:00:30,562 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:30,562 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:30,654 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-08 05:00:30,654 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:30,654 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2018847596] [2025-03-08 05:00:30,654 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2018847596] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:30,655 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [366741019] [2025-03-08 05:00:30,655 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:30,655 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:30,655 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:30,656 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:30,658 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-08 05:00:30,684 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-03-08 05:00:30,700 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-03-08 05:00:30,700 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:30,700 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:30,701 INFO L256 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-08 05:00:30,702 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:30,727 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-08 05:00:30,727 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:30,819 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-08 05:00:30,819 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [366741019] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:30,820 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:00:30,820 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-08 05:00:30,820 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1722361358] [2025-03-08 05:00:30,820 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:30,820 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-08 05:00:30,820 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:30,820 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-08 05:00:30,820 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:00:30,821 INFO L87 Difference]: Start difference. First operand 195 states and 233 transitions. Second operand has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-03-08 05:00:30,972 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:30,972 INFO L93 Difference]: Finished difference Result 279 states and 364 transitions. [2025-03-08 05:00:30,973 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-08 05:00:30,973 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 57 [2025-03-08 05:00:30,973 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:30,974 INFO L225 Difference]: With dead ends: 279 [2025-03-08 05:00:30,975 INFO L226 Difference]: Without dead ends: 259 [2025-03-08 05:00:30,975 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 109 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=134, Unknown=0, NotChecked=0, Total=182 [2025-03-08 05:00:30,975 INFO L435 NwaCegarLoop]: 48 mSDtfsCounter, 60 mSDsluCounter, 201 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:30,976 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 249 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:30,976 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states. [2025-03-08 05:00:31,010 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 235. [2025-03-08 05:00:31,011 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 235 states, 152 states have (on average 1.2236842105263157) internal successors, (186), 155 states have internal predecessors, (186), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2025-03-08 05:00:31,013 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 299 transitions. [2025-03-08 05:00:31,014 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 299 transitions. Word has length 57 [2025-03-08 05:00:31,014 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:31,014 INFO L471 AbstractCegarLoop]: Abstraction has 235 states and 299 transitions. [2025-03-08 05:00:31,014 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2025-03-08 05:00:31,014 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 299 transitions. [2025-03-08 05:00:31,016 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2025-03-08 05:00:31,016 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:31,017 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:31,023 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-03-08 05:00:31,217 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-08 05:00:31,218 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:31,218 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:31,218 INFO L85 PathProgramCache]: Analyzing trace with hash -351822558, now seen corresponding path program 1 times [2025-03-08 05:00:31,218 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:31,219 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1390816570] [2025-03-08 05:00:31,219 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:31,219 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:31,227 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 59 statements into 1 equivalence classes. [2025-03-08 05:00:31,235 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 59 of 59 statements. [2025-03-08 05:00:31,235 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:31,235 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:31,300 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-08 05:00:31,301 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:31,301 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1390816570] [2025-03-08 05:00:31,301 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1390816570] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:31,301 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [89165247] [2025-03-08 05:00:31,302 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:31,302 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:31,302 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:31,311 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:31,316 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-08 05:00:31,360 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 59 statements into 1 equivalence classes. [2025-03-08 05:00:31,376 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 59 of 59 statements. [2025-03-08 05:00:31,377 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:31,377 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:31,378 INFO L256 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-08 05:00:31,379 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:31,454 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-08 05:00:31,454 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:31,516 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-03-08 05:00:31,516 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [89165247] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:31,516 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-08 05:00:31,516 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2025-03-08 05:00:31,517 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1131210408] [2025-03-08 05:00:31,517 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:31,517 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-08 05:00:31,517 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:31,518 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-08 05:00:31,518 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2025-03-08 05:00:31,518 INFO L87 Difference]: Start difference. First operand 235 states and 299 transitions. Second operand has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2025-03-08 05:00:31,651 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:31,651 INFO L93 Difference]: Finished difference Result 344 states and 448 transitions. [2025-03-08 05:00:31,651 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-08 05:00:31,651 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 59 [2025-03-08 05:00:31,651 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:31,653 INFO L225 Difference]: With dead ends: 344 [2025-03-08 05:00:31,653 INFO L226 Difference]: Without dead ends: 248 [2025-03-08 05:00:31,654 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 114 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2025-03-08 05:00:31,654 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 68 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 70 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 83 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 70 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:31,654 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [68 Valid, 179 Invalid, 83 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 70 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:31,654 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 248 states. [2025-03-08 05:00:31,679 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 248 to 244. [2025-03-08 05:00:31,680 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 244 states, 161 states have (on average 1.173913043478261) internal successors, (189), 164 states have internal predecessors, (189), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2025-03-08 05:00:31,682 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 244 states to 244 states and 302 transitions. [2025-03-08 05:00:31,682 INFO L78 Accepts]: Start accepts. Automaton has 244 states and 302 transitions. Word has length 59 [2025-03-08 05:00:31,683 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:31,683 INFO L471 AbstractCegarLoop]: Abstraction has 244 states and 302 transitions. [2025-03-08 05:00:31,683 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2025-03-08 05:00:31,683 INFO L276 IsEmpty]: Start isEmpty. Operand 244 states and 302 transitions. [2025-03-08 05:00:31,684 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2025-03-08 05:00:31,684 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:31,684 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:31,691 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-08 05:00:31,890 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:31,890 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:31,890 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:31,890 INFO L85 PathProgramCache]: Analyzing trace with hash -1287548176, now seen corresponding path program 1 times [2025-03-08 05:00:31,890 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:31,890 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [772708528] [2025-03-08 05:00:31,890 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:31,890 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:31,895 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-03-08 05:00:31,904 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-03-08 05:00:31,904 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:31,904 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:31,904 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1144889534] [2025-03-08 05:00:31,905 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:31,905 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:31,905 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:31,906 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:31,908 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-08 05:00:31,931 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-03-08 05:00:31,952 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-03-08 05:00:31,952 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:31,952 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:31,953 INFO L256 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-03-08 05:00:31,955 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:32,075 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2025-03-08 05:00:32,076 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:32,108 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:32,108 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [772708528] [2025-03-08 05:00:32,108 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:32,108 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1144889534] [2025-03-08 05:00:32,108 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1144889534] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:32,108 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:32,108 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2025-03-08 05:00:32,108 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [650720639] [2025-03-08 05:00:32,109 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:32,109 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-08 05:00:32,109 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:32,109 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-08 05:00:32,109 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2025-03-08 05:00:32,109 INFO L87 Difference]: Start difference. First operand 244 states and 302 transitions. Second operand has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-08 05:00:32,198 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:32,199 INFO L93 Difference]: Finished difference Result 283 states and 355 transitions. [2025-03-08 05:00:32,199 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-08 05:00:32,199 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 64 [2025-03-08 05:00:32,199 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:32,201 INFO L225 Difference]: With dead ends: 283 [2025-03-08 05:00:32,201 INFO L226 Difference]: Without dead ends: 278 [2025-03-08 05:00:32,201 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 61 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2025-03-08 05:00:32,201 INFO L435 NwaCegarLoop]: 53 mSDtfsCounter, 10 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 213 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:32,202 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 213 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:32,202 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 278 states. [2025-03-08 05:00:32,225 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 278 to 276. [2025-03-08 05:00:32,226 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 276 states, 183 states have (on average 1.185792349726776) internal successors, (217), 187 states have internal predecessors, (217), 65 states have call successors, (65), 27 states have call predecessors, (65), 27 states have return successors, (61), 61 states have call predecessors, (61), 61 states have call successors, (61) [2025-03-08 05:00:32,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 276 states to 276 states and 343 transitions. [2025-03-08 05:00:32,228 INFO L78 Accepts]: Start accepts. Automaton has 276 states and 343 transitions. Word has length 64 [2025-03-08 05:00:32,228 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:32,228 INFO L471 AbstractCegarLoop]: Abstraction has 276 states and 343 transitions. [2025-03-08 05:00:32,228 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2025-03-08 05:00:32,228 INFO L276 IsEmpty]: Start isEmpty. Operand 276 states and 343 transitions. [2025-03-08 05:00:32,229 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2025-03-08 05:00:32,229 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:32,229 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:32,235 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-08 05:00:32,429 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2025-03-08 05:00:32,430 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:32,430 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:32,430 INFO L85 PathProgramCache]: Analyzing trace with hash 691051449, now seen corresponding path program 2 times [2025-03-08 05:00:32,430 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:32,430 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2114417435] [2025-03-08 05:00:32,430 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:00:32,430 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:32,435 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 69 statements into 2 equivalence classes. [2025-03-08 05:00:32,448 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 69 of 69 statements. [2025-03-08 05:00:32,448 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:00:32,448 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:32,448 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [891589736] [2025-03-08 05:00:32,448 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-08 05:00:32,449 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:32,449 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:32,453 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:32,454 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-08 05:00:32,479 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 69 statements into 2 equivalence classes. [2025-03-08 05:00:32,498 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 69 of 69 statements. [2025-03-08 05:00:32,498 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-08 05:00:32,498 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:32,500 INFO L256 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 23 conjuncts are in the unsatisfiable core [2025-03-08 05:00:32,501 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:32,666 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2025-03-08 05:00:32,667 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:32,727 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:32,727 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2114417435] [2025-03-08 05:00:32,728 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:32,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [891589736] [2025-03-08 05:00:32,728 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [891589736] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:32,728 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:32,728 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2025-03-08 05:00:32,728 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2145637265] [2025-03-08 05:00:32,728 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:32,728 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-08 05:00:32,728 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:32,728 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-08 05:00:32,728 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-08 05:00:32,729 INFO L87 Difference]: Start difference. First operand 276 states and 343 transitions. Second operand has 7 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2025-03-08 05:00:32,843 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:32,844 INFO L93 Difference]: Finished difference Result 291 states and 357 transitions. [2025-03-08 05:00:32,844 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-08 05:00:32,844 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 69 [2025-03-08 05:00:32,844 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:32,846 INFO L225 Difference]: With dead ends: 291 [2025-03-08 05:00:32,846 INFO L226 Difference]: Without dead ends: 289 [2025-03-08 05:00:32,846 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 81 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-03-08 05:00:32,848 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 16 mSDsluCounter, 182 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 228 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:32,848 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 228 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-08 05:00:32,849 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 289 states. [2025-03-08 05:00:32,880 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 289 to 288. [2025-03-08 05:00:32,881 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 288 states, 192 states have (on average 1.1770833333333333) internal successors, (226), 196 states have internal predecessors, (226), 65 states have call successors, (65), 30 states have call predecessors, (65), 30 states have return successors, (61), 61 states have call predecessors, (61), 61 states have call successors, (61) [2025-03-08 05:00:32,882 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 288 states to 288 states and 352 transitions. [2025-03-08 05:00:32,882 INFO L78 Accepts]: Start accepts. Automaton has 288 states and 352 transitions. Word has length 69 [2025-03-08 05:00:32,882 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:32,882 INFO L471 AbstractCegarLoop]: Abstraction has 288 states and 352 transitions. [2025-03-08 05:00:32,882 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2025-03-08 05:00:32,882 INFO L276 IsEmpty]: Start isEmpty. Operand 288 states and 352 transitions. [2025-03-08 05:00:32,883 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-03-08 05:00:32,883 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:32,883 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:32,889 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-03-08 05:00:33,083 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-03-08 05:00:33,084 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:33,084 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:33,084 INFO L85 PathProgramCache]: Analyzing trace with hash 239571152, now seen corresponding path program 3 times [2025-03-08 05:00:33,084 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:33,084 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1369143554] [2025-03-08 05:00:33,084 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 05:00:33,084 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:33,091 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 74 statements into 5 equivalence classes. [2025-03-08 05:00:33,106 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 74 of 74 statements. [2025-03-08 05:00:33,106 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-08 05:00:33,106 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:33,107 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [337370140] [2025-03-08 05:00:33,107 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-08 05:00:33,107 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:33,108 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:33,109 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:33,111 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-08 05:00:33,138 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 74 statements into 5 equivalence classes. [2025-03-08 05:00:33,155 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 54 of 74 statements. [2025-03-08 05:00:33,155 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-08 05:00:33,155 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:33,157 INFO L256 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 42 conjuncts are in the unsatisfiable core [2025-03-08 05:00:33,159 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:33,521 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 40 proven. 10 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2025-03-08 05:00:33,521 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:33,761 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:33,761 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1369143554] [2025-03-08 05:00:33,761 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:33,761 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [337370140] [2025-03-08 05:00:33,761 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [337370140] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-08 05:00:33,762 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-08 05:00:33,762 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2025-03-08 05:00:33,762 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1621970991] [2025-03-08 05:00:33,762 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:33,762 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-08 05:00:33,762 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:33,763 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-08 05:00:33,763 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=231, Unknown=0, NotChecked=0, Total=272 [2025-03-08 05:00:33,763 INFO L87 Difference]: Start difference. First operand 288 states and 352 transitions. Second operand has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-08 05:00:33,999 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:33,999 INFO L93 Difference]: Finished difference Result 303 states and 366 transitions. [2025-03-08 05:00:34,000 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-08 05:00:34,000 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 74 [2025-03-08 05:00:34,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:34,001 INFO L225 Difference]: With dead ends: 303 [2025-03-08 05:00:34,001 INFO L226 Difference]: Without dead ends: 299 [2025-03-08 05:00:34,002 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2025-03-08 05:00:34,002 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 26 mSDsluCounter, 247 mSDsCounter, 0 mSdLazyCounter, 271 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 281 SdHoareTripleChecker+Invalid, 287 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 271 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:34,002 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 281 Invalid, 287 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 271 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-08 05:00:34,003 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 299 states. [2025-03-08 05:00:34,029 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 299 to 298. [2025-03-08 05:00:34,030 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 298 states, 200 states have (on average 1.165) internal successors, (233), 203 states have internal predecessors, (233), 65 states have call successors, (65), 33 states have call predecessors, (65), 32 states have return successors, (61), 61 states have call predecessors, (61), 61 states have call successors, (61) [2025-03-08 05:00:34,032 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 298 states to 298 states and 359 transitions. [2025-03-08 05:00:34,032 INFO L78 Accepts]: Start accepts. Automaton has 298 states and 359 transitions. Word has length 74 [2025-03-08 05:00:34,032 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:34,032 INFO L471 AbstractCegarLoop]: Abstraction has 298 states and 359 transitions. [2025-03-08 05:00:34,032 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-08 05:00:34,033 INFO L276 IsEmpty]: Start isEmpty. Operand 298 states and 359 transitions. [2025-03-08 05:00:34,033 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2025-03-08 05:00:34,033 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:34,033 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:34,039 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2025-03-08 05:00:34,238 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-03-08 05:00:34,238 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:34,238 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:34,238 INFO L85 PathProgramCache]: Analyzing trace with hash 852496708, now seen corresponding path program 1 times [2025-03-08 05:00:34,238 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:34,238 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [249005333] [2025-03-08 05:00:34,238 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:34,239 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:34,242 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 80 statements into 1 equivalence classes. [2025-03-08 05:00:34,249 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 80 of 80 statements. [2025-03-08 05:00:34,249 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:34,249 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:34,249 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1728864] [2025-03-08 05:00:34,249 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:34,249 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:34,250 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:34,252 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:34,253 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-03-08 05:00:34,279 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 80 statements into 1 equivalence classes. [2025-03-08 05:00:34,299 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 80 of 80 statements. [2025-03-08 05:00:34,299 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:34,299 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:34,304 INFO L256 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 41 conjuncts are in the unsatisfiable core [2025-03-08 05:00:34,306 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:34,742 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 19 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2025-03-08 05:00:34,742 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:00:35,040 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2025-03-08 05:00:35,040 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:35,040 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [249005333] [2025-03-08 05:00:35,040 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:00:35,040 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1728864] [2025-03-08 05:00:35,040 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1728864] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:00:35,040 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:00:35,040 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2025-03-08 05:00:35,040 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [792363934] [2025-03-08 05:00:35,040 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:00:35,040 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-08 05:00:35,040 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:35,041 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-08 05:00:35,041 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2025-03-08 05:00:35,041 INFO L87 Difference]: Start difference. First operand 298 states and 359 transitions. Second operand has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2025-03-08 05:00:36,994 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:36,994 INFO L93 Difference]: Finished difference Result 435 states and 581 transitions. [2025-03-08 05:00:36,997 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-03-08 05:00:36,997 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 80 [2025-03-08 05:00:36,997 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:36,999 INFO L225 Difference]: With dead ends: 435 [2025-03-08 05:00:36,999 INFO L226 Difference]: Without dead ends: 428 [2025-03-08 05:00:36,999 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 139 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 265 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=296, Invalid=1264, Unknown=0, NotChecked=0, Total=1560 [2025-03-08 05:00:37,000 INFO L435 NwaCegarLoop]: 61 mSDtfsCounter, 134 mSDsluCounter, 700 mSDsCounter, 0 mSdLazyCounter, 559 mSolverCounterSat, 131 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 139 SdHoareTripleChecker+Valid, 761 SdHoareTripleChecker+Invalid, 690 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 131 IncrementalHoareTripleChecker+Valid, 559 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:37,000 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [139 Valid, 761 Invalid, 690 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [131 Valid, 559 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2025-03-08 05:00:37,001 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 428 states. [2025-03-08 05:00:37,053 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 428 to 391. [2025-03-08 05:00:37,054 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 391 states, 256 states have (on average 1.23046875) internal successors, (315), 259 states have internal predecessors, (315), 100 states have call successors, (100), 34 states have call predecessors, (100), 34 states have return successors, (98), 97 states have call predecessors, (98), 98 states have call successors, (98) [2025-03-08 05:00:37,057 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 391 states to 391 states and 513 transitions. [2025-03-08 05:00:37,058 INFO L78 Accepts]: Start accepts. Automaton has 391 states and 513 transitions. Word has length 80 [2025-03-08 05:00:37,058 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:37,058 INFO L471 AbstractCegarLoop]: Abstraction has 391 states and 513 transitions. [2025-03-08 05:00:37,058 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2025-03-08 05:00:37,058 INFO L276 IsEmpty]: Start isEmpty. Operand 391 states and 513 transitions. [2025-03-08 05:00:37,059 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2025-03-08 05:00:37,059 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:37,059 INFO L218 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:37,068 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2025-03-08 05:00:37,263 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2025-03-08 05:00:37,264 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:37,264 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:37,264 INFO L85 PathProgramCache]: Analyzing trace with hash 2042434077, now seen corresponding path program 4 times [2025-03-08 05:00:37,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:37,264 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1244797251] [2025-03-08 05:00:37,264 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-08 05:00:37,264 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:37,271 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 91 statements into 2 equivalence classes. [2025-03-08 05:00:37,279 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 87 of 91 statements. [2025-03-08 05:00:37,283 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-08 05:00:37,284 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:37,329 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 43 proven. 0 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2025-03-08 05:00:37,329 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:00:37,329 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1244797251] [2025-03-08 05:00:37,329 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1244797251] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-08 05:00:37,329 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-08 05:00:37,329 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-08 05:00:37,329 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [105955302] [2025-03-08 05:00:37,329 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-08 05:00:37,329 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-08 05:00:37,330 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:00:37,330 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-08 05:00:37,330 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-08 05:00:37,330 INFO L87 Difference]: Start difference. First operand 391 states and 513 transitions. Second operand has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-08 05:00:37,459 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-08 05:00:37,460 INFO L93 Difference]: Finished difference Result 587 states and 831 transitions. [2025-03-08 05:00:37,460 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-08 05:00:37,460 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) Word has length 91 [2025-03-08 05:00:37,461 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-08 05:00:37,465 INFO L225 Difference]: With dead ends: 587 [2025-03-08 05:00:37,465 INFO L226 Difference]: Without dead ends: 462 [2025-03-08 05:00:37,466 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2025-03-08 05:00:37,467 INFO L435 NwaCegarLoop]: 55 mSDtfsCounter, 12 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-08 05:00:37,467 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 186 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-08 05:00:37,469 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 462 states. [2025-03-08 05:00:37,528 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 462 to 410. [2025-03-08 05:00:37,529 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 410 states, 267 states have (on average 1.2397003745318351) internal successors, (331), 270 states have internal predecessors, (331), 108 states have call successors, (108), 34 states have call predecessors, (108), 34 states have return successors, (106), 105 states have call predecessors, (106), 106 states have call successors, (106) [2025-03-08 05:00:37,530 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 410 states to 410 states and 545 transitions. [2025-03-08 05:00:37,531 INFO L78 Accepts]: Start accepts. Automaton has 410 states and 545 transitions. Word has length 91 [2025-03-08 05:00:37,531 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-08 05:00:37,531 INFO L471 AbstractCegarLoop]: Abstraction has 410 states and 545 transitions. [2025-03-08 05:00:37,532 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-08 05:00:37,532 INFO L276 IsEmpty]: Start isEmpty. Operand 410 states and 545 transitions. [2025-03-08 05:00:37,532 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2025-03-08 05:00:37,532 INFO L210 NwaCegarLoop]: Found error trace [2025-03-08 05:00:37,533 INFO L218 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-08 05:00:37,533 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15 [2025-03-08 05:00:37,533 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-08 05:00:37,533 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-08 05:00:37,533 INFO L85 PathProgramCache]: Analyzing trace with hash 777061389, now seen corresponding path program 1 times [2025-03-08 05:00:37,533 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-08 05:00:37,533 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1498503430] [2025-03-08 05:00:37,534 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:37,534 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-08 05:00:37,538 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 97 statements into 1 equivalence classes. [2025-03-08 05:00:37,553 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 97 of 97 statements. [2025-03-08 05:00:37,553 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:37,553 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-08 05:00:37,554 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1524994519] [2025-03-08 05:00:37,554 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-08 05:00:37,554 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-08 05:00:37,555 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-08 05:00:37,557 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-08 05:00:37,559 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2025-03-08 05:00:37,590 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 97 statements into 1 equivalence classes. [2025-03-08 05:00:37,619 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 97 of 97 statements. [2025-03-08 05:00:37,619 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-08 05:00:37,620 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-08 05:00:37,621 INFO L256 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 53 conjuncts are in the unsatisfiable core [2025-03-08 05:00:37,625 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-08 05:00:38,390 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 68 proven. 39 refuted. 0 times theorem prover too weak. 181 trivial. 0 not checked. [2025-03-08 05:00:38,390 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-08 05:01:25,932 WARN L286 SmtUtils]: Spent 5.65s on a formula simplification that was a NOOP. DAG size: 24 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2025-03-08 05:01:27,304 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 68 proven. 30 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2025-03-08 05:01:27,304 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-08 05:01:27,304 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1498503430] [2025-03-08 05:01:27,304 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-08 05:01:27,304 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1524994519] [2025-03-08 05:01:27,304 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1524994519] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-08 05:01:27,304 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-08 05:01:27,304 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 26 [2025-03-08 05:01:27,304 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [782826620] [2025-03-08 05:01:27,304 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-08 05:01:27,304 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-03-08 05:01:27,304 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-08 05:01:27,305 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-03-08 05:01:27,305 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=537, Unknown=2, NotChecked=0, Total=650 [2025-03-08 05:01:27,305 INFO L87 Difference]: Start difference. First operand 410 states and 545 transitions. Second operand has 26 states, 25 states have (on average 2.12) internal successors, (53), 21 states have internal predecessors, (53), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 13 states have call predecessors, (30), 10 states have call successors, (30) [2025-03-08 05:01:31,451 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-08 05:01:44,730 WARN L286 SmtUtils]: Spent 12.92s on a formula simplification. DAG size of input: 76 DAG size of output: 75 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-08 05:01:57,506 WARN L286 SmtUtils]: Spent 8.39s on a formula simplification. DAG size of input: 67 DAG size of output: 66 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-08 05:02:01,989 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-08 05:02:06,776 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers []