./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8fc3dc66 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/egcd3-ll_valuebound5.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 1aca3c96522e618238f11f200c96e0ec490e756d4e04895bd2a51f9a4ff85af1 --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 18:11:20,023 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 18:11:20,079 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-16 18:11:20,084 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 18:11:20,085 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 18:11:20,103 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 18:11:20,105 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 18:11:20,105 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 18:11:20,105 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 18:11:20,106 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 18:11:20,106 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 18:11:20,106 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 18:11:20,106 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 18:11:20,106 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 18:11:20,107 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 18:11:20,107 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 18:11:20,107 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 18:11:20,107 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 18:11:20,108 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 18:11:20,108 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 18:11:20,108 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 18:11:20,108 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 18:11:20,108 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 18:11:20,108 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 18:11:20,108 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 18:11:20,108 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 18:11:20,108 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 18:11:20,108 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 18:11:20,108 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 18:11:20,108 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 18:11:20,109 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 18:11:20,109 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 18:11:20,109 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:11:20,109 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 18:11:20,109 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 18:11:20,109 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 18:11:20,109 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 18:11:20,109 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 18:11:20,109 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 18:11:20,109 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 18:11:20,110 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 18:11:20,110 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 18:11:20,110 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 18:11:20,110 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 -> 1aca3c96522e618238f11f200c96e0ec490e756d4e04895bd2a51f9a4ff85af1 [2025-03-16 18:11:20,294 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 18:11:20,299 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 18:11:20,300 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 18:11:20,301 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 18:11:20,301 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 18:11:20,302 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound5.c [2025-03-16 18:11:21,417 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a41a51474/ba89bcf4eb644ea8a25490285ac034c0/FLAG2fd16be22 [2025-03-16 18:11:21,662 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 18:11:21,663 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound5.c [2025-03-16 18:11:21,671 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a41a51474/ba89bcf4eb644ea8a25490285ac034c0/FLAG2fd16be22 [2025-03-16 18:11:21,687 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a41a51474/ba89bcf4eb644ea8a25490285ac034c0 [2025-03-16 18:11:21,690 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 18:11:21,691 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 18:11:21,693 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 18:11:21,694 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 18:11:21,697 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 18:11:21,698 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,699 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@14d91769 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21, skipping insertion in model container [2025-03-16 18:11:21,699 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,710 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 18:11:21,812 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/egcd3-ll_valuebound5.c[490,503] [2025-03-16 18:11:21,830 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:11:21,841 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 18:11:21,849 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/egcd3-ll_valuebound5.c[490,503] [2025-03-16 18:11:21,857 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:11:21,866 INFO L204 MainTranslator]: Completed translation [2025-03-16 18:11:21,867 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21 WrapperNode [2025-03-16 18:11:21,867 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 18:11:21,868 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 18:11:21,869 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 18:11:21,869 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 18:11:21,873 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,877 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,889 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 74 [2025-03-16 18:11:21,889 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 18:11:21,889 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 18:11:21,889 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 18:11:21,889 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 18:11:21,896 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,897 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,901 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,912 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-16 18:11:21,914 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,914 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,918 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,920 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,921 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,921 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,922 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 18:11:21,923 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 18:11:21,923 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 18:11:21,923 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 18:11:21,924 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21" (1/1) ... [2025-03-16 18:11:21,927 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:11:21,936 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:21,947 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-16 18:11:21,952 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-16 18:11:21,971 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 18:11:21,972 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-16 18:11:21,972 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-16 18:11:21,972 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 18:11:21,972 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 18:11:21,972 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 18:11:21,972 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-16 18:11:21,972 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-16 18:11:22,017 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 18:11:22,019 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 18:11:22,160 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2025-03-16 18:11:22,160 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 18:11:22,166 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 18:11:22,168 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 18:11:22,169 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:11:22 BoogieIcfgContainer [2025-03-16 18:11:22,169 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 18:11:22,171 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 18:11:22,171 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 18:11:22,174 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 18:11:22,174 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 06:11:21" (1/3) ... [2025-03-16 18:11:22,175 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b02ca63 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:11:22, skipping insertion in model container [2025-03-16 18:11:22,175 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:11:21" (2/3) ... [2025-03-16 18:11:22,175 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b02ca63 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:11:22, skipping insertion in model container [2025-03-16 18:11:22,176 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:11:22" (3/3) ... [2025-03-16 18:11:22,177 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound5.c [2025-03-16 18:11:22,188 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 18:11:22,189 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd3-ll_valuebound5.c that has 3 procedures, 30 locations, 1 initial locations, 3 loop locations, and 1 error locations. [2025-03-16 18:11:22,226 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 18:11:22,233 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;@4e644483, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 18:11:22,234 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 18:11:22,237 INFO L276 IsEmpty]: Start isEmpty. Operand has 30 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-16 18:11:22,241 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-16 18:11:22,241 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:22,242 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-16 18:11:22,242 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:22,246 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:22,247 INFO L85 PathProgramCache]: Analyzing trace with hash -1461292294, now seen corresponding path program 1 times [2025-03-16 18:11:22,251 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:22,252 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [333463231] [2025-03-16 18:11:22,252 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:22,252 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:22,300 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-16 18:11:22,324 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-16 18:11:22,324 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:22,325 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:22,527 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:11:22,528 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:22,528 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [333463231] [2025-03-16 18:11:22,529 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [333463231] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:22,529 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:22,529 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2025-03-16 18:11:22,530 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1885194648] [2025-03-16 18:11:22,530 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:22,533 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-16 18:11:22,533 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:22,547 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-16 18:11:22,547 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-16 18:11:22,549 INFO L87 Difference]: Start difference. First operand has 30 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:22,649 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:22,649 INFO L93 Difference]: Finished difference Result 67 states and 117 transitions. [2025-03-16 18:11:22,650 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:22,651 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2025-03-16 18:11:22,651 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:22,655 INFO L225 Difference]: With dead ends: 67 [2025-03-16 18:11:22,655 INFO L226 Difference]: Without dead ends: 36 [2025-03-16 18:11:22,657 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:11:22,658 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 22 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:22,659 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 119 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:11:22,670 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2025-03-16 18:11:22,685 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 28. [2025-03-16 18:11:22,689 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-16 18:11:22,691 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2025-03-16 18:11:22,692 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 28 [2025-03-16 18:11:22,693 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:22,693 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2025-03-16 18:11:22,693 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:22,693 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2025-03-16 18:11:22,694 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-03-16 18:11:22,694 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:22,694 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-16 18:11:22,694 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-16 18:11:22,694 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:22,695 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:22,695 INFO L85 PathProgramCache]: Analyzing trace with hash 1979049318, now seen corresponding path program 1 times [2025-03-16 18:11:22,695 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:22,695 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1909019783] [2025-03-16 18:11:22,695 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:22,695 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:22,704 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-16 18:11:22,718 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 18:11:22,719 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:22,719 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:22,722 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1396720535] [2025-03-16 18:11:22,722 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:22,722 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:22,722 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:22,727 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-16 18:11:22,727 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-16 18:11:22,759 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-03-16 18:11:22,770 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-03-16 18:11:22,770 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:22,770 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:22,772 INFO L256 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:11:22,776 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:22,865 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-16 18:11:22,865 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:22,865 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:22,865 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1909019783] [2025-03-16 18:11:22,866 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:22,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1396720535] [2025-03-16 18:11:22,866 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1396720535] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:22,866 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:22,866 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:22,867 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [249279004] [2025-03-16 18:11:22,867 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:22,867 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:22,867 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:22,868 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:22,868 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:22,868 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 5 states, 5 states have (on average 2.2) 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-16 18:11:22,907 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:22,909 INFO L93 Difference]: Finished difference Result 42 states and 56 transitions. [2025-03-16 18:11:22,909 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:22,909 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) 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-16 18:11:22,909 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:22,910 INFO L225 Difference]: With dead ends: 42 [2025-03-16 18:11:22,910 INFO L226 Difference]: Without dead ends: 40 [2025-03-16 18:11:22,911 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 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-16 18:11:22,911 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 7 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:22,912 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 118 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:22,912 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-03-16 18:11:22,917 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2025-03-16 18:11:22,917 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2025-03-16 18:11:22,918 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 53 transitions. [2025-03-16 18:11:22,918 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 53 transitions. Word has length 29 [2025-03-16 18:11:22,918 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:22,918 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 53 transitions. [2025-03-16 18:11:22,918 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) 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-16 18:11:22,918 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 53 transitions. [2025-03-16 18:11:22,920 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-16 18:11:22,920 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:22,921 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] [2025-03-16 18:11:22,927 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-16 18:11:23,125 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:23,125 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:23,125 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:23,125 INFO L85 PathProgramCache]: Analyzing trace with hash 351925117, now seen corresponding path program 1 times [2025-03-16 18:11:23,126 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:23,126 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [755394962] [2025-03-16 18:11:23,126 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:23,126 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:23,131 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:11:23,143 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:11:23,144 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:23,144 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:23,257 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:11:23,258 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:23,258 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [755394962] [2025-03-16 18:11:23,258 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [755394962] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:23,258 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [471674908] [2025-03-16 18:11:23,258 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:23,258 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:23,258 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:23,260 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-16 18:11:23,261 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-16 18:11:23,284 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-16 18:11:23,296 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-16 18:11:23,297 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:23,297 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:23,297 INFO L256 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:11:23,299 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:23,326 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:11:23,327 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:23,410 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-16 18:11:23,412 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [471674908] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:23,412 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:11:23,412 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-16 18:11:23,412 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [247917322] [2025-03-16 18:11:23,412 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:23,412 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-16 18:11:23,412 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:23,413 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-16 18:11:23,413 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:11:23,414 INFO L87 Difference]: Start difference. First operand 39 states and 53 transitions. Second operand has 9 states, 9 states have (on average 2.0) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-16 18:11:23,563 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:23,565 INFO L93 Difference]: Finished difference Result 81 states and 121 transitions. [2025-03-16 18:11:23,565 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-16 18:11:23,565 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.0) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 31 [2025-03-16 18:11:23,565 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:23,566 INFO L225 Difference]: With dead ends: 81 [2025-03-16 18:11:23,566 INFO L226 Difference]: Without dead ends: 74 [2025-03-16 18:11:23,568 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 57 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2025-03-16 18:11:23,568 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 44 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 116 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:23,569 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 169 Invalid, 116 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:11:23,569 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2025-03-16 18:11:23,580 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 53. [2025-03-16 18:11:23,580 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 32 states have (on average 1.375) internal successors, (44), 33 states have internal predecessors, (44), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-16 18:11:23,582 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 77 transitions. [2025-03-16 18:11:23,582 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 77 transitions. Word has length 31 [2025-03-16 18:11:23,582 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:23,583 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 77 transitions. [2025-03-16 18:11:23,583 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.0) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-16 18:11:23,583 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 77 transitions. [2025-03-16 18:11:23,583 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-16 18:11:23,583 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:23,583 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] [2025-03-16 18:11:23,590 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:23,788 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-16 18:11:23,788 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:23,788 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:23,788 INFO L85 PathProgramCache]: Analyzing trace with hash -1940753085, now seen corresponding path program 1 times [2025-03-16 18:11:23,788 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:23,788 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1009824606] [2025-03-16 18:11:23,789 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:23,789 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:23,793 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-16 18:11:23,803 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-16 18:11:23,803 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:23,803 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:23,803 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [275635208] [2025-03-16 18:11:23,805 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:23,805 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:23,805 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:23,807 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:23,807 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-16 18:11:23,828 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-16 18:11:23,840 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-16 18:11:23,840 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:23,840 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:23,841 INFO L256 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 15 conjuncts are in the unsatisfiable core [2025-03-16 18:11:23,842 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:23,915 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:23,915 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:24,030 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:24,030 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:24,030 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1009824606] [2025-03-16 18:11:24,030 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:24,030 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [275635208] [2025-03-16 18:11:24,030 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [275635208] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:24,030 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:24,030 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2025-03-16 18:11:24,031 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1710442891] [2025-03-16 18:11:24,031 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:24,031 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-03-16 18:11:24,031 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:24,031 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-16 18:11:24,031 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:24,032 INFO L87 Difference]: Start difference. First operand 53 states and 77 transitions. Second operand has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:24,120 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:24,120 INFO L93 Difference]: Finished difference Result 82 states and 119 transitions. [2025-03-16 18:11:24,121 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:24,121 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2025-03-16 18:11:24,121 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:24,122 INFO L225 Difference]: With dead ends: 82 [2025-03-16 18:11:24,122 INFO L226 Difference]: Without dead ends: 80 [2025-03-16 18:11:24,122 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 54 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:11:24,123 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 17 mSDsluCounter, 190 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 240 SdHoareTripleChecker+Invalid, 87 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:24,123 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 240 Invalid, 87 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:11:24,127 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-03-16 18:11:24,137 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 76. [2025-03-16 18:11:24,138 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 76 states, 46 states have (on average 1.391304347826087) internal successors, (64), 47 states have internal predecessors, (64), 25 states have call successors, (25), 4 states have call predecessors, (25), 4 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2025-03-16 18:11:24,138 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 113 transitions. [2025-03-16 18:11:24,139 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 113 transitions. Word has length 32 [2025-03-16 18:11:24,139 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:24,139 INFO L471 AbstractCegarLoop]: Abstraction has 76 states and 113 transitions. [2025-03-16 18:11:24,139 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-16 18:11:24,139 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 113 transitions. [2025-03-16 18:11:24,140 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2025-03-16 18:11:24,140 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:24,140 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:24,145 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-16 18:11:24,344 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-16 18:11:24,344 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:24,344 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:24,344 INFO L85 PathProgramCache]: Analyzing trace with hash -908329914, now seen corresponding path program 2 times [2025-03-16 18:11:24,344 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:24,345 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1054855044] [2025-03-16 18:11:24,345 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:24,345 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:24,350 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 35 statements into 2 equivalence classes. [2025-03-16 18:11:24,356 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 35 of 35 statements. [2025-03-16 18:11:24,356 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:24,356 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:24,424 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:24,424 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:24,424 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1054855044] [2025-03-16 18:11:24,424 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1054855044] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:24,424 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:24,424 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:24,424 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2127498155] [2025-03-16 18:11:24,425 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:24,425 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:24,425 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:24,425 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:24,425 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:24,425 INFO L87 Difference]: Start difference. First operand 76 states and 113 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-16 18:11:24,493 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:24,493 INFO L93 Difference]: Finished difference Result 115 states and 177 transitions. [2025-03-16 18:11:24,494 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:11:24,494 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-16 18:11:24,494 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:24,496 INFO L225 Difference]: With dead ends: 115 [2025-03-16 18:11:24,497 INFO L226 Difference]: Without dead ends: 86 [2025-03-16 18:11:24,497 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-16 18:11:24,497 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 13 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:24,498 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 118 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:24,499 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2025-03-16 18:11:24,511 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 57. [2025-03-16 18:11:24,513 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 35 states have (on average 1.2857142857142858) internal successors, (45), 36 states have internal predecessors, (45), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2025-03-16 18:11:24,513 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 78 transitions. [2025-03-16 18:11:24,514 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 78 transitions. Word has length 35 [2025-03-16 18:11:24,515 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:24,515 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 78 transitions. [2025-03-16 18:11:24,515 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-16 18:11:24,515 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 78 transitions. [2025-03-16 18:11:24,515 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-03-16 18:11:24,515 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:24,515 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:24,515 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2025-03-16 18:11:24,515 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:24,516 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:24,516 INFO L85 PathProgramCache]: Analyzing trace with hash -1361869309, now seen corresponding path program 1 times [2025-03-16 18:11:24,516 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:24,516 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1679487408] [2025-03-16 18:11:24,516 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:24,516 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:24,521 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-16 18:11:24,534 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-16 18:11:24,535 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:24,535 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:24,536 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1437740815] [2025-03-16 18:11:24,537 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:24,537 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:24,537 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:24,539 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-16 18:11:24,541 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-16 18:11:24,565 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-03-16 18:11:24,578 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-03-16 18:11:24,578 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:24,578 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:24,579 INFO L256 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-03-16 18:11:24,580 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:24,698 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-16 18:11:24,699 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:24,734 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:24,734 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1679487408] [2025-03-16 18:11:24,735 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:24,735 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1437740815] [2025-03-16 18:11:24,735 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1437740815] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:24,735 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:24,735 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2025-03-16 18:11:24,735 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [534957710] [2025-03-16 18:11:24,735 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:24,735 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-16 18:11:24,735 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:24,736 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-16 18:11:24,736 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:24,736 INFO L87 Difference]: Start difference. First operand 57 states and 78 transitions. Second operand has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 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-16 18:11:24,847 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:24,848 INFO L93 Difference]: Finished difference Result 78 states and 109 transitions. [2025-03-16 18:11:24,848 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-16 18:11:24,848 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 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 37 [2025-03-16 18:11:24,848 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:24,849 INFO L225 Difference]: With dead ends: 78 [2025-03-16 18:11:24,849 INFO L226 Difference]: Without dead ends: 76 [2025-03-16 18:11:24,849 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 33 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2025-03-16 18:11:24,850 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 21 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 173 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:24,850 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 173 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:11:24,850 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2025-03-16 18:11:24,859 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 74. [2025-03-16 18:11:24,860 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 43 states have (on average 1.302325581395349) internal successors, (56), 44 states have internal predecessors, (56), 25 states have call successors, (25), 5 states have call predecessors, (25), 5 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2025-03-16 18:11:24,860 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 105 transitions. [2025-03-16 18:11:24,861 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 105 transitions. Word has length 37 [2025-03-16 18:11:24,861 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:24,861 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 105 transitions. [2025-03-16 18:11:24,861 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 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-16 18:11:24,861 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 105 transitions. [2025-03-16 18:11:24,861 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2025-03-16 18:11:24,862 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:24,862 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:24,890 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:25,066 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:25,066 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:25,066 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:25,066 INFO L85 PathProgramCache]: Analyzing trace with hash -1979591293, now seen corresponding path program 1 times [2025-03-16 18:11:25,066 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:25,066 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1515308] [2025-03-16 18:11:25,066 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:25,067 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:25,070 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 42 statements into 1 equivalence classes. [2025-03-16 18:11:25,079 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 18:11:25,079 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:25,079 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:25,080 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1915500156] [2025-03-16 18:11:25,080 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:25,080 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:25,080 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:25,082 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-16 18:11:25,087 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-16 18:11:25,109 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 42 statements into 1 equivalence classes. [2025-03-16 18:11:25,122 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 42 of 42 statements. [2025-03-16 18:11:25,122 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:25,122 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:25,125 INFO L256 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:11:25,126 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:25,160 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2025-03-16 18:11:25,161 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:25,161 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:25,161 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1515308] [2025-03-16 18:11:25,161 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:25,161 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1915500156] [2025-03-16 18:11:25,162 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1915500156] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:25,162 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:25,162 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:25,162 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [39748862] [2025-03-16 18:11:25,163 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:25,164 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:25,164 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:25,164 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:25,164 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:25,164 INFO L87 Difference]: Start difference. First operand 74 states and 105 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-16 18:11:25,206 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:25,206 INFO L93 Difference]: Finished difference Result 103 states and 147 transitions. [2025-03-16 18:11:25,207 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:25,207 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 42 [2025-03-16 18:11:25,207 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:25,208 INFO L225 Difference]: With dead ends: 103 [2025-03-16 18:11:25,208 INFO L226 Difference]: Without dead ends: 101 [2025-03-16 18:11:25,208 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 38 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-16 18:11:25,209 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 6 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:25,209 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 108 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:25,209 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2025-03-16 18:11:25,221 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 97. [2025-03-16 18:11:25,221 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 52 states have (on average 1.3076923076923077) internal successors, (68), 53 states have internal predecessors, (68), 37 states have call successors, (37), 7 states have call predecessors, (37), 7 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2025-03-16 18:11:25,222 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 141 transitions. [2025-03-16 18:11:25,222 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 141 transitions. Word has length 42 [2025-03-16 18:11:25,222 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:25,222 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 141 transitions. [2025-03-16 18:11:25,223 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-16 18:11:25,223 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 141 transitions. [2025-03-16 18:11:25,223 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2025-03-16 18:11:25,223 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:25,223 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] [2025-03-16 18:11:25,229 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-03-16 18:11:25,428 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-16 18:11:25,428 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:25,429 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:25,429 INFO L85 PathProgramCache]: Analyzing trace with hash 146539456, now seen corresponding path program 1 times [2025-03-16 18:11:25,429 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:25,429 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1290088852] [2025-03-16 18:11:25,429 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:25,429 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:25,432 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-16 18:11:25,436 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-16 18:11:25,436 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:25,436 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:25,437 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [183704771] [2025-03-16 18:11:25,437 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:25,437 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:25,437 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:25,439 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-16 18:11:25,440 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-16 18:11:25,463 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-03-16 18:11:25,485 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-03-16 18:11:25,485 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:25,485 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:25,486 INFO L256 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:11:25,488 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:25,522 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-16 18:11:25,522 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:11:25,523 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:25,523 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1290088852] [2025-03-16 18:11:25,523 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:25,523 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [183704771] [2025-03-16 18:11:25,523 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [183704771] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:11:25,523 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:11:25,523 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:11:25,523 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [919256501] [2025-03-16 18:11:25,523 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:25,524 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:25,524 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:25,524 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:25,524 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:11:25,524 INFO L87 Difference]: Start difference. First operand 97 states and 141 transitions. Second operand has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 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-16 18:11:25,580 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:25,580 INFO L93 Difference]: Finished difference Result 147 states and 230 transitions. [2025-03-16 18:11:25,581 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:25,581 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 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 44 [2025-03-16 18:11:25,581 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:25,582 INFO L225 Difference]: With dead ends: 147 [2025-03-16 18:11:25,582 INFO L226 Difference]: Without dead ends: 145 [2025-03-16 18:11:25,582 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 40 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-16 18:11:25,583 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 4 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:25,583 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 116 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:25,583 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2025-03-16 18:11:25,607 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 133. [2025-03-16 18:11:25,608 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 133 states, 55 states have (on average 1.290909090909091) internal successors, (71), 64 states have internal predecessors, (71), 69 states have call successors, (69), 8 states have call predecessors, (69), 8 states have return successors, (68), 60 states have call predecessors, (68), 68 states have call successors, (68) [2025-03-16 18:11:25,610 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 208 transitions. [2025-03-16 18:11:25,611 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 208 transitions. Word has length 44 [2025-03-16 18:11:25,611 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:25,611 INFO L471 AbstractCegarLoop]: Abstraction has 133 states and 208 transitions. [2025-03-16 18:11:25,611 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 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-16 18:11:25,611 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 208 transitions. [2025-03-16 18:11:25,612 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2025-03-16 18:11:25,614 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:25,614 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:25,619 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-03-16 18:11:25,814 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-16 18:11:25,815 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:25,815 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:25,815 INFO L85 PathProgramCache]: Analyzing trace with hash 89640629, now seen corresponding path program 1 times [2025-03-16 18:11:25,815 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:25,815 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1640414377] [2025-03-16 18:11:25,815 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:25,815 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:25,819 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:11:25,827 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:11:25,827 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:25,827 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:25,828 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1281633694] [2025-03-16 18:11:25,828 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:25,828 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:25,828 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:25,830 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-16 18:11:25,831 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-16 18:11:25,853 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 54 statements into 1 equivalence classes. [2025-03-16 18:11:25,868 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 54 of 54 statements. [2025-03-16 18:11:25,868 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:25,868 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:25,869 INFO L256 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 51 conjuncts are in the unsatisfiable core [2025-03-16 18:11:25,871 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:26,305 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-03-16 18:11:26,305 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:26,642 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-16 18:11:26,643 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:26,643 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1640414377] [2025-03-16 18:11:26,643 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:26,643 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1281633694] [2025-03-16 18:11:26,643 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1281633694] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:26,643 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:26,643 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2025-03-16 18:11:26,643 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [83681286] [2025-03-16 18:11:26,643 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:26,643 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-16 18:11:26,644 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:26,644 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-16 18:11:26,645 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2025-03-16 18:11:26,645 INFO L87 Difference]: Start difference. First operand 133 states and 208 transitions. Second operand has 23 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 20 states have internal predecessors, (32), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2025-03-16 18:11:28,975 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:28,976 INFO L93 Difference]: Finished difference Result 357 states and 579 transitions. [2025-03-16 18:11:28,976 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2025-03-16 18:11:28,977 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 20 states have internal predecessors, (32), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 54 [2025-03-16 18:11:28,977 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:28,980 INFO L225 Difference]: With dead ends: 357 [2025-03-16 18:11:28,980 INFO L226 Difference]: Without dead ends: 275 [2025-03-16 18:11:28,981 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 434 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=398, Invalid=1672, Unknown=0, NotChecked=0, Total=2070 [2025-03-16 18:11:28,981 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 126 mSDsluCounter, 233 mSDsCounter, 0 mSdLazyCounter, 640 mSolverCounterSat, 126 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 255 SdHoareTripleChecker+Invalid, 766 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 126 IncrementalHoareTripleChecker+Valid, 640 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:28,981 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 255 Invalid, 766 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [126 Valid, 640 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2025-03-16 18:11:28,982 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 275 states. [2025-03-16 18:11:29,035 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 275 to 203. [2025-03-16 18:11:29,035 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 203 states, 98 states have (on average 1.316326530612245) internal successors, (129), 105 states have internal predecessors, (129), 93 states have call successors, (93), 11 states have call predecessors, (93), 11 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2025-03-16 18:11:29,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 203 states to 203 states and 314 transitions. [2025-03-16 18:11:29,039 INFO L78 Accepts]: Start accepts. Automaton has 203 states and 314 transitions. Word has length 54 [2025-03-16 18:11:29,039 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:29,039 INFO L471 AbstractCegarLoop]: Abstraction has 203 states and 314 transitions. [2025-03-16 18:11:29,039 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 20 states have internal predecessors, (32), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2025-03-16 18:11:29,039 INFO L276 IsEmpty]: Start isEmpty. Operand 203 states and 314 transitions. [2025-03-16 18:11:29,039 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2025-03-16 18:11:29,040 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:29,040 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:29,048 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-16 18:11:29,240 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-16 18:11:29,240 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:29,241 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:29,241 INFO L85 PathProgramCache]: Analyzing trace with hash 107169448, now seen corresponding path program 1 times [2025-03-16 18:11:29,241 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:29,241 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1048761034] [2025-03-16 18:11:29,241 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:29,241 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:29,244 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-16 18:11:29,253 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 18:11:29,253 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:29,253 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:29,253 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1679340362] [2025-03-16 18:11:29,254 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:29,254 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:29,254 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:29,255 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-16 18:11:29,257 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-16 18:11:29,277 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 58 statements into 1 equivalence classes. [2025-03-16 18:11:29,293 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 58 of 58 statements. [2025-03-16 18:11:29,293 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:29,293 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:29,295 INFO L256 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 49 conjuncts are in the unsatisfiable core [2025-03-16 18:11:29,296 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:29,639 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 16 proven. 21 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2025-03-16 18:11:29,639 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:29,771 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 18 proven. 8 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2025-03-16 18:11:29,771 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:29,771 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1048761034] [2025-03-16 18:11:29,771 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:29,771 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1679340362] [2025-03-16 18:11:29,771 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1679340362] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:29,771 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:29,771 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2025-03-16 18:11:29,772 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [491966898] [2025-03-16 18:11:29,772 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:29,772 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-03-16 18:11:29,772 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:29,772 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-03-16 18:11:29,772 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2025-03-16 18:11:29,772 INFO L87 Difference]: Start difference. First operand 203 states and 314 transitions. Second operand has 22 states, 22 states have (on average 2.0) internal successors, (44), 19 states have internal predecessors, (44), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2025-03-16 18:11:30,803 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:30,803 INFO L93 Difference]: Finished difference Result 254 states and 393 transitions. [2025-03-16 18:11:30,803 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-16 18:11:30,804 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.0) internal successors, (44), 19 states have internal predecessors, (44), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 58 [2025-03-16 18:11:30,804 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:30,806 INFO L225 Difference]: With dead ends: 254 [2025-03-16 18:11:30,807 INFO L226 Difference]: Without dead ends: 252 [2025-03-16 18:11:30,807 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 103 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 194 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=190, Invalid=932, Unknown=0, NotChecked=0, Total=1122 [2025-03-16 18:11:30,808 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 95 mSDsluCounter, 287 mSDsCounter, 0 mSdLazyCounter, 563 mSolverCounterSat, 103 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 97 SdHoareTripleChecker+Valid, 325 SdHoareTripleChecker+Invalid, 666 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 103 IncrementalHoareTripleChecker+Valid, 563 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:30,808 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [97 Valid, 325 Invalid, 666 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [103 Valid, 563 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2025-03-16 18:11:30,809 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 252 states. [2025-03-16 18:11:30,871 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 252 to 211. [2025-03-16 18:11:30,871 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 211 states, 104 states have (on average 1.2980769230769231) internal successors, (135), 111 states have internal predecessors, (135), 93 states have call successors, (93), 13 states have call predecessors, (93), 13 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2025-03-16 18:11:30,872 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 211 states to 211 states and 320 transitions. [2025-03-16 18:11:30,873 INFO L78 Accepts]: Start accepts. Automaton has 211 states and 320 transitions. Word has length 58 [2025-03-16 18:11:30,873 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:30,873 INFO L471 AbstractCegarLoop]: Abstraction has 211 states and 320 transitions. [2025-03-16 18:11:30,873 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.0) internal successors, (44), 19 states have internal predecessors, (44), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2025-03-16 18:11:30,873 INFO L276 IsEmpty]: Start isEmpty. Operand 211 states and 320 transitions. [2025-03-16 18:11:30,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2025-03-16 18:11:30,874 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:30,874 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:30,879 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-16 18:11:31,078 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-16 18:11:31,078 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:31,078 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:31,078 INFO L85 PathProgramCache]: Analyzing trace with hash 2061499091, now seen corresponding path program 1 times [2025-03-16 18:11:31,078 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:31,078 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [502797245] [2025-03-16 18:11:31,078 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:31,079 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:31,081 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-03-16 18:11:31,088 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-03-16 18:11:31,089 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:31,089 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:31,089 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [579207220] [2025-03-16 18:11:31,089 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:31,089 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:31,089 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:31,091 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-16 18:11:31,093 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-16 18:11:31,112 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-03-16 18:11:31,126 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-03-16 18:11:31,127 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:31,127 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:31,129 INFO L256 TraceCheckSpWp]: Trace formula consists of 160 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-16 18:11:31,131 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:31,177 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 14 proven. 4 refuted. 0 times theorem prover too weak. 108 trivial. 0 not checked. [2025-03-16 18:11:31,177 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:31,228 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2025-03-16 18:11:31,229 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:31,229 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [502797245] [2025-03-16 18:11:31,229 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:31,229 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [579207220] [2025-03-16 18:11:31,229 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [579207220] provided 1 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:31,229 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:31,229 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2025-03-16 18:11:31,229 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [483333978] [2025-03-16 18:11:31,229 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:11:31,229 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:11:31,229 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:31,230 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:11:31,230 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:11:31,230 INFO L87 Difference]: Start difference. First operand 211 states and 320 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, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-16 18:11:31,305 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:31,305 INFO L93 Difference]: Finished difference Result 217 states and 325 transitions. [2025-03-16 18:11:31,305 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:11:31,305 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, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 65 [2025-03-16 18:11:31,306 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:31,307 INFO L225 Difference]: With dead ends: 217 [2025-03-16 18:11:31,307 INFO L226 Difference]: Without dead ends: 215 [2025-03-16 18:11:31,307 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 121 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:11:31,307 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 4 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 112 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-16 18:11:31,308 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 112 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:11:31,308 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2025-03-16 18:11:31,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 215. [2025-03-16 18:11:31,363 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 215 states, 107 states have (on average 1.2897196261682242) internal successors, (138), 114 states have internal predecessors, (138), 93 states have call successors, (93), 14 states have call predecessors, (93), 14 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2025-03-16 18:11:31,365 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 215 states to 215 states and 323 transitions. [2025-03-16 18:11:31,365 INFO L78 Accepts]: Start accepts. Automaton has 215 states and 323 transitions. Word has length 65 [2025-03-16 18:11:31,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:31,365 INFO L471 AbstractCegarLoop]: Abstraction has 215 states and 323 transitions. [2025-03-16 18:11:31,365 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, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2025-03-16 18:11:31,365 INFO L276 IsEmpty]: Start isEmpty. Operand 215 states and 323 transitions. [2025-03-16 18:11:31,366 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2025-03-16 18:11:31,366 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:31,366 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:31,372 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-03-16 18:11:31,567 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-16 18:11:31,567 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:31,567 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:31,567 INFO L85 PathProgramCache]: Analyzing trace with hash 1341574078, now seen corresponding path program 2 times [2025-03-16 18:11:31,567 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:31,567 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [388164179] [2025-03-16 18:11:31,567 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:31,567 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:31,570 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 63 statements into 2 equivalence classes. [2025-03-16 18:11:31,583 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 63 of 63 statements. [2025-03-16 18:11:31,583 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:31,583 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:31,584 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [284936577] [2025-03-16 18:11:31,584 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:31,584 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:31,584 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:31,586 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-16 18:11:31,587 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-16 18:11:31,607 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 63 statements into 2 equivalence classes. [2025-03-16 18:11:31,624 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 63 of 63 statements. [2025-03-16 18:11:31,624 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:31,625 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:31,629 INFO L256 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 65 conjuncts are in the unsatisfiable core [2025-03-16 18:11:31,630 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:32,049 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 18 proven. 25 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2025-03-16 18:11:32,049 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:32,461 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 15 proven. 19 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2025-03-16 18:11:32,461 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:32,461 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [388164179] [2025-03-16 18:11:32,462 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:32,462 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [284936577] [2025-03-16 18:11:32,462 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [284936577] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:32,462 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:32,462 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 15] total 31 [2025-03-16 18:11:32,462 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1853141811] [2025-03-16 18:11:32,462 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:32,462 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2025-03-16 18:11:32,462 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:32,462 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2025-03-16 18:11:32,463 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=791, Unknown=0, NotChecked=0, Total=930 [2025-03-16 18:11:32,463 INFO L87 Difference]: Start difference. First operand 215 states and 323 transitions. Second operand has 31 states, 29 states have (on average 1.5517241379310345) internal successors, (45), 27 states have internal predecessors, (45), 8 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 8 states have call predecessors, (16), 8 states have call successors, (16) [2025-03-16 18:11:36,571 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.28s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-16 18:11:37,536 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:37,536 INFO L93 Difference]: Finished difference Result 399 states and 591 transitions. [2025-03-16 18:11:37,537 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2025-03-16 18:11:37,537 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 29 states have (on average 1.5517241379310345) internal successors, (45), 27 states have internal predecessors, (45), 8 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 8 states have call predecessors, (16), 8 states have call successors, (16) Word has length 63 [2025-03-16 18:11:37,537 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:37,539 INFO L225 Difference]: With dead ends: 399 [2025-03-16 18:11:37,540 INFO L226 Difference]: Without dead ends: 334 [2025-03-16 18:11:37,543 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 95 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 780 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=678, Invalid=2862, Unknown=0, NotChecked=0, Total=3540 [2025-03-16 18:11:37,543 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 144 mSDsluCounter, 359 mSDsCounter, 0 mSdLazyCounter, 939 mSolverCounterSat, 177 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 144 SdHoareTripleChecker+Valid, 386 SdHoareTripleChecker+Invalid, 1116 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 177 IncrementalHoareTripleChecker+Valid, 939 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.5s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:37,543 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [144 Valid, 386 Invalid, 1116 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [177 Valid, 939 Invalid, 0 Unknown, 0 Unchecked, 3.5s Time] [2025-03-16 18:11:37,544 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 334 states. [2025-03-16 18:11:37,654 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 334 to 287. [2025-03-16 18:11:37,655 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 287 states, 144 states have (on average 1.2708333333333333) internal successors, (183), 155 states have internal predecessors, (183), 121 states have call successors, (121), 21 states have call predecessors, (121), 21 states have return successors, (120), 110 states have call predecessors, (120), 120 states have call successors, (120) [2025-03-16 18:11:37,656 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 287 states to 287 states and 424 transitions. [2025-03-16 18:11:37,657 INFO L78 Accepts]: Start accepts. Automaton has 287 states and 424 transitions. Word has length 63 [2025-03-16 18:11:37,657 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:37,657 INFO L471 AbstractCegarLoop]: Abstraction has 287 states and 424 transitions. [2025-03-16 18:11:37,657 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 29 states have (on average 1.5517241379310345) internal successors, (45), 27 states have internal predecessors, (45), 8 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 8 states have call predecessors, (16), 8 states have call successors, (16) [2025-03-16 18:11:37,657 INFO L276 IsEmpty]: Start isEmpty. Operand 287 states and 424 transitions. [2025-03-16 18:11:37,658 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2025-03-16 18:11:37,658 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:37,658 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 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-16 18:11:37,669 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:37,858 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-16 18:11:37,858 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:37,859 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:37,859 INFO L85 PathProgramCache]: Analyzing trace with hash 408526629, now seen corresponding path program 1 times [2025-03-16 18:11:37,859 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:37,859 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [570771828] [2025-03-16 18:11:37,859 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:37,859 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:37,862 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 78 statements into 1 equivalence classes. [2025-03-16 18:11:37,875 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 78 of 78 statements. [2025-03-16 18:11:37,875 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:37,875 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:37,878 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1911743723] [2025-03-16 18:11:37,878 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:11:37,878 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:37,878 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:37,880 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-16 18:11:37,882 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-16 18:11:37,907 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 78 statements into 1 equivalence classes. [2025-03-16 18:11:37,929 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 78 of 78 statements. [2025-03-16 18:11:37,929 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:11:37,929 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:37,931 INFO L256 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 66 conjuncts are in the unsatisfiable core [2025-03-16 18:11:37,932 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:38,582 INFO L134 CoverageAnalysis]: Checked inductivity of 164 backedges. 36 proven. 22 refuted. 0 times theorem prover too weak. 106 trivial. 0 not checked. [2025-03-16 18:11:38,582 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:38,833 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:38,833 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [570771828] [2025-03-16 18:11:38,833 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:38,833 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1911743723] [2025-03-16 18:11:38,833 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1911743723] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:38,833 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:38,833 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2025-03-16 18:11:38,833 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1692814438] [2025-03-16 18:11:38,834 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:38,834 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-16 18:11:38,834 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:38,834 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-16 18:11:38,834 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=664, Unknown=0, NotChecked=0, Total=756 [2025-03-16 18:11:38,835 INFO L87 Difference]: Start difference. First operand 287 states and 424 transitions. Second operand has 21 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 19 states have internal predecessors, (29), 6 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2025-03-16 18:11:39,597 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:39,597 INFO L93 Difference]: Finished difference Result 364 states and 543 transitions. [2025-03-16 18:11:39,597 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-16 18:11:39,597 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 19 states have internal predecessors, (29), 6 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) Word has length 78 [2025-03-16 18:11:39,597 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:39,600 INFO L225 Difference]: With dead ends: 364 [2025-03-16 18:11:39,600 INFO L226 Difference]: Without dead ends: 357 [2025-03-16 18:11:39,600 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 71 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 253 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=165, Invalid=1167, Unknown=0, NotChecked=0, Total=1332 [2025-03-16 18:11:39,601 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 69 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 863 mSolverCounterSat, 62 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 85 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 925 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 863 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:39,601 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [85 Valid, 212 Invalid, 925 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 863 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-03-16 18:11:39,601 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 357 states. [2025-03-16 18:11:39,734 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 357 to 350. [2025-03-16 18:11:39,735 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 350 states, 168 states have (on average 1.2857142857142858) internal successors, (216), 182 states have internal predecessors, (216), 157 states have call successors, (157), 24 states have call predecessors, (157), 24 states have return successors, (156), 143 states have call predecessors, (156), 156 states have call successors, (156) [2025-03-16 18:11:39,736 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 350 states to 350 states and 529 transitions. [2025-03-16 18:11:39,737 INFO L78 Accepts]: Start accepts. Automaton has 350 states and 529 transitions. Word has length 78 [2025-03-16 18:11:39,737 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:39,737 INFO L471 AbstractCegarLoop]: Abstraction has 350 states and 529 transitions. [2025-03-16 18:11:39,737 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 19 states have internal predecessors, (29), 6 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2025-03-16 18:11:39,737 INFO L276 IsEmpty]: Start isEmpty. Operand 350 states and 529 transitions. [2025-03-16 18:11:39,738 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2025-03-16 18:11:39,738 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:39,738 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 3, 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] [2025-03-16 18:11:39,744 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:39,938 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-16 18:11:39,938 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:39,939 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:39,939 INFO L85 PathProgramCache]: Analyzing trace with hash -1408173133, now seen corresponding path program 2 times [2025-03-16 18:11:39,939 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:39,939 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1875498291] [2025-03-16 18:11:39,939 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:39,939 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:39,942 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 83 statements into 2 equivalence classes. [2025-03-16 18:11:39,948 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 83 of 83 statements. [2025-03-16 18:11:39,948 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:39,948 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:40,083 INFO L134 CoverageAnalysis]: Checked inductivity of 177 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2025-03-16 18:11:40,084 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:40,084 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1875498291] [2025-03-16 18:11:40,084 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1875498291] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:40,084 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [332501418] [2025-03-16 18:11:40,084 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:40,084 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:40,084 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:40,086 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-16 18:11:40,087 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-16 18:11:40,112 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 83 statements into 2 equivalence classes. [2025-03-16 18:11:40,145 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 83 of 83 statements. [2025-03-16 18:11:40,146 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:40,146 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:40,146 INFO L256 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-16 18:11:40,148 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:40,207 INFO L134 CoverageAnalysis]: Checked inductivity of 177 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2025-03-16 18:11:40,207 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:40,275 INFO L134 CoverageAnalysis]: Checked inductivity of 177 backedges. 28 proven. 11 refuted. 0 times theorem prover too weak. 138 trivial. 0 not checked. [2025-03-16 18:11:40,275 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [332501418] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:40,275 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:11:40,276 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 13 [2025-03-16 18:11:40,276 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [461735975] [2025-03-16 18:11:40,276 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:40,276 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-16 18:11:40,276 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:40,276 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-16 18:11:40,276 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2025-03-16 18:11:40,276 INFO L87 Difference]: Start difference. First operand 350 states and 529 transitions. Second operand has 13 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2025-03-16 18:11:40,723 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:40,723 INFO L93 Difference]: Finished difference Result 595 states and 893 transitions. [2025-03-16 18:11:40,724 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-16 18:11:40,724 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 83 [2025-03-16 18:11:40,724 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:40,726 INFO L225 Difference]: With dead ends: 595 [2025-03-16 18:11:40,726 INFO L226 Difference]: Without dead ends: 364 [2025-03-16 18:11:40,727 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 199 GetRequests, 162 SyntacticMatches, 8 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 164 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=214, Invalid=716, Unknown=0, NotChecked=0, Total=930 [2025-03-16 18:11:40,728 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 65 mSDsluCounter, 306 mSDsCounter, 0 mSdLazyCounter, 296 mSolverCounterSat, 90 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 351 SdHoareTripleChecker+Invalid, 386 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 90 IncrementalHoareTripleChecker+Valid, 296 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:40,728 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 351 Invalid, 386 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [90 Valid, 296 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 18:11:40,728 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 364 states. [2025-03-16 18:11:40,817 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 364 to 269. [2025-03-16 18:11:40,817 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 269 states, 142 states have (on average 1.2535211267605635) internal successors, (178), 144 states have internal predecessors, (178), 103 states have call successors, (103), 23 states have call predecessors, (103), 23 states have return successors, (102), 101 states have call predecessors, (102), 102 states have call successors, (102) [2025-03-16 18:11:40,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 269 states to 269 states and 383 transitions. [2025-03-16 18:11:40,819 INFO L78 Accepts]: Start accepts. Automaton has 269 states and 383 transitions. Word has length 83 [2025-03-16 18:11:40,820 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:40,820 INFO L471 AbstractCegarLoop]: Abstraction has 269 states and 383 transitions. [2025-03-16 18:11:40,820 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.5384615384615383) internal successors, (33), 13 states have internal predecessors, (33), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2025-03-16 18:11:40,820 INFO L276 IsEmpty]: Start isEmpty. Operand 269 states and 383 transitions. [2025-03-16 18:11:40,821 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2025-03-16 18:11:40,821 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:40,821 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:40,826 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-16 18:11:41,021 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-16 18:11:41,021 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:41,022 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:41,022 INFO L85 PathProgramCache]: Analyzing trace with hash -807522155, now seen corresponding path program 2 times [2025-03-16 18:11:41,022 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:41,022 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [65951588] [2025-03-16 18:11:41,022 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:41,022 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:41,025 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-16 18:11:41,038 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:11:41,038 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:41,038 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:41,039 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1775225551] [2025-03-16 18:11:41,039 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:11:41,039 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:41,039 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:41,042 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-16 18:11:41,043 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-16 18:11:41,065 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 96 statements into 2 equivalence classes. [2025-03-16 18:11:41,087 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 96 of 96 statements. [2025-03-16 18:11:41,087 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:11:41,087 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:41,088 INFO L256 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 47 conjuncts are in the unsatisfiable core [2025-03-16 18:11:41,090 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:41,508 INFO L134 CoverageAnalysis]: Checked inductivity of 329 backedges. 24 proven. 17 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2025-03-16 18:11:41,508 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:41,971 INFO L134 CoverageAnalysis]: Checked inductivity of 329 backedges. 24 proven. 17 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2025-03-16 18:11:41,971 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:41,971 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [65951588] [2025-03-16 18:11:41,972 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:41,972 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1775225551] [2025-03-16 18:11:41,972 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1775225551] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:41,972 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:41,972 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2025-03-16 18:11:41,972 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1742301077] [2025-03-16 18:11:41,972 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:41,972 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-03-16 18:11:41,972 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:41,972 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-03-16 18:11:41,973 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=396, Unknown=0, NotChecked=0, Total=462 [2025-03-16 18:11:41,973 INFO L87 Difference]: Start difference. First operand 269 states and 383 transitions. Second operand has 22 states, 20 states have (on average 1.55) internal successors, (31), 21 states have internal predecessors, (31), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2025-03-16 18:11:46,794 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:46,794 INFO L93 Difference]: Finished difference Result 458 states and 700 transitions. [2025-03-16 18:11:46,795 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2025-03-16 18:11:46,795 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 1.55) internal successors, (31), 21 states have internal predecessors, (31), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 96 [2025-03-16 18:11:46,795 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:46,797 INFO L225 Difference]: With dead ends: 458 [2025-03-16 18:11:46,797 INFO L226 Difference]: Without dead ends: 450 [2025-03-16 18:11:46,798 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 239 GetRequests, 168 SyntacticMatches, 2 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1404 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=867, Invalid=4103, Unknown=0, NotChecked=0, Total=4970 [2025-03-16 18:11:46,799 INFO L435 NwaCegarLoop]: 73 mSDtfsCounter, 119 mSDsluCounter, 850 mSDsCounter, 0 mSdLazyCounter, 1275 mSolverCounterSat, 183 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 123 SdHoareTripleChecker+Valid, 923 SdHoareTripleChecker+Invalid, 1458 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 183 IncrementalHoareTripleChecker+Valid, 1275 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:46,799 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [123 Valid, 923 Invalid, 1458 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [183 Valid, 1275 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2025-03-16 18:11:46,800 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 450 states. [2025-03-16 18:11:46,923 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 450 to 312. [2025-03-16 18:11:46,924 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 312 states, 156 states have (on average 1.2884615384615385) internal successors, (201), 158 states have internal predecessors, (201), 131 states have call successors, (131), 24 states have call predecessors, (131), 24 states have return successors, (130), 129 states have call predecessors, (130), 130 states have call successors, (130) [2025-03-16 18:11:46,925 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 312 states to 312 states and 462 transitions. [2025-03-16 18:11:46,926 INFO L78 Accepts]: Start accepts. Automaton has 312 states and 462 transitions. Word has length 96 [2025-03-16 18:11:46,926 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:46,926 INFO L471 AbstractCegarLoop]: Abstraction has 312 states and 462 transitions. [2025-03-16 18:11:46,926 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 1.55) internal successors, (31), 21 states have internal predecessors, (31), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2025-03-16 18:11:46,926 INFO L276 IsEmpty]: Start isEmpty. Operand 312 states and 462 transitions. [2025-03-16 18:11:46,927 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2025-03-16 18:11:46,927 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:46,927 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:46,934 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2025-03-16 18:11:47,127 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-16 18:11:47,128 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:47,128 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:47,128 INFO L85 PathProgramCache]: Analyzing trace with hash 1069370314, now seen corresponding path program 3 times [2025-03-16 18:11:47,128 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:47,128 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [222793311] [2025-03-16 18:11:47,128 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:11:47,128 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:47,134 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 98 statements into 11 equivalence classes. [2025-03-16 18:11:47,163 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) and asserted 98 of 98 statements. [2025-03-16 18:11:47,163 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2025-03-16 18:11:47,164 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:47,164 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2026848163] [2025-03-16 18:11:47,164 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:11:47,164 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:47,164 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:47,166 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-16 18:11:47,168 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-16 18:11:47,193 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 98 statements into 11 equivalence classes. [2025-03-16 18:11:47,213 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 62 of 98 statements. [2025-03-16 18:11:47,213 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-16 18:11:47,213 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:47,214 INFO L256 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 61 conjuncts are in the unsatisfiable core [2025-03-16 18:11:47,215 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:47,915 INFO L134 CoverageAnalysis]: Checked inductivity of 332 backedges. 55 proven. 27 refuted. 0 times theorem prover too weak. 250 trivial. 0 not checked. [2025-03-16 18:11:47,915 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:48,570 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:48,570 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [222793311] [2025-03-16 18:11:48,570 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:48,573 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2026848163] [2025-03-16 18:11:48,573 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2026848163] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:48,573 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:48,573 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2025-03-16 18:11:48,573 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [939375787] [2025-03-16 18:11:48,573 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:48,573 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-16 18:11:48,573 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:48,574 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-16 18:11:48,574 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=686, Unknown=0, NotChecked=0, Total=812 [2025-03-16 18:11:48,575 INFO L87 Difference]: Start difference. First operand 312 states and 462 transitions. Second operand has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-16 18:11:49,271 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:49,271 INFO L93 Difference]: Finished difference Result 390 states and 568 transitions. [2025-03-16 18:11:49,272 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-16 18:11:49,272 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) Word has length 98 [2025-03-16 18:11:49,272 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:49,274 INFO L225 Difference]: With dead ends: 390 [2025-03-16 18:11:49,274 INFO L226 Difference]: Without dead ends: 383 [2025-03-16 18:11:49,274 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 103 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 273 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=227, Invalid=1105, Unknown=0, NotChecked=0, Total=1332 [2025-03-16 18:11:49,275 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 46 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 517 mSolverCounterSat, 51 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 568 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 517 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:49,275 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [58 Valid, 161 Invalid, 568 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 517 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 18:11:49,275 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 383 states. [2025-03-16 18:11:49,425 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 383 to 373. [2025-03-16 18:11:49,425 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 373 states, 188 states have (on average 1.2872340425531914) internal successors, (242), 190 states have internal predecessors, (242), 155 states have call successors, (155), 29 states have call predecessors, (155), 29 states have return successors, (154), 153 states have call predecessors, (154), 154 states have call successors, (154) [2025-03-16 18:11:49,427 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 373 states to 373 states and 551 transitions. [2025-03-16 18:11:49,427 INFO L78 Accepts]: Start accepts. Automaton has 373 states and 551 transitions. Word has length 98 [2025-03-16 18:11:49,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:49,428 INFO L471 AbstractCegarLoop]: Abstraction has 373 states and 551 transitions. [2025-03-16 18:11:49,428 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 16 states have internal predecessors, (29), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) [2025-03-16 18:11:49,428 INFO L276 IsEmpty]: Start isEmpty. Operand 373 states and 551 transitions. [2025-03-16 18:11:49,429 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2025-03-16 18:11:49,429 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:49,429 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:49,435 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2025-03-16 18:11:49,629 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:49,630 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:49,630 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:49,630 INFO L85 PathProgramCache]: Analyzing trace with hash -215364371, now seen corresponding path program 4 times [2025-03-16 18:11:49,630 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:49,630 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [13373197] [2025-03-16 18:11:49,630 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:11:49,630 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:49,634 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 101 statements into 2 equivalence classes. [2025-03-16 18:11:49,660 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 101 of 101 statements. [2025-03-16 18:11:49,660 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-16 18:11:49,660 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:49,661 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [600472651] [2025-03-16 18:11:49,661 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:11:49,661 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:49,661 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:49,664 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:49,664 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2025-03-16 18:11:49,690 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 101 statements into 2 equivalence classes. [2025-03-16 18:11:49,717 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 99 of 101 statements. [2025-03-16 18:11:49,717 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-16 18:11:49,717 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:49,719 INFO L256 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 70 conjuncts are in the unsatisfiable core [2025-03-16 18:11:49,721 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:50,689 INFO L134 CoverageAnalysis]: Checked inductivity of 338 backedges. 56 proven. 36 refuted. 0 times theorem prover too weak. 246 trivial. 0 not checked. [2025-03-16 18:11:50,689 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:52,422 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:52,422 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [13373197] [2025-03-16 18:11:52,422 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:52,422 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [600472651] [2025-03-16 18:11:52,422 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [600472651] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:11:52,422 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:11:52,422 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2025-03-16 18:11:52,422 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [49972253] [2025-03-16 18:11:52,422 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:52,423 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-16 18:11:52,423 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:52,423 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-16 18:11:52,423 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=160, Invalid=1172, Unknown=0, NotChecked=0, Total=1332 [2025-03-16 18:11:52,423 INFO L87 Difference]: Start difference. First operand 373 states and 551 transitions. Second operand has 23 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 21 states have internal predecessors, (32), 7 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2025-03-16 18:11:54,053 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:11:54,053 INFO L93 Difference]: Finished difference Result 454 states and 665 transitions. [2025-03-16 18:11:54,054 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-03-16 18:11:54,054 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 21 states have internal predecessors, (32), 7 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 101 [2025-03-16 18:11:54,054 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:11:54,058 INFO L225 Difference]: With dead ends: 454 [2025-03-16 18:11:54,058 INFO L226 Difference]: Without dead ends: 447 [2025-03-16 18:11:54,059 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 168 GetRequests, 122 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 505 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=287, Invalid=1969, Unknown=0, NotChecked=0, Total=2256 [2025-03-16 18:11:54,059 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 64 mSDsluCounter, 366 mSDsCounter, 0 mSdLazyCounter, 1081 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 80 SdHoareTripleChecker+Valid, 402 SdHoareTripleChecker+Invalid, 1131 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 1081 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2025-03-16 18:11:54,059 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [80 Valid, 402 Invalid, 1131 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 1081 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2025-03-16 18:11:54,059 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 447 states. [2025-03-16 18:11:54,248 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 447 to 431. [2025-03-16 18:11:54,249 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 431 states, 214 states have (on average 1.294392523364486) internal successors, (277), 216 states have internal predecessors, (277), 183 states have call successors, (183), 33 states have call predecessors, (183), 33 states have return successors, (182), 181 states have call predecessors, (182), 182 states have call successors, (182) [2025-03-16 18:11:54,251 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 431 states to 431 states and 642 transitions. [2025-03-16 18:11:54,252 INFO L78 Accepts]: Start accepts. Automaton has 431 states and 642 transitions. Word has length 101 [2025-03-16 18:11:54,252 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:11:54,252 INFO L471 AbstractCegarLoop]: Abstraction has 431 states and 642 transitions. [2025-03-16 18:11:54,252 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 21 states have internal predecessors, (32), 7 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2025-03-16 18:11:54,252 INFO L276 IsEmpty]: Start isEmpty. Operand 431 states and 642 transitions. [2025-03-16 18:11:54,254 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2025-03-16 18:11:54,254 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:11:54,254 INFO L218 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:11:54,265 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2025-03-16 18:11:54,458 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-03-16 18:11:54,458 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:11:54,458 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:11:54,458 INFO L85 PathProgramCache]: Analyzing trace with hash 311264781, now seen corresponding path program 5 times [2025-03-16 18:11:54,458 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:11:54,458 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1568070384] [2025-03-16 18:11:54,458 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:11:54,458 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:11:54,462 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 101 statements into 8 equivalence classes. [2025-03-16 18:11:54,478 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) and asserted 101 of 101 statements. [2025-03-16 18:11:54,478 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-03-16 18:11:54,478 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:11:54,479 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [162415529] [2025-03-16 18:11:54,479 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:11:54,479 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:11:54,479 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:11:54,482 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:11:54,483 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2025-03-16 18:11:54,511 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 101 statements into 8 equivalence classes. [2025-03-16 18:11:54,566 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) and asserted 101 of 101 statements. [2025-03-16 18:11:54,566 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-03-16 18:11:54,566 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:11:54,568 INFO L256 TraceCheckSpWp]: Trace formula consists of 253 conjuncts, 77 conjuncts are in the unsatisfiable core [2025-03-16 18:11:54,570 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:11:55,201 INFO L134 CoverageAnalysis]: Checked inductivity of 338 backedges. 31 proven. 79 refuted. 0 times theorem prover too weak. 228 trivial. 0 not checked. [2025-03-16 18:11:55,201 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:11:56,226 INFO L134 CoverageAnalysis]: Checked inductivity of 338 backedges. 31 proven. 79 refuted. 0 times theorem prover too weak. 228 trivial. 0 not checked. [2025-03-16 18:11:56,226 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:11:56,226 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1568070384] [2025-03-16 18:11:56,226 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:11:56,226 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [162415529] [2025-03-16 18:11:56,227 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [162415529] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:11:56,227 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:11:56,227 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 35 [2025-03-16 18:11:56,227 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [894268305] [2025-03-16 18:11:56,227 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:11:56,227 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2025-03-16 18:11:56,227 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:11:56,228 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2025-03-16 18:11:56,228 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=151, Invalid=1039, Unknown=0, NotChecked=0, Total=1190 [2025-03-16 18:11:56,228 INFO L87 Difference]: Start difference. First operand 431 states and 642 transitions. Second operand has 35 states, 30 states have (on average 1.6) internal successors, (48), 31 states have internal predecessors, (48), 11 states have call successors, (30), 3 states have call predecessors, (30), 2 states have return successors, (28), 10 states have call predecessors, (28), 9 states have call successors, (28) [2025-03-16 18:12:17,042 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.28s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-16 18:12:27,022 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.19s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-16 18:13:01,266 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 []