./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 798a7b37 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound50.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 deef9b1f63fa90bdeace0bbb769d25578ef53bda95c70ad5e444555427b2b0e2 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 13:50:48,891 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 13:50:48,935 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-03 13:50:48,938 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 13:50:48,938 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 13:50:48,958 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 13:50:48,958 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 13:50:48,958 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 13:50:48,958 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 13:50:48,958 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 13:50:48,958 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 13:50:48,958 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 13:50:48,959 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 13:50:48,959 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 13:50:48,959 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 13:50:48,959 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 13:50:48,960 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 13:50:48,960 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 13:50:48,960 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 13:50:48,960 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 13:50:48,960 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 13:50:48,960 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 13:50:48,960 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 13:50:48,960 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 13:50:48,960 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 13:50:48,960 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 13:50:48,960 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 13:50:48,960 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 -> deef9b1f63fa90bdeace0bbb769d25578ef53bda95c70ad5e444555427b2b0e2 [2025-03-03 13:50:49,182 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 13:50:49,189 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 13:50:49,191 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 13:50:49,191 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 13:50:49,192 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 13:50:49,193 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound50.c [2025-03-03 13:50:50,317 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/32821b63b/26516763a98347b18ef5653df902c981/FLAGca9b5990c [2025-03-03 13:50:50,537 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 13:50:50,538 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound50.c [2025-03-03 13:50:50,543 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/32821b63b/26516763a98347b18ef5653df902c981/FLAGca9b5990c [2025-03-03 13:50:50,559 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/32821b63b/26516763a98347b18ef5653df902c981 [2025-03-03 13:50:50,561 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 13:50:50,564 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 13:50:50,575 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 13:50:50,576 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 13:50:50,583 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 13:50:50,584 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,585 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6777911c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50, skipping insertion in model container [2025-03-03 13:50:50,585 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,595 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 13:50:50,692 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_unwindbound50.c[490,503] [2025-03-03 13:50:50,711 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 13:50:50,718 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 13:50:50,727 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_unwindbound50.c[490,503] [2025-03-03 13:50:50,735 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 13:50:50,745 INFO L204 MainTranslator]: Completed translation [2025-03-03 13:50:50,746 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50 WrapperNode [2025-03-03 13:50:50,746 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 13:50:50,746 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 13:50:50,746 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 13:50:50,746 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 13:50:50,751 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,756 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,766 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 84 [2025-03-03 13:50:50,767 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 13:50:50,768 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 13:50:50,768 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 13:50:50,768 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 13:50:50,772 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,772 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,778 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,785 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2025-03-03 13:50:50,785 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,785 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,787 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,788 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,788 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,789 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,789 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 13:50:50,790 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 13:50:50,790 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 13:50:50,790 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 13:50:50,791 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50" (1/1) ... [2025-03-03 13:50:50,795 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 13:50:50,804 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:50,813 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-03 13:50:50,818 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-03 13:50:50,829 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 13:50:50,830 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-03 13:50:50,830 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-03 13:50:50,830 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 13:50:50,830 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 13:50:50,830 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 13:50:50,830 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-03 13:50:50,830 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-03 13:50:50,871 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 13:50:50,873 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 13:50:50,987 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2025-03-03 13:50:50,987 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 13:50:50,993 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 13:50:50,993 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 13:50:50,993 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 01:50:50 BoogieIcfgContainer [2025-03-03 13:50:50,994 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 13:50:50,995 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 13:50:50,995 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 13:50:50,998 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 13:50:50,998 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 01:50:50" (1/3) ... [2025-03-03 13:50:50,998 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3e0ccd08 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 01:50:50, skipping insertion in model container [2025-03-03 13:50:50,999 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:50:50" (2/3) ... [2025-03-03 13:50:50,999 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3e0ccd08 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 01:50:50, skipping insertion in model container [2025-03-03 13:50:50,999 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 01:50:50" (3/3) ... [2025-03-03 13:50:51,000 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound50.c [2025-03-03 13:50:51,008 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 13:50:51,011 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd2-ll_unwindbound50.c that has 3 procedures, 34 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-03 13:50:51,050 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 13:50:51,057 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;@4c4b5fda, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 13:50:51,057 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-03 13:50:51,060 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-03 13:50:51,063 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-03 13:50:51,064 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:51,064 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-03 13:50:51,064 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:51,067 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:51,067 INFO L85 PathProgramCache]: Analyzing trace with hash 100709880, now seen corresponding path program 1 times [2025-03-03 13:50:51,072 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:51,072 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1344771216] [2025-03-03 13:50:51,072 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:51,073 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:51,121 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:50:51,131 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:50:51,131 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:51,131 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:51,181 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-03 13:50:51,182 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:51,183 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1344771216] [2025-03-03 13:50:51,183 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1344771216] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:51,183 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1370416726] [2025-03-03 13:50:51,183 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:51,184 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:51,184 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:51,186 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:50:51,187 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-03 13:50:51,230 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:50:51,253 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:50:51,254 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:51,254 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:51,257 INFO L256 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-03 13:50:51,259 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:51,269 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-03 13:50:51,271 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:51,271 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1370416726] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:51,272 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:51,272 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-03 13:50:51,274 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [438921117] [2025-03-03 13:50:51,274 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:51,276 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-03 13:50:51,277 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:51,290 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-03 13:50:51,291 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-03 13:50:51,292 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-03 13:50:51,306 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:51,308 INFO L93 Difference]: Finished difference Result 65 states and 104 transitions. [2025-03-03 13:50:51,308 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-03 13:50:51,309 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-03 13:50:51,309 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:51,313 INFO L225 Difference]: With dead ends: 65 [2025-03-03 13:50:51,315 INFO L226 Difference]: Without dead ends: 30 [2025-03-03 13:50:51,317 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-03 13:50:51,319 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-03 13:50:51,320 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-03 13:50:51,330 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2025-03-03 13:50:51,338 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2025-03-03 13:50:51,338 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-03 13:50:51,341 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 41 transitions. [2025-03-03 13:50:51,342 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 41 transitions. Word has length 28 [2025-03-03 13:50:51,343 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:51,343 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 41 transitions. [2025-03-03 13:50:51,343 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-03 13:50:51,344 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 41 transitions. [2025-03-03 13:50:51,344 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-03 13:50:51,344 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:51,345 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-03 13:50:51,351 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-03 13:50:51,549 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2025-03-03 13:50:51,549 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:51,549 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:51,550 INFO L85 PathProgramCache]: Analyzing trace with hash -1726789354, now seen corresponding path program 1 times [2025-03-03 13:50:51,550 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:51,550 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [610714563] [2025-03-03 13:50:51,550 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:51,550 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:51,560 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-03 13:50:51,574 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-03 13:50:51,575 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:51,575 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:51,671 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-03 13:50:51,672 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:51,672 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [610714563] [2025-03-03 13:50:51,673 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [610714563] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:51,675 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:51,675 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-03 13:50:51,675 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [281778018] [2025-03-03 13:50:51,675 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:51,675 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-03 13:50:51,676 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:51,676 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-03 13:50:51,676 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-03 13:50:51,676 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-03 13:50:51,697 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:51,697 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2025-03-03 13:50:51,698 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-03 13:50:51,698 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-03 13:50:51,698 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:51,699 INFO L225 Difference]: With dead ends: 40 [2025-03-03 13:50:51,700 INFO L226 Difference]: Without dead ends: 32 [2025-03-03 13:50:51,700 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-03 13:50:51,701 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-03 13:50:51,701 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-03 13:50:51,702 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2025-03-03 13:50:51,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2025-03-03 13:50:51,709 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-03 13:50:51,710 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 43 transitions. [2025-03-03 13:50:51,711 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 43 transitions. Word has length 29 [2025-03-03 13:50:51,712 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:51,712 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 43 transitions. [2025-03-03 13:50:51,712 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-03 13:50:51,712 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 43 transitions. [2025-03-03 13:50:51,713 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2025-03-03 13:50:51,713 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:51,714 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-03 13:50:51,714 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-03 13:50:51,714 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:51,714 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:51,714 INFO L85 PathProgramCache]: Analyzing trace with hash -2044305484, now seen corresponding path program 1 times [2025-03-03 13:50:51,714 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:51,714 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [673619252] [2025-03-03 13:50:51,715 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:51,715 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:51,720 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-03 13:50:51,734 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-03 13:50:51,734 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:51,734 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:51,868 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-03 13:50:51,868 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:51,868 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [673619252] [2025-03-03 13:50:51,868 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [673619252] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:51,868 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [287760016] [2025-03-03 13:50:51,868 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:51,868 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:51,869 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:51,872 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:50:51,873 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-03 13:50:51,898 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 30 statements into 1 equivalence classes. [2025-03-03 13:50:51,912 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 30 of 30 statements. [2025-03-03 13:50:51,912 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:51,912 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:51,913 INFO L256 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 13:50:51,914 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:52,025 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-03 13:50:52,025 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:52,025 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [287760016] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:52,025 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:52,025 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2025-03-03 13:50:52,026 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1822714804] [2025-03-03 13:50:52,026 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:52,026 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-03 13:50:52,027 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:52,028 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-03 13:50:52,028 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2025-03-03 13:50:52,028 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-03 13:50:52,099 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:52,099 INFO L93 Difference]: Finished difference Result 49 states and 67 transitions. [2025-03-03 13:50:52,100 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-03 13:50:52,100 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-03 13:50:52,100 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:52,101 INFO L225 Difference]: With dead ends: 49 [2025-03-03 13:50:52,101 INFO L226 Difference]: Without dead ends: 47 [2025-03-03 13:50:52,101 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-03 13:50:52,102 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-03 13:50:52,102 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-03 13:50:52,102 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2025-03-03 13:50:52,107 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 45. [2025-03-03 13:50:52,107 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-03 13:50:52,108 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 63 transitions. [2025-03-03 13:50:52,108 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 63 transitions. Word has length 30 [2025-03-03 13:50:52,108 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:52,108 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 63 transitions. [2025-03-03 13:50:52,108 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-03 13:50:52,109 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 63 transitions. [2025-03-03 13:50:52,109 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-03 13:50:52,109 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:52,109 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-03 13:50:52,119 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-03 13:50:52,314 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-03 13:50:52,314 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:52,315 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:52,315 INFO L85 PathProgramCache]: Analyzing trace with hash -886820372, now seen corresponding path program 1 times [2025-03-03 13:50:52,315 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:52,315 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1541262860] [2025-03-03 13:50:52,315 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:52,315 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:52,320 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-03 13:50:52,327 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-03 13:50:52,327 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:52,327 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:52,328 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [159907640] [2025-03-03 13:50:52,329 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:52,329 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:52,329 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:52,331 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:50:52,333 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-03 13:50:52,358 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-03 13:50:52,376 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-03 13:50:52,376 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:52,376 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:52,377 INFO L256 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-03 13:50:52,378 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:52,413 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-03 13:50:52,414 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:52,414 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:52,414 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1541262860] [2025-03-03 13:50:52,414 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:52,414 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [159907640] [2025-03-03 13:50:52,414 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [159907640] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:52,414 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:52,414 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:50:52,414 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1280809261] [2025-03-03 13:50:52,414 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:52,415 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:52,415 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:52,415 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:52,415 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:50:52,415 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-03 13:50:52,459 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:52,459 INFO L93 Difference]: Finished difference Result 66 states and 95 transitions. [2025-03-03 13:50:52,460 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:52,460 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-03 13:50:52,460 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:52,461 INFO L225 Difference]: With dead ends: 66 [2025-03-03 13:50:52,461 INFO L226 Difference]: Without dead ends: 64 [2025-03-03 13:50:52,462 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-03 13:50:52,462 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-03 13:50:52,462 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-03 13:50:52,465 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2025-03-03 13:50:52,471 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 55. [2025-03-03 13:50:52,472 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-03 13:50:52,472 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 76 transitions. [2025-03-03 13:50:52,472 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 76 transitions. Word has length 32 [2025-03-03 13:50:52,473 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:52,473 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 76 transitions. [2025-03-03 13:50:52,473 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-03 13:50:52,473 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 76 transitions. [2025-03-03 13:50:52,473 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-03 13:50:52,473 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:52,473 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-03 13:50:52,479 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-03 13:50:52,674 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-03 13:50:52,674 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:52,674 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:52,674 INFO L85 PathProgramCache]: Analyzing trace with hash -276176331, now seen corresponding path program 1 times [2025-03-03 13:50:52,675 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:52,675 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [573602279] [2025-03-03 13:50:52,675 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:52,675 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:52,679 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-03 13:50:52,683 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-03 13:50:52,684 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:52,684 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:52,753 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-03 13:50:52,754 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:52,754 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [573602279] [2025-03-03 13:50:52,754 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [573602279] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:52,754 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1524549052] [2025-03-03 13:50:52,754 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:52,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:52,754 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:52,756 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:50:52,757 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-03 13:50:52,778 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-03 13:50:52,789 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-03 13:50:52,789 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:52,789 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:52,790 INFO L256 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-03 13:50:52,791 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:52,872 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-03 13:50:52,872 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:52,872 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1524549052] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:52,872 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:52,872 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2025-03-03 13:50:52,872 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1979843868] [2025-03-03 13:50:52,872 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:52,872 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:52,872 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:52,873 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:52,873 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2025-03-03 13:50:52,873 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-03 13:50:52,907 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:52,907 INFO L93 Difference]: Finished difference Result 63 states and 83 transitions. [2025-03-03 13:50:52,907 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:52,907 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-03 13:50:52,908 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:52,908 INFO L225 Difference]: With dead ends: 63 [2025-03-03 13:50:52,908 INFO L226 Difference]: Without dead ends: 59 [2025-03-03 13:50:52,909 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-03 13:50:52,909 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-03 13:50:52,909 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-03 13:50:52,910 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-03-03 13:50:52,915 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2025-03-03 13:50:52,915 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-03 13:50:52,916 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 76 transitions. [2025-03-03 13:50:52,916 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 76 transitions. Word has length 35 [2025-03-03 13:50:52,916 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:52,916 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 76 transitions. [2025-03-03 13:50:52,916 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-03 13:50:52,916 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 76 transitions. [2025-03-03 13:50:52,917 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-03 13:50:52,917 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:52,917 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-03 13:50:52,923 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-03 13:50:53,117 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-03 13:50:53,117 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:53,118 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:53,118 INFO L85 PathProgramCache]: Analyzing trace with hash -247836027, now seen corresponding path program 1 times [2025-03-03 13:50:53,118 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:53,118 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [562602441] [2025-03-03 13:50:53,118 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:53,118 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:53,122 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 35 statements into 1 equivalence classes. [2025-03-03 13:50:53,126 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 35 of 35 statements. [2025-03-03 13:50:53,126 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:53,126 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:53,159 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-03 13:50:53,159 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:53,159 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [562602441] [2025-03-03 13:50:53,159 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [562602441] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:53,159 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:53,159 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:50:53,159 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1759191917] [2025-03-03 13:50:53,159 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:53,160 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:53,160 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:53,160 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:53,160 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:50:53,160 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-03 13:50:53,177 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:53,178 INFO L93 Difference]: Finished difference Result 84 states and 111 transitions. [2025-03-03 13:50:53,178 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:53,178 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-03 13:50:53,178 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:53,179 INFO L225 Difference]: With dead ends: 84 [2025-03-03 13:50:53,179 INFO L226 Difference]: Without dead ends: 58 [2025-03-03 13:50:53,179 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-03 13:50:53,179 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-03 13:50:53,180 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-03 13:50:53,180 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2025-03-03 13:50:53,188 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2025-03-03 13:50:53,188 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-03 13:50:53,191 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2025-03-03 13:50:53,191 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 35 [2025-03-03 13:50:53,191 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:53,191 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2025-03-03 13:50:53,194 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-03 13:50:53,194 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2025-03-03 13:50:53,194 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-03-03 13:50:53,194 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:53,194 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-03 13:50:53,194 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2025-03-03 13:50:53,194 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:53,195 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:53,195 INFO L85 PathProgramCache]: Analyzing trace with hash -1535941731, now seen corresponding path program 1 times [2025-03-03 13:50:53,195 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:53,195 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [781874105] [2025-03-03 13:50:53,195 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:53,195 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:53,201 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-03 13:50:53,209 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-03 13:50:53,209 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:53,209 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:53,210 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [444699941] [2025-03-03 13:50:53,210 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:53,210 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:53,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:53,213 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:50:53,213 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-03 13:50:53,240 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-03 13:50:53,255 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-03 13:50:53,255 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:53,255 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:53,256 INFO L256 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 13:50:53,257 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:53,387 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-03 13:50:53,387 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:50:53,388 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:53,388 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [781874105] [2025-03-03 13:50:53,388 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:53,388 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [444699941] [2025-03-03 13:50:53,389 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [444699941] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:50:53,389 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:50:53,389 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:50:53,389 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1028406686] [2025-03-03 13:50:53,389 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:50:53,389 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:50:53,390 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:53,390 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:50:53,390 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:50:53,390 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-03 13:50:53,438 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:53,438 INFO L93 Difference]: Finished difference Result 65 states and 81 transitions. [2025-03-03 13:50:53,438 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 13:50:53,438 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-03 13:50:53,439 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:53,439 INFO L225 Difference]: With dead ends: 65 [2025-03-03 13:50:53,439 INFO L226 Difference]: Without dead ends: 63 [2025-03-03 13:50:53,439 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-03 13:50:53,440 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-03 13:50:53,440 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-03 13:50:53,440 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2025-03-03 13:50:53,447 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2025-03-03 13:50:53,447 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-03 13:50:53,450 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 78 transitions. [2025-03-03 13:50:53,450 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 78 transitions. Word has length 47 [2025-03-03 13:50:53,450 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:53,450 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 78 transitions. [2025-03-03 13:50:53,450 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-03 13:50:53,450 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 78 transitions. [2025-03-03 13:50:53,452 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-03-03 13:50:53,452 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:53,453 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-03 13:50:53,459 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-03 13:50:53,653 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:53,653 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:53,654 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:53,654 INFO L85 PathProgramCache]: Analyzing trace with hash 101798249, now seen corresponding path program 1 times [2025-03-03 13:50:53,654 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:53,654 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1704464646] [2025-03-03 13:50:53,654 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:53,654 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:53,672 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-03 13:50:53,683 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-03 13:50:53,683 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:53,684 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:53,684 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [421741372] [2025-03-03 13:50:53,684 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:53,684 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:53,684 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:53,688 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:50:53,689 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-03 13:50:53,713 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-03-03 13:50:53,731 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-03-03 13:50:53,731 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:53,731 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:53,731 INFO L256 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 13:50:53,733 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:53,797 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-03 13:50:53,797 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:53,891 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-03 13:50:53,892 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:53,892 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1704464646] [2025-03-03 13:50:53,892 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:53,893 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [421741372] [2025-03-03 13:50:53,893 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [421741372] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:50:53,893 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:50:53,893 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2025-03-03 13:50:53,893 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1454905497] [2025-03-03 13:50:53,894 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:53,894 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-03 13:50:53,894 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:53,894 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-03 13:50:53,894 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-03 13:50:53,894 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-03 13:50:53,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:53,966 INFO L93 Difference]: Finished difference Result 92 states and 127 transitions. [2025-03-03 13:50:53,967 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-03 13:50:53,967 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-03 13:50:53,968 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:53,968 INFO L225 Difference]: With dead ends: 92 [2025-03-03 13:50:53,968 INFO L226 Difference]: Without dead ends: 90 [2025-03-03 13:50:53,968 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-03 13:50:53,969 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 9 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s 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-03 13:50:53,969 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-03 13:50:53,969 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2025-03-03 13:50:53,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 58. [2025-03-03 13:50:53,982 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-03 13:50:53,982 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 71 transitions. [2025-03-03 13:50:53,984 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 71 transitions. Word has length 55 [2025-03-03 13:50:53,985 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:53,985 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 71 transitions. [2025-03-03 13:50:53,985 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-03 13:50:53,985 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 71 transitions. [2025-03-03 13:50:53,985 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2025-03-03 13:50:53,985 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:53,985 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-03 13:50:53,992 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-03 13:50:54,186 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-03 13:50:54,186 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:54,186 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:54,186 INFO L85 PathProgramCache]: Analyzing trace with hash -1244697335, now seen corresponding path program 1 times [2025-03-03 13:50:54,186 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:54,186 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1878114614] [2025-03-03 13:50:54,186 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:54,186 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:54,190 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-03 13:50:54,197 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-03 13:50:54,197 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:54,197 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:54,252 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-03 13:50:54,252 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:54,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1878114614] [2025-03-03 13:50:54,252 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1878114614] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:54,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [445094347] [2025-03-03 13:50:54,252 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:54,252 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:54,253 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:54,254 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:50:54,256 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-03 13:50:54,280 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 56 statements into 1 equivalence classes. [2025-03-03 13:50:54,296 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 56 of 56 statements. [2025-03-03 13:50:54,296 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:54,296 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:54,299 INFO L256 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-03 13:50:54,301 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:54,356 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-03 13:50:54,356 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:54,442 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-03 13:50:54,443 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [445094347] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:50:54,443 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 13:50:54,443 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2025-03-03 13:50:54,443 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1923129524] [2025-03-03 13:50:54,443 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:54,443 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-03 13:50:54,443 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:54,444 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-03 13:50:54,444 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2025-03-03 13:50:54,444 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-03 13:50:54,577 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:54,577 INFO L93 Difference]: Finished difference Result 211 states and 250 transitions. [2025-03-03 13:50:54,578 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-03 13:50:54,578 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-03 13:50:54,578 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:54,579 INFO L225 Difference]: With dead ends: 211 [2025-03-03 13:50:54,579 INFO L226 Difference]: Without dead ends: 203 [2025-03-03 13:50:54,580 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-03 13:50:54,580 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-03 13:50:54,580 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-03 13:50:54,581 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2025-03-03 13:50:54,602 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 195. [2025-03-03 13:50:54,603 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-03 13:50:54,606 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 195 states to 195 states and 233 transitions. [2025-03-03 13:50:54,607 INFO L78 Accepts]: Start accepts. Automaton has 195 states and 233 transitions. Word has length 56 [2025-03-03 13:50:54,607 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:54,607 INFO L471 AbstractCegarLoop]: Abstraction has 195 states and 233 transitions. [2025-03-03 13:50:54,607 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-03 13:50:54,607 INFO L276 IsEmpty]: Start isEmpty. Operand 195 states and 233 transitions. [2025-03-03 13:50:54,608 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2025-03-03 13:50:54,608 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:54,608 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-03 13:50:54,615 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-03 13:50:54,808 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-03 13:50:54,809 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:54,809 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:54,809 INFO L85 PathProgramCache]: Analyzing trace with hash 15645217, now seen corresponding path program 1 times [2025-03-03 13:50:54,809 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:54,809 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2145966730] [2025-03-03 13:50:54,809 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:54,809 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:54,813 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-03-03 13:50:54,821 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-03-03 13:50:54,821 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:54,821 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:54,921 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-03 13:50:54,921 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:54,921 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2145966730] [2025-03-03 13:50:54,921 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2145966730] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:54,921 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1325556857] [2025-03-03 13:50:54,921 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:54,921 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:54,922 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:54,923 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:50:54,925 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-03 13:50:54,947 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 57 statements into 1 equivalence classes. [2025-03-03 13:50:54,965 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 57 of 57 statements. [2025-03-03 13:50:54,965 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:54,965 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:54,966 INFO L256 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-03 13:50:54,967 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:54,999 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-03 13:50:54,999 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:55,091 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-03 13:50:55,092 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1325556857] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:50:55,092 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 13:50:55,092 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-03 13:50:55,092 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1769657673] [2025-03-03 13:50:55,092 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:55,093 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-03 13:50:55,094 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:55,094 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-03 13:50:55,094 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-03 13:50:55,094 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-03 13:50:55,239 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:55,240 INFO L93 Difference]: Finished difference Result 279 states and 364 transitions. [2025-03-03 13:50:55,240 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-03 13:50:55,240 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-03 13:50:55,241 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:55,242 INFO L225 Difference]: With dead ends: 279 [2025-03-03 13:50:55,242 INFO L226 Difference]: Without dead ends: 259 [2025-03-03 13:50:55,244 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-03 13:50:55,245 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-03 13:50:55,245 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-03 13:50:55,246 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states. [2025-03-03 13:50:55,276 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 235. [2025-03-03 13:50:55,277 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-03 13:50:55,278 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 299 transitions. [2025-03-03 13:50:55,279 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 299 transitions. Word has length 57 [2025-03-03 13:50:55,279 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:55,279 INFO L471 AbstractCegarLoop]: Abstraction has 235 states and 299 transitions. [2025-03-03 13:50:55,279 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-03 13:50:55,279 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 299 transitions. [2025-03-03 13:50:55,280 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2025-03-03 13:50:55,280 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:55,280 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-03 13:50:55,287 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-03-03 13:50:55,481 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-03 13:50:55,481 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:55,482 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:55,482 INFO L85 PathProgramCache]: Analyzing trace with hash -351822558, now seen corresponding path program 1 times [2025-03-03 13:50:55,482 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:55,482 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [567370551] [2025-03-03 13:50:55,482 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:55,482 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:55,487 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 59 statements into 1 equivalence classes. [2025-03-03 13:50:55,494 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 59 of 59 statements. [2025-03-03 13:50:55,494 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:55,494 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:55,540 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-03 13:50:55,540 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:55,540 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [567370551] [2025-03-03 13:50:55,541 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [567370551] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:55,541 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1961993154] [2025-03-03 13:50:55,541 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:55,541 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:55,541 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:55,543 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:50:55,544 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-03 13:50:55,567 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 59 statements into 1 equivalence classes. [2025-03-03 13:50:55,581 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 59 of 59 statements. [2025-03-03 13:50:55,581 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:55,581 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:55,582 INFO L256 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-03 13:50:55,583 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:55,641 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-03 13:50:55,642 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:55,704 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-03 13:50:55,705 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1961993154] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:50:55,705 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 13:50:55,705 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2025-03-03 13:50:55,705 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [814692067] [2025-03-03 13:50:55,705 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:55,705 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-03 13:50:55,705 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:55,706 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-03 13:50:55,706 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2025-03-03 13:50:55,706 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-03 13:50:55,835 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:55,835 INFO L93 Difference]: Finished difference Result 344 states and 448 transitions. [2025-03-03 13:50:55,836 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-03 13:50:55,836 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-03 13:50:55,836 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:55,837 INFO L225 Difference]: With dead ends: 344 [2025-03-03 13:50:55,838 INFO L226 Difference]: Without dead ends: 248 [2025-03-03 13:50:55,838 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 114 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2025-03-03 13:50:55,838 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-03 13:50:55,839 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-03 13:50:55,839 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 248 states. [2025-03-03 13:50:55,859 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 248 to 244. [2025-03-03 13:50:55,860 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-03 13:50:55,861 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 244 states to 244 states and 302 transitions. [2025-03-03 13:50:55,861 INFO L78 Accepts]: Start accepts. Automaton has 244 states and 302 transitions. Word has length 59 [2025-03-03 13:50:55,861 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:55,862 INFO L471 AbstractCegarLoop]: Abstraction has 244 states and 302 transitions. [2025-03-03 13:50:55,862 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-03 13:50:55,862 INFO L276 IsEmpty]: Start isEmpty. Operand 244 states and 302 transitions. [2025-03-03 13:50:55,862 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2025-03-03 13:50:55,862 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:55,862 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-03 13:50:55,868 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-03 13:50:56,067 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-03 13:50:56,067 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:56,067 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:56,067 INFO L85 PathProgramCache]: Analyzing trace with hash -1287548176, now seen corresponding path program 1 times [2025-03-03 13:50:56,067 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:56,067 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1995533355] [2025-03-03 13:50:56,067 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:56,067 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:56,071 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-03-03 13:50:56,078 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-03-03 13:50:56,079 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:56,079 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:56,079 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1866147786] [2025-03-03 13:50:56,079 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:56,079 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:56,080 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:56,081 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:50:56,083 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-03 13:50:56,106 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-03-03 13:50:56,123 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-03-03 13:50:56,123 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:56,123 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:56,124 INFO L256 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 17 conjuncts are in the unsatisfiable core [2025-03-03 13:50:56,125 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:56,234 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-03 13:50:56,234 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:56,262 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:56,262 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1995533355] [2025-03-03 13:50:56,262 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:56,262 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1866147786] [2025-03-03 13:50:56,262 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1866147786] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:56,262 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:56,262 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2025-03-03 13:50:56,262 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [51113389] [2025-03-03 13:50:56,262 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:56,263 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-03 13:50:56,263 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:56,263 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-03 13:50:56,263 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2025-03-03 13:50:56,263 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-03 13:50:56,342 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:56,342 INFO L93 Difference]: Finished difference Result 283 states and 355 transitions. [2025-03-03 13:50:56,342 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-03 13:50:56,342 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-03 13:50:56,343 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:56,344 INFO L225 Difference]: With dead ends: 283 [2025-03-03 13:50:56,344 INFO L226 Difference]: Without dead ends: 278 [2025-03-03 13:50:56,344 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-03 13:50:56,344 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-03 13:50:56,345 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-03 13:50:56,345 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 278 states. [2025-03-03 13:50:56,372 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 278 to 276. [2025-03-03 13:50:56,372 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-03 13:50:56,373 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 276 states to 276 states and 343 transitions. [2025-03-03 13:50:56,374 INFO L78 Accepts]: Start accepts. Automaton has 276 states and 343 transitions. Word has length 64 [2025-03-03 13:50:56,374 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:56,374 INFO L471 AbstractCegarLoop]: Abstraction has 276 states and 343 transitions. [2025-03-03 13:50:56,374 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-03 13:50:56,374 INFO L276 IsEmpty]: Start isEmpty. Operand 276 states and 343 transitions. [2025-03-03 13:50:56,375 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2025-03-03 13:50:56,375 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:56,375 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-03 13:50:56,381 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-03-03 13:50:56,575 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-03 13:50:56,575 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:56,575 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:56,576 INFO L85 PathProgramCache]: Analyzing trace with hash 691051449, now seen corresponding path program 2 times [2025-03-03 13:50:56,576 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:56,576 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1868293628] [2025-03-03 13:50:56,576 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 13:50:56,576 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:56,580 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 69 statements into 2 equivalence classes. [2025-03-03 13:50:56,589 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 69 of 69 statements. [2025-03-03 13:50:56,589 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 13:50:56,589 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:56,590 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2105525094] [2025-03-03 13:50:56,590 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 13:50:56,590 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:56,590 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:56,594 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:50:56,595 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-03 13:50:56,621 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 69 statements into 2 equivalence classes. [2025-03-03 13:50:56,638 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 69 of 69 statements. [2025-03-03 13:50:56,638 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 13:50:56,638 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:56,639 INFO L256 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 23 conjuncts are in the unsatisfiable core [2025-03-03 13:50:56,640 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:56,820 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-03 13:50:56,820 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:56,898 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:56,898 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1868293628] [2025-03-03 13:50:56,898 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:56,898 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2105525094] [2025-03-03 13:50:56,898 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2105525094] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:56,898 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:56,898 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2025-03-03 13:50:56,898 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1703199302] [2025-03-03 13:50:56,898 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:56,898 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-03 13:50:56,898 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:56,899 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-03 13:50:56,899 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-03 13:50:56,899 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-03 13:50:57,022 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:57,022 INFO L93 Difference]: Finished difference Result 291 states and 357 transitions. [2025-03-03 13:50:57,023 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-03 13:50:57,023 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-03 13:50:57,023 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:57,024 INFO L225 Difference]: With dead ends: 291 [2025-03-03 13:50:57,024 INFO L226 Difference]: Without dead ends: 289 [2025-03-03 13:50:57,025 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-03 13:50:57,025 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-03 13:50:57,025 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-03 13:50:57,025 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 289 states. [2025-03-03 13:50:57,055 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 289 to 288. [2025-03-03 13:50:57,056 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-03 13:50:57,057 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 288 states to 288 states and 352 transitions. [2025-03-03 13:50:57,057 INFO L78 Accepts]: Start accepts. Automaton has 288 states and 352 transitions. Word has length 69 [2025-03-03 13:50:57,058 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:57,058 INFO L471 AbstractCegarLoop]: Abstraction has 288 states and 352 transitions. [2025-03-03 13:50:57,058 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-03 13:50:57,058 INFO L276 IsEmpty]: Start isEmpty. Operand 288 states and 352 transitions. [2025-03-03 13:50:57,058 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2025-03-03 13:50:57,058 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:57,058 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-03 13:50:57,064 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-03-03 13:50:57,259 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-03 13:50:57,259 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:57,259 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:57,260 INFO L85 PathProgramCache]: Analyzing trace with hash 239571152, now seen corresponding path program 3 times [2025-03-03 13:50:57,260 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:57,260 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [920061480] [2025-03-03 13:50:57,260 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 13:50:57,260 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:57,265 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 74 statements into 5 equivalence classes. [2025-03-03 13:50:57,284 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 74 of 74 statements. [2025-03-03 13:50:57,284 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-03 13:50:57,284 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:57,285 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1453340217] [2025-03-03 13:50:57,285 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 13:50:57,285 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:57,285 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:57,287 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:50:57,288 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-03 13:50:57,315 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 74 statements into 5 equivalence classes. [2025-03-03 13:50:57,331 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 54 of 74 statements. [2025-03-03 13:50:57,331 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-03 13:50:57,331 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:57,332 INFO L256 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 42 conjuncts are in the unsatisfiable core [2025-03-03 13:50:57,334 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:57,696 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-03 13:50:57,696 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:57,908 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:57,908 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [920061480] [2025-03-03 13:50:57,908 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:57,908 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1453340217] [2025-03-03 13:50:57,908 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1453340217] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:50:57,908 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 13:50:57,909 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2025-03-03 13:50:57,909 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1077879535] [2025-03-03 13:50:57,909 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:57,909 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-03 13:50:57,909 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:57,909 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-03 13:50:57,909 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=231, Unknown=0, NotChecked=0, Total=272 [2025-03-03 13:50:57,910 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-03 13:50:58,150 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:50:58,151 INFO L93 Difference]: Finished difference Result 303 states and 366 transitions. [2025-03-03 13:50:58,151 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-03 13:50:58,151 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-03 13:50:58,151 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:50:58,152 INFO L225 Difference]: With dead ends: 303 [2025-03-03 13:50:58,152 INFO L226 Difference]: Without dead ends: 299 [2025-03-03 13:50:58,153 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-03 13:50:58,153 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-03 13:50:58,154 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-03 13:50:58,154 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 299 states. [2025-03-03 13:50:58,178 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 299 to 298. [2025-03-03 13:50:58,178 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-03 13:50:58,179 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 298 states to 298 states and 359 transitions. [2025-03-03 13:50:58,180 INFO L78 Accepts]: Start accepts. Automaton has 298 states and 359 transitions. Word has length 74 [2025-03-03 13:50:58,180 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:50:58,180 INFO L471 AbstractCegarLoop]: Abstraction has 298 states and 359 transitions. [2025-03-03 13:50:58,180 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-03 13:50:58,180 INFO L276 IsEmpty]: Start isEmpty. Operand 298 states and 359 transitions. [2025-03-03 13:50:58,181 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2025-03-03 13:50:58,181 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:50:58,181 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-03 13:50:58,186 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-03 13:50:58,385 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-03 13:50:58,385 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:50:58,385 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:50:58,386 INFO L85 PathProgramCache]: Analyzing trace with hash 852496708, now seen corresponding path program 1 times [2025-03-03 13:50:58,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:50:58,386 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2103623365] [2025-03-03 13:50:58,386 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:58,386 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:50:58,390 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 80 statements into 1 equivalence classes. [2025-03-03 13:50:58,398 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 80 of 80 statements. [2025-03-03 13:50:58,398 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:58,398 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:50:58,399 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [942896947] [2025-03-03 13:50:58,399 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:50:58,399 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:50:58,399 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:50:58,401 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-03 13:50:58,402 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-03 13:50:58,429 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 80 statements into 1 equivalence classes. [2025-03-03 13:50:58,447 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 80 of 80 statements. [2025-03-03 13:50:58,448 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:50:58,448 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:50:58,449 INFO L256 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 41 conjuncts are in the unsatisfiable core [2025-03-03 13:50:58,450 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:50:58,844 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-03 13:50:58,844 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:50:59,126 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-03 13:50:59,127 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:50:59,127 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2103623365] [2025-03-03 13:50:59,127 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:50:59,128 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [942896947] [2025-03-03 13:50:59,128 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [942896947] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:50:59,128 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:50:59,128 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2025-03-03 13:50:59,128 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [959926722] [2025-03-03 13:50:59,128 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:50:59,128 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-03 13:50:59,128 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:50:59,129 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-03 13:50:59,129 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2025-03-03 13:50:59,129 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-03 13:51:01,200 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:51:01,200 INFO L93 Difference]: Finished difference Result 435 states and 581 transitions. [2025-03-03 13:51:01,201 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-03-03 13:51:01,201 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-03 13:51:01,201 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:51:01,203 INFO L225 Difference]: With dead ends: 435 [2025-03-03 13:51:01,203 INFO L226 Difference]: Without dead ends: 428 [2025-03-03 13:51:01,203 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 139 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 265 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=296, Invalid=1264, Unknown=0, NotChecked=0, Total=1560 [2025-03-03 13:51:01,204 INFO L435 NwaCegarLoop]: 61 mSDtfsCounter, 134 mSDsluCounter, 700 mSDsCounter, 0 mSdLazyCounter, 559 mSolverCounterSat, 131 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s 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.5s IncrementalHoareTripleChecker+Time [2025-03-03 13:51:01,204 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.5s Time] [2025-03-03 13:51:01,204 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 428 states. [2025-03-03 13:51:01,263 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 428 to 391. [2025-03-03 13:51:01,264 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-03 13:51:01,265 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 391 states to 391 states and 513 transitions. [2025-03-03 13:51:01,266 INFO L78 Accepts]: Start accepts. Automaton has 391 states and 513 transitions. Word has length 80 [2025-03-03 13:51:01,266 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:51:01,266 INFO L471 AbstractCegarLoop]: Abstraction has 391 states and 513 transitions. [2025-03-03 13:51:01,266 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-03 13:51:01,266 INFO L276 IsEmpty]: Start isEmpty. Operand 391 states and 513 transitions. [2025-03-03 13:51:01,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2025-03-03 13:51:01,267 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:51:01,267 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-03 13:51:01,272 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-03 13:51:01,467 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-03 13:51:01,467 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:51:01,467 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:51:01,468 INFO L85 PathProgramCache]: Analyzing trace with hash 2042434077, now seen corresponding path program 4 times [2025-03-03 13:51:01,468 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:51:01,468 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [517131622] [2025-03-03 13:51:01,468 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-03 13:51:01,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:51:01,472 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 91 statements into 2 equivalence classes. [2025-03-03 13:51:01,476 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 81 of 91 statements. [2025-03-03 13:51:01,476 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-03 13:51:01,476 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:51:01,525 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-03 13:51:01,526 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:51:01,526 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [517131622] [2025-03-03 13:51:01,526 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [517131622] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:51:01,526 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:51:01,526 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:51:01,526 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1693235198] [2025-03-03 13:51:01,526 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:51:01,526 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 13:51:01,526 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:51:01,527 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 13:51:01,527 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:51:01,527 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-03 13:51:01,625 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:51:01,626 INFO L93 Difference]: Finished difference Result 587 states and 831 transitions. [2025-03-03 13:51:01,626 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-03 13:51:01,626 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-03 13:51:01,626 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:51:01,629 INFO L225 Difference]: With dead ends: 587 [2025-03-03 13:51:01,629 INFO L226 Difference]: Without dead ends: 462 [2025-03-03 13:51:01,629 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-03 13:51:01,630 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-03 13:51:01,630 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-03 13:51:01,630 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 462 states. [2025-03-03 13:51:01,695 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 462 to 410. [2025-03-03 13:51:01,695 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-03 13:51:01,697 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 410 states to 410 states and 545 transitions. [2025-03-03 13:51:01,697 INFO L78 Accepts]: Start accepts. Automaton has 410 states and 545 transitions. Word has length 91 [2025-03-03 13:51:01,697 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:51:01,697 INFO L471 AbstractCegarLoop]: Abstraction has 410 states and 545 transitions. [2025-03-03 13:51:01,698 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-03 13:51:01,698 INFO L276 IsEmpty]: Start isEmpty. Operand 410 states and 545 transitions. [2025-03-03 13:51:01,698 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2025-03-03 13:51:01,698 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:51:01,698 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-03 13:51:01,698 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15 [2025-03-03 13:51:01,699 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:51:01,699 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:51:01,699 INFO L85 PathProgramCache]: Analyzing trace with hash 777061389, now seen corresponding path program 1 times [2025-03-03 13:51:01,699 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:51:01,699 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2091335428] [2025-03-03 13:51:01,699 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:51:01,699 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:51:01,703 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 97 statements into 1 equivalence classes. [2025-03-03 13:51:01,711 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 97 of 97 statements. [2025-03-03 13:51:01,712 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:51:01,712 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 13:51:01,712 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1302846083] [2025-03-03 13:51:01,712 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:51:01,713 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:51:01,713 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:51:01,714 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-03 13:51:01,716 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-03 13:51:01,743 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 97 statements into 1 equivalence classes. [2025-03-03 13:51:01,765 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 97 of 97 statements. [2025-03-03 13:51:01,766 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:51:01,766 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:51:01,767 INFO L256 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 53 conjuncts are in the unsatisfiable core [2025-03-03 13:51:01,770 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:51:02,470 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-03 13:51:02,470 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:51:42,984 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-03 13:51:42,984 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:51:42,984 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2091335428] [2025-03-03 13:51:42,984 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 13:51:42,984 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1302846083] [2025-03-03 13:51:42,984 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1302846083] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:51:42,984 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:51:42,984 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 26 [2025-03-03 13:51:42,984 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1762692182] [2025-03-03 13:51:42,984 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:51:42,985 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-03-03 13:51:42,985 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:51:42,985 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-03-03 13:51:42,985 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=538, Unknown=1, NotChecked=0, Total=650 [2025-03-03 13:51:42,985 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-03 13:51:50,774 WARN L286 SmtUtils]: Spent 7.11s 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-03 13:51:56,519 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-03 13:52:12,742 WARN L286 SmtUtils]: Spent 8.17s on a formula simplification. DAG size of input: 64 DAG size of output: 63 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-03-03 13:52:16,760 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 [] [2025-03-03 13:52:27,002 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 [] [2025-03-03 13:52:31,025 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 []