./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound2.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/egcd2-ll_valuebound2.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 ebdf8b0d6633d593d56778eaf5218135ab2be92cae14e75cdda2462494f96410 --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 18:09:40,030 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 18:09:40,084 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-16 18:09:40,090 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 18:09:40,090 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 18:09:40,102 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 18:09:40,103 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 18:09:40,103 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 18:09:40,103 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 18:09:40,103 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 18:09:40,104 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 18:09:40,104 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 18:09:40,104 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 18:09:40,104 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 18:09:40,105 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 18:09:40,105 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 18:09:40,105 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 18:09:40,105 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 18:09:40,105 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 18:09:40,105 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 18:09:40,105 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 18:09:40,105 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 18:09:40,105 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 18:09:40,105 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 18:09:40,105 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 18:09:40,105 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 18:09:40,105 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 18:09:40,106 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:09:40,106 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 18:09:40,106 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 18:09:40,106 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 -> ebdf8b0d6633d593d56778eaf5218135ab2be92cae14e75cdda2462494f96410 [2025-03-16 18:09:40,344 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 18:09:40,349 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 18:09:40,353 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 18:09:40,354 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 18:09:40,354 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 18:09:40,355 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound2.c [2025-03-16 18:09:41,504 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/622fdb127/ca65be1d6b99469cba6984f9a2e4c4a9/FLAG51b2c05ce [2025-03-16 18:09:41,800 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 18:09:41,801 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound2.c [2025-03-16 18:09:41,807 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/622fdb127/ca65be1d6b99469cba6984f9a2e4c4a9/FLAG51b2c05ce [2025-03-16 18:09:41,822 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/622fdb127/ca65be1d6b99469cba6984f9a2e4c4a9 [2025-03-16 18:09:41,823 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 18:09:41,825 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 18:09:41,827 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 18:09:41,827 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 18:09:41,830 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 18:09:41,831 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:09:41" (1/1) ... [2025-03-16 18:09:41,832 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@33f67c65 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:41, skipping insertion in model container [2025-03-16 18:09:41,832 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:09:41" (1/1) ... [2025-03-16 18:09:41,843 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 18:09:41,950 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound2.c[490,503] [2025-03-16 18:09:41,970 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:09:41,977 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 18:09:41,984 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound2.c[490,503] [2025-03-16 18:09:41,997 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:09:42,006 INFO L204 MainTranslator]: Completed translation [2025-03-16 18:09:42,007 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:42 WrapperNode [2025-03-16 18:09:42,007 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 18:09:42,009 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 18:09:42,009 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 18:09:42,009 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 18:09:42,013 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:09:42" (1/1) ... [2025-03-16 18:09:42,019 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:09:42" (1/1) ... [2025-03-16 18:09:42,034 INFO L138 Inliner]: procedures = 14, calls = 19, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 73 [2025-03-16 18:09:42,034 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 18:09:42,035 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 18:09:42,035 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 18:09:42,035 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 18:09:42,041 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:42" (1/1) ... [2025-03-16 18:09:42,042 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:42" (1/1) ... [2025-03-16 18:09:42,046 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:42" (1/1) ... [2025-03-16 18:09:42,055 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:09:42,058 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:42" (1/1) ... [2025-03-16 18:09:42,059 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:42" (1/1) ... [2025-03-16 18:09:42,060 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:42" (1/1) ... [2025-03-16 18:09:42,061 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:42" (1/1) ... [2025-03-16 18:09:42,064 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:42" (1/1) ... [2025-03-16 18:09:42,064 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:42" (1/1) ... [2025-03-16 18:09:42,068 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 18:09:42,068 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 18:09:42,069 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 18:09:42,069 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 18:09:42,072 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:42" (1/1) ... [2025-03-16 18:09:42,076 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:09:42,088 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:42,114 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:09:42,120 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:09:42,134 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 18:09:42,134 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-03-16 18:09:42,134 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-03-16 18:09:42,135 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 18:09:42,135 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 18:09:42,135 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 18:09:42,135 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-16 18:09:42,135 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-16 18:09:42,183 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 18:09:42,184 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 18:09:42,319 INFO L? ?]: Removed 10 outVars from TransFormulas that were not future-live. [2025-03-16 18:09:42,319 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 18:09:42,327 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 18:09:42,327 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 18:09:42,328 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:09:42 BoogieIcfgContainer [2025-03-16 18:09:42,328 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 18:09:42,329 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 18:09:42,330 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 18:09:42,333 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 18:09:42,333 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 06:09:41" (1/3) ... [2025-03-16 18:09:42,334 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@620b8c3f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:09:42, skipping insertion in model container [2025-03-16 18:09:42,334 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:09:42" (2/3) ... [2025-03-16 18:09:42,334 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@620b8c3f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:09:42, skipping insertion in model container [2025-03-16 18:09:42,334 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:09:42" (3/3) ... [2025-03-16 18:09:42,335 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd2-ll_valuebound2.c [2025-03-16 18:09:42,345 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 18:09:42,347 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd2-ll_valuebound2.c that has 3 procedures, 31 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2025-03-16 18:09:42,381 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 18:09:42,389 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;@98e5067, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 18:09:42,390 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 18:09:42,392 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2025-03-16 18:09:42,396 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2025-03-16 18:09:42,397 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:42,397 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:42,397 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:42,401 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:42,401 INFO L85 PathProgramCache]: Analyzing trace with hash 948231786, now seen corresponding path program 1 times [2025-03-16 18:09:42,406 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:42,406 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1689237786] [2025-03-16 18:09:42,406 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:42,407 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:42,454 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-16 18:09:42,466 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-16 18:09:42,467 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:42,467 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:42,527 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2025-03-16 18:09:42,528 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:42,528 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1689237786] [2025-03-16 18:09:42,528 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1689237786] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:42,529 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [788808978] [2025-03-16 18:09:42,529 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:42,529 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:42,530 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:42,531 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:09:42,533 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:09:42,578 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-16 18:09:42,599 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-16 18:09:42,599 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:42,599 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:42,601 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-03-16 18:09:42,603 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:42,612 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2025-03-16 18:09:42,615 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:09:42,615 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [788808978] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:09:42,615 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:09:42,615 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-03-16 18:09:42,617 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1126079882] [2025-03-16 18:09:42,617 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:09:42,620 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-16 18:09:42,621 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:42,634 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-16 18:09:42,634 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-16 18:09:42,636 INFO L87 Difference]: Start difference. First operand has 31 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-16 18:09:42,651 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:42,654 INFO L93 Difference]: Finished difference Result 60 states and 101 transitions. [2025-03-16 18:09:42,654 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-16 18:09:42,655 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) Word has length 38 [2025-03-16 18:09:42,655 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:42,659 INFO L225 Difference]: With dead ends: 60 [2025-03-16 18:09:42,659 INFO L226 Difference]: Without dead ends: 28 [2025-03-16 18:09:42,663 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-16 18:09:42,665 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:42,669 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:09:42,679 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2025-03-16 18:09:42,690 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2025-03-16 18:09:42,691 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 15 states have internal predecessors, (16), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-03-16 18:09:42,695 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 39 transitions. [2025-03-16 18:09:42,697 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 39 transitions. Word has length 38 [2025-03-16 18:09:42,698 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:42,698 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 39 transitions. [2025-03-16 18:09:42,698 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-16 18:09:42,698 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 39 transitions. [2025-03-16 18:09:42,699 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2025-03-16 18:09:42,700 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:42,700 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:42,707 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-03-16 18:09:42,905 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2025-03-16 18:09:42,905 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:42,906 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:42,906 INFO L85 PathProgramCache]: Analyzing trace with hash -390224212, now seen corresponding path program 1 times [2025-03-16 18:09:42,906 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:42,906 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1594459622] [2025-03-16 18:09:42,906 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:42,906 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:42,916 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-16 18:09:42,945 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-16 18:09:42,946 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:42,946 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:42,948 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1094896874] [2025-03-16 18:09:42,948 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:42,948 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:42,948 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:42,950 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:09:42,951 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:09:42,989 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-16 18:09:43,019 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-16 18:09:43,019 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:43,019 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:43,020 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-16 18:09:43,022 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:43,082 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2025-03-16 18:09:43,082 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:09:43,082 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:43,082 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1594459622] [2025-03-16 18:09:43,083 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:43,083 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1094896874] [2025-03-16 18:09:43,083 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1094896874] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:09:43,083 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:09:43,083 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:09:43,083 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1585056896] [2025-03-16 18:09:43,083 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:09:43,084 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:09:43,084 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:43,084 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:09:43,084 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:09:43,084 INFO L87 Difference]: Start difference. First operand 28 states and 39 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2025-03-16 18:09:43,138 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:43,139 INFO L93 Difference]: Finished difference Result 40 states and 55 transitions. [2025-03-16 18:09:43,139 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:09:43,139 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 38 [2025-03-16 18:09:43,139 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:43,140 INFO L225 Difference]: With dead ends: 40 [2025-03-16 18:09:43,140 INFO L226 Difference]: Without dead ends: 38 [2025-03-16 18:09:43,140 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 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:09:43,141 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 4 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:43,141 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 124 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:09:43,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2025-03-16 18:09:43,149 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 33. [2025-03-16 18:09:43,150 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 16 states have (on average 1.1875) internal successors, (19), 19 states have internal predecessors, (19), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2025-03-16 18:09:43,151 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 44 transitions. [2025-03-16 18:09:43,151 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 44 transitions. Word has length 38 [2025-03-16 18:09:43,151 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:43,151 INFO L471 AbstractCegarLoop]: Abstraction has 33 states and 44 transitions. [2025-03-16 18:09:43,151 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2025-03-16 18:09:43,151 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2025-03-16 18:09:43,152 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2025-03-16 18:09:43,152 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:43,152 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:43,159 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-16 18:09:43,352 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2025-03-16 18:09:43,353 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:43,353 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:43,353 INFO L85 PathProgramCache]: Analyzing trace with hash -392309582, now seen corresponding path program 1 times [2025-03-16 18:09:43,353 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:43,353 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1642785089] [2025-03-16 18:09:43,353 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:43,353 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:43,359 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-16 18:09:43,373 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-16 18:09:43,373 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:43,373 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:43,524 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-03-16 18:09:43,524 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:43,524 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1642785089] [2025-03-16 18:09:43,525 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1642785089] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:43,525 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [939680959] [2025-03-16 18:09:43,525 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:43,525 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:43,525 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:43,527 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:09:43,529 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:09:43,557 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-03-16 18:09:43,586 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-03-16 18:09:43,587 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:43,587 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:43,590 INFO L256 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-03-16 18:09:43,592 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:43,741 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 3 proven. 12 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-03-16 18:09:43,741 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:43,839 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [939680959] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:43,840 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:09:43,840 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 9] total 11 [2025-03-16 18:09:43,840 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [912251842] [2025-03-16 18:09:43,840 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:43,840 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-16 18:09:43,840 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:43,841 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-16 18:09:43,841 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=174, Unknown=0, NotChecked=0, Total=210 [2025-03-16 18:09:43,841 INFO L87 Difference]: Start difference. First operand 33 states and 44 transitions. Second operand has 11 states, 10 states have (on average 1.7) internal successors, (17), 8 states have internal predecessors, (17), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-16 18:09:44,012 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:44,012 INFO L93 Difference]: Finished difference Result 53 states and 71 transitions. [2025-03-16 18:09:44,013 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-16 18:09:44,013 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 1.7) internal successors, (17), 8 states have internal predecessors, (17), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 38 [2025-03-16 18:09:44,014 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:44,015 INFO L225 Difference]: With dead ends: 53 [2025-03-16 18:09:44,015 INFO L226 Difference]: Without dead ends: 45 [2025-03-16 18:09:44,015 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 36 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=54, Invalid=252, Unknown=0, NotChecked=0, Total=306 [2025-03-16 18:09:44,016 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 25 mSDsluCounter, 189 mSDsCounter, 0 mSdLazyCounter, 161 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 216 SdHoareTripleChecker+Invalid, 186 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 161 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:44,016 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 216 Invalid, 186 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 161 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:44,018 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2025-03-16 18:09:44,025 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 44. [2025-03-16 18:09:44,026 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 24 states have internal predecessors, (25), 18 states have call successors, (18), 4 states have call predecessors, (18), 4 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2025-03-16 18:09:44,026 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 60 transitions. [2025-03-16 18:09:44,027 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 60 transitions. Word has length 38 [2025-03-16 18:09:44,027 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:44,027 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 60 transitions. [2025-03-16 18:09:44,027 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 1.7) internal successors, (17), 8 states have internal predecessors, (17), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2025-03-16 18:09:44,027 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 60 transitions. [2025-03-16 18:09:44,028 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2025-03-16 18:09:44,028 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:44,028 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 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:09:44,034 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-16 18:09:44,228 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:44,229 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:44,229 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:44,229 INFO L85 PathProgramCache]: Analyzing trace with hash -1378011465, now seen corresponding path program 1 times [2025-03-16 18:09:44,229 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:44,229 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1816912304] [2025-03-16 18:09:44,229 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:44,229 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:44,234 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 43 statements into 1 equivalence classes. [2025-03-16 18:09:44,243 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 43 of 43 statements. [2025-03-16 18:09:44,243 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:44,243 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:44,244 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1420455584] [2025-03-16 18:09:44,244 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:44,244 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:44,245 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:44,246 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:09:44,248 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:09:44,271 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 43 statements into 1 equivalence classes. [2025-03-16 18:09:44,283 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 43 of 43 statements. [2025-03-16 18:09:44,284 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:44,284 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:44,284 INFO L256 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:09:44,286 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:44,349 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2025-03-16 18:09:44,349 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:09:44,349 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:44,349 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1816912304] [2025-03-16 18:09:44,349 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:44,349 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1420455584] [2025-03-16 18:09:44,349 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1420455584] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:09:44,349 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:09:44,349 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:09:44,349 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1423541468] [2025-03-16 18:09:44,349 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:09:44,349 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:09:44,349 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:44,350 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:09:44,350 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:09:44,350 INFO L87 Difference]: Start difference. First operand 44 states and 60 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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:09:44,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:44,393 INFO L93 Difference]: Finished difference Result 51 states and 66 transitions. [2025-03-16 18:09:44,394 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:09:44,394 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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 43 [2025-03-16 18:09:44,394 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:44,395 INFO L225 Difference]: With dead ends: 51 [2025-03-16 18:09:44,396 INFO L226 Difference]: Without dead ends: 49 [2025-03-16 18:09:44,396 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 39 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:09:44,396 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 5 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:44,396 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 134 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:09:44,397 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2025-03-16 18:09:44,406 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2025-03-16 18:09:44,406 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 24 states have (on average 1.1666666666666667) internal successors, (28), 27 states have internal predecessors, (28), 18 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2025-03-16 18:09:44,407 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 63 transitions. [2025-03-16 18:09:44,407 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 63 transitions. Word has length 43 [2025-03-16 18:09:44,407 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:44,407 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 63 transitions. [2025-03-16 18:09:44,407 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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:09:44,408 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 63 transitions. [2025-03-16 18:09:44,408 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2025-03-16 18:09:44,408 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:44,408 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:44,414 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-16 18:09:44,613 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:44,613 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:44,614 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:44,614 INFO L85 PathProgramCache]: Analyzing trace with hash 874923031, now seen corresponding path program 1 times [2025-03-16 18:09:44,614 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:44,614 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [115564331] [2025-03-16 18:09:44,614 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:44,614 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:44,622 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 53 statements into 1 equivalence classes. [2025-03-16 18:09:44,639 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 53 of 53 statements. [2025-03-16 18:09:44,639 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:44,639 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:44,640 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1334140648] [2025-03-16 18:09:44,640 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:44,640 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:44,640 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:44,642 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:09:44,644 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:09:44,666 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 53 statements into 1 equivalence classes. [2025-03-16 18:09:44,680 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 53 of 53 statements. [2025-03-16 18:09:44,680 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:44,681 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:44,681 INFO L256 TraceCheckSpWp]: Trace formula consists of 140 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-16 18:09:44,683 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:44,786 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2025-03-16 18:09:44,786 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-16 18:09:44,786 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:44,786 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [115564331] [2025-03-16 18:09:44,786 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:44,786 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1334140648] [2025-03-16 18:09:44,786 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1334140648] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:09:44,787 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:09:44,787 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:09:44,787 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1834959510] [2025-03-16 18:09:44,787 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:09:44,787 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:09:44,787 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:44,787 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:09:44,788 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:09:44,788 INFO L87 Difference]: Start difference. First operand 48 states and 63 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-16 18:09:44,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:44,838 INFO L93 Difference]: Finished difference Result 55 states and 69 transitions. [2025-03-16 18:09:44,839 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:09:44,839 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 53 [2025-03-16 18:09:44,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:44,840 INFO L225 Difference]: With dead ends: 55 [2025-03-16 18:09:44,840 INFO L226 Difference]: Without dead ends: 53 [2025-03-16 18:09:44,840 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 49 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:09:44,840 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 5 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:44,840 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 121 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:09:44,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2025-03-16 18:09:44,849 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 52. [2025-03-16 18:09:44,849 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 30 states have internal predecessors, (31), 18 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2025-03-16 18:09:44,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 66 transitions. [2025-03-16 18:09:44,852 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 66 transitions. Word has length 53 [2025-03-16 18:09:44,852 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:44,852 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 66 transitions. [2025-03-16 18:09:44,852 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2025-03-16 18:09:44,852 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 66 transitions. [2025-03-16 18:09:44,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2025-03-16 18:09:44,853 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:44,853 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:44,860 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:09:45,053 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:45,053 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:45,054 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:45,054 INFO L85 PathProgramCache]: Analyzing trace with hash 1835406633, now seen corresponding path program 1 times [2025-03-16 18:09:45,054 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:45,054 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [899638121] [2025-03-16 18:09:45,054 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:45,054 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:45,059 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 59 statements into 1 equivalence classes. [2025-03-16 18:09:45,078 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 59 of 59 statements. [2025-03-16 18:09:45,078 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:45,078 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:45,079 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [237998813] [2025-03-16 18:09:45,079 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:45,083 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:45,083 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:45,085 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:09:45,086 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:09:45,111 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 59 statements into 1 equivalence classes. [2025-03-16 18:09:45,127 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 59 of 59 statements. [2025-03-16 18:09:45,127 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:45,127 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:45,128 INFO L256 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-16 18:09:45,129 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:45,182 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 8 proven. 1 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2025-03-16 18:09:45,182 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:45,268 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 8 proven. 1 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2025-03-16 18:09:45,269 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:45,269 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [899638121] [2025-03-16 18:09:45,269 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:45,269 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [237998813] [2025-03-16 18:09:45,269 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [237998813] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:09:45,269 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:09:45,269 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2025-03-16 18:09:45,269 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1006105719] [2025-03-16 18:09:45,269 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:45,269 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-16 18:09:45,269 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:45,270 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-16 18:09:45,270 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-03-16 18:09:45,270 INFO L87 Difference]: Start difference. First operand 52 states and 66 transitions. Second operand has 7 states, 5 states have (on average 3.0) internal successors, (15), 6 states have internal predecessors, (15), 4 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2025-03-16 18:09:45,352 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:45,352 INFO L93 Difference]: Finished difference Result 78 states and 109 transitions. [2025-03-16 18:09:45,353 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-16 18:09:45,353 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 5 states have (on average 3.0) internal successors, (15), 6 states have internal predecessors, (15), 4 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 59 [2025-03-16 18:09:45,353 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:45,354 INFO L225 Difference]: With dead ends: 78 [2025-03-16 18:09:45,354 INFO L226 Difference]: Without dead ends: 76 [2025-03-16 18:09:45,354 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 108 SyntacticMatches, 3 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:09:45,354 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 161 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 201 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:45,354 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 201 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:45,355 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2025-03-16 18:09:45,362 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 50. [2025-03-16 18:09:45,362 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 28 states have internal predecessors, (31), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2025-03-16 18:09:45,363 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 62 transitions. [2025-03-16 18:09:45,363 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 62 transitions. Word has length 59 [2025-03-16 18:09:45,363 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:45,363 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 62 transitions. [2025-03-16 18:09:45,363 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 5 states have (on average 3.0) internal successors, (15), 6 states have internal predecessors, (15), 4 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2025-03-16 18:09:45,364 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 62 transitions. [2025-03-16 18:09:45,364 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2025-03-16 18:09:45,364 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:45,364 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:45,370 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:09:45,565 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:45,565 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:45,565 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:45,565 INFO L85 PathProgramCache]: Analyzing trace with hash -194270950, now seen corresponding path program 1 times [2025-03-16 18:09:45,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:45,566 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [589472236] [2025-03-16 18:09:45,566 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:45,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:45,569 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 61 statements into 1 equivalence classes. [2025-03-16 18:09:45,576 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 61 of 61 statements. [2025-03-16 18:09:45,576 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:45,576 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:45,675 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 14 proven. 10 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2025-03-16 18:09:45,675 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:45,675 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [589472236] [2025-03-16 18:09:45,675 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [589472236] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:45,676 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2027651477] [2025-03-16 18:09:45,676 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:45,676 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:45,676 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:45,677 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:09:45,679 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:09:45,701 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 61 statements into 1 equivalence classes. [2025-03-16 18:09:45,716 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 61 of 61 statements. [2025-03-16 18:09:45,716 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:45,716 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:45,717 INFO L256 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-03-16 18:09:45,718 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:45,745 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 14 proven. 10 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2025-03-16 18:09:45,746 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:45,832 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 14 proven. 10 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2025-03-16 18:09:45,832 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2027651477] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:09:45,833 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:09:45,833 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2025-03-16 18:09:45,833 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1778161543] [2025-03-16 18:09:45,833 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:45,833 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-16 18:09:45,833 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:45,833 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-16 18:09:45,834 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-16 18:09:45,834 INFO L87 Difference]: Start difference. First operand 50 states and 62 transitions. Second operand has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2025-03-16 18:09:45,970 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:45,970 INFO L93 Difference]: Finished difference Result 90 states and 130 transitions. [2025-03-16 18:09:45,971 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-16 18:09:45,971 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 61 [2025-03-16 18:09:45,972 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:45,973 INFO L225 Difference]: With dead ends: 90 [2025-03-16 18:09:45,973 INFO L226 Difference]: Without dead ends: 82 [2025-03-16 18:09:45,973 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 117 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:09:45,974 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 23 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 80 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 201 SdHoareTripleChecker+Invalid, 110 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 80 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:45,974 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 201 Invalid, 110 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 80 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:45,974 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2025-03-16 18:09:45,990 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 74. [2025-03-16 18:09:45,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 35 states have (on average 1.2571428571428571) internal successors, (44), 36 states have internal predecessors, (44), 32 states have call successors, (32), 6 states have call predecessors, (32), 6 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2025-03-16 18:09:45,991 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 107 transitions. [2025-03-16 18:09:45,991 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 107 transitions. Word has length 61 [2025-03-16 18:09:45,992 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:45,992 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 107 transitions. [2025-03-16 18:09:45,992 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2025-03-16 18:09:45,992 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 107 transitions. [2025-03-16 18:09:45,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2025-03-16 18:09:45,992 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:45,993 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:45,999 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:09:46,193 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:46,194 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:46,194 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:46,194 INFO L85 PathProgramCache]: Analyzing trace with hash 1863050063, now seen corresponding path program 1 times [2025-03-16 18:09:46,194 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:46,194 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1894278022] [2025-03-16 18:09:46,194 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:46,194 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:46,198 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 66 statements into 1 equivalence classes. [2025-03-16 18:09:46,208 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 66 of 66 statements. [2025-03-16 18:09:46,208 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:46,208 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:46,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1782285665] [2025-03-16 18:09:46,209 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:46,209 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:46,209 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:46,212 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:09:46,213 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:09:46,235 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 66 statements into 1 equivalence classes. [2025-03-16 18:09:46,252 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 66 of 66 statements. [2025-03-16 18:09:46,253 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:46,253 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:46,254 INFO L256 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 29 conjuncts are in the unsatisfiable core [2025-03-16 18:09:46,256 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:46,557 INFO L134 CoverageAnalysis]: Checked inductivity of 113 backedges. 16 proven. 21 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2025-03-16 18:09:46,557 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:46,780 INFO L134 CoverageAnalysis]: Checked inductivity of 113 backedges. 16 proven. 21 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2025-03-16 18:09:46,781 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:46,781 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1894278022] [2025-03-16 18:09:46,781 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:46,781 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1782285665] [2025-03-16 18:09:46,781 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1782285665] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:09:46,781 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:09:46,781 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2025-03-16 18:09:46,781 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2037470415] [2025-03-16 18:09:46,781 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:46,782 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-16 18:09:46,782 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:46,782 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-16 18:09:46,782 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2025-03-16 18:09:46,783 INFO L87 Difference]: Start difference. First operand 74 states and 107 transitions. Second operand has 19 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 14 states have internal predecessors, (26), 11 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 11 states have call predecessors, (21), 11 states have call successors, (21) [2025-03-16 18:09:47,266 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:47,267 INFO L93 Difference]: Finished difference Result 117 states and 176 transitions. [2025-03-16 18:09:47,268 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-16 18:09:47,268 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 14 states have internal predecessors, (26), 11 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 11 states have call predecessors, (21), 11 states have call successors, (21) Word has length 66 [2025-03-16 18:09:47,268 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:47,269 INFO L225 Difference]: With dead ends: 117 [2025-03-16 18:09:47,271 INFO L226 Difference]: Without dead ends: 114 [2025-03-16 18:09:47,271 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 111 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=156, Invalid=546, Unknown=0, NotChecked=0, Total=702 [2025-03-16 18:09:47,272 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 94 mSDsluCounter, 299 mSDsCounter, 0 mSdLazyCounter, 302 mSolverCounterSat, 113 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 99 SdHoareTripleChecker+Valid, 332 SdHoareTripleChecker+Invalid, 415 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 113 IncrementalHoareTripleChecker+Valid, 302 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:47,272 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [99 Valid, 332 Invalid, 415 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [113 Valid, 302 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 18:09:47,273 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2025-03-16 18:09:47,299 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 105. [2025-03-16 18:09:47,300 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 48 states have (on average 1.2916666666666667) internal successors, (62), 50 states have internal predecessors, (62), 49 states have call successors, (49), 7 states have call predecessors, (49), 7 states have return successors, (47), 47 states have call predecessors, (47), 47 states have call successors, (47) [2025-03-16 18:09:47,301 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 158 transitions. [2025-03-16 18:09:47,304 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 158 transitions. Word has length 66 [2025-03-16 18:09:47,304 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:47,304 INFO L471 AbstractCegarLoop]: Abstraction has 105 states and 158 transitions. [2025-03-16 18:09:47,304 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 14 states have internal predecessors, (26), 11 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (21), 11 states have call predecessors, (21), 11 states have call successors, (21) [2025-03-16 18:09:47,305 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 158 transitions. [2025-03-16 18:09:47,305 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2025-03-16 18:09:47,305 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:47,305 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 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, 1, 1] [2025-03-16 18:09:47,311 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-03-16 18:09:47,505 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,SelfDestructingSolverStorable7 [2025-03-16 18:09:47,506 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:47,506 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:47,506 INFO L85 PathProgramCache]: Analyzing trace with hash 1629311028, now seen corresponding path program 2 times [2025-03-16 18:09:47,507 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:47,507 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [661786286] [2025-03-16 18:09:47,507 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:09:47,507 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:47,513 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 71 statements into 2 equivalence classes. [2025-03-16 18:09:47,552 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 71 of 71 statements. [2025-03-16 18:09:47,553 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:09:47,553 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:47,554 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [995896210] [2025-03-16 18:09:47,554 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:09:47,554 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:47,554 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:47,556 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:09:47,557 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:09:47,582 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 71 statements into 2 equivalence classes. [2025-03-16 18:09:47,599 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 71 of 71 statements. [2025-03-16 18:09:47,599 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:09:47,599 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:47,600 INFO L256 TraceCheckSpWp]: Trace formula consists of 185 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-03-16 18:09:47,602 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:47,718 INFO L134 CoverageAnalysis]: Checked inductivity of 136 backedges. 12 proven. 4 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2025-03-16 18:09:47,718 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:47,751 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:47,751 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [661786286] [2025-03-16 18:09:47,751 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:47,751 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [995896210] [2025-03-16 18:09:47,751 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [995896210] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:47,751 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:09:47,752 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2025-03-16 18:09:47,752 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [487983037] [2025-03-16 18:09:47,752 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:47,752 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-16 18:09:47,753 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:47,754 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-16 18:09:47,754 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2025-03-16 18:09:47,754 INFO L87 Difference]: Start difference. First operand 105 states and 158 transitions. Second operand has 7 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2025-03-16 18:09:47,867 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:47,868 INFO L93 Difference]: Finished difference Result 121 states and 177 transitions. [2025-03-16 18:09:47,868 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-16 18:09:47,868 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 71 [2025-03-16 18:09:47,868 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:47,870 INFO L225 Difference]: With dead ends: 121 [2025-03-16 18:09:47,871 INFO L226 Difference]: Without dead ends: 119 [2025-03-16 18:09:47,871 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 67 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:09:47,872 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 10 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 190 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:47,872 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 190 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:47,873 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2025-03-16 18:09:47,901 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 118. [2025-03-16 18:09:47,901 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 55 states have (on average 1.2727272727272727) internal successors, (70), 57 states have internal predecessors, (70), 53 states have call successors, (53), 9 states have call predecessors, (53), 9 states have return successors, (51), 51 states have call predecessors, (51), 51 states have call successors, (51) [2025-03-16 18:09:47,903 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 174 transitions. [2025-03-16 18:09:47,903 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 174 transitions. Word has length 71 [2025-03-16 18:09:47,904 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:47,904 INFO L471 AbstractCegarLoop]: Abstraction has 118 states and 174 transitions. [2025-03-16 18:09:47,904 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2025-03-16 18:09:47,904 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 174 transitions. [2025-03-16 18:09:47,905 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2025-03-16 18:09:47,905 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:47,905 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:47,911 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:09:48,108 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:48,108 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:48,108 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:48,108 INFO L85 PathProgramCache]: Analyzing trace with hash -474475857, now seen corresponding path program 3 times [2025-03-16 18:09:48,108 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:48,109 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [836830577] [2025-03-16 18:09:48,109 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:09:48,109 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:48,114 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 76 statements into 6 equivalence classes. [2025-03-16 18:09:48,145 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 76 of 76 statements. [2025-03-16 18:09:48,145 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-16 18:09:48,145 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:48,146 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [305954978] [2025-03-16 18:09:48,146 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:09:48,146 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:48,146 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:48,147 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:09:48,149 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:09:48,174 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 76 statements into 6 equivalence classes. [2025-03-16 18:09:48,200 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) and asserted 45 of 76 statements. [2025-03-16 18:09:48,200 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2025-03-16 18:09:48,200 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:48,201 INFO L256 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 51 conjuncts are in the unsatisfiable core [2025-03-16 18:09:48,203 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:48,743 INFO L134 CoverageAnalysis]: Checked inductivity of 163 backedges. 43 proven. 18 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2025-03-16 18:09:48,743 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:49,127 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:49,128 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [836830577] [2025-03-16 18:09:49,128 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:49,128 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [305954978] [2025-03-16 18:09:49,128 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [305954978] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:49,128 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:09:49,128 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2025-03-16 18:09:49,128 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1668949936] [2025-03-16 18:09:49,128 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:49,128 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-16 18:09:49,128 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:49,128 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-16 18:09:49,129 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=378, Unknown=0, NotChecked=0, Total=462 [2025-03-16 18:09:49,129 INFO L87 Difference]: Start difference. First operand 118 states and 174 transitions. Second operand has 15 states, 13 states have (on average 1.6923076923076923) internal successors, (22), 13 states have internal predecessors, (22), 5 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2025-03-16 18:09:49,464 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:49,465 INFO L93 Difference]: Finished difference Result 125 states and 180 transitions. [2025-03-16 18:09:49,465 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-16 18:09:49,465 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.6923076923076923) internal successors, (22), 13 states have internal predecessors, (22), 5 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 76 [2025-03-16 18:09:49,466 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:49,468 INFO L225 Difference]: With dead ends: 125 [2025-03-16 18:09:49,468 INFO L226 Difference]: Without dead ends: 123 [2025-03-16 18:09:49,468 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 115 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=114, Invalid=486, Unknown=0, NotChecked=0, Total=600 [2025-03-16 18:09:49,468 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 24 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 323 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 340 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 323 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:49,469 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 124 Invalid, 340 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 323 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 18:09:49,469 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2025-03-16 18:09:49,500 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 122. [2025-03-16 18:09:49,500 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 58 states have (on average 1.2586206896551724) internal successors, (73), 60 states have internal predecessors, (73), 53 states have call successors, (53), 10 states have call predecessors, (53), 10 states have return successors, (51), 51 states have call predecessors, (51), 51 states have call successors, (51) [2025-03-16 18:09:49,501 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 177 transitions. [2025-03-16 18:09:49,501 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 177 transitions. Word has length 76 [2025-03-16 18:09:49,501 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:49,502 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 177 transitions. [2025-03-16 18:09:49,502 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.6923076923076923) internal successors, (22), 13 states have internal predecessors, (22), 5 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2025-03-16 18:09:49,502 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 177 transitions. [2025-03-16 18:09:49,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2025-03-16 18:09:49,502 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:49,503 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:49,508 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-03-16 18:09:49,707 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,SelfDestructingSolverStorable9 [2025-03-16 18:09:49,707 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:49,707 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:49,707 INFO L85 PathProgramCache]: Analyzing trace with hash 1793736189, now seen corresponding path program 1 times [2025-03-16 18:09:49,707 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:49,707 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1204955810] [2025-03-16 18:09:49,707 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:49,707 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:49,712 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 82 statements into 1 equivalence classes. [2025-03-16 18:09:49,723 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 82 of 82 statements. [2025-03-16 18:09:49,723 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:49,723 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:49,724 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1202788762] [2025-03-16 18:09:49,724 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:49,724 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:49,724 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:49,727 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:09:49,728 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:09:49,752 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 82 statements into 1 equivalence classes. [2025-03-16 18:09:49,772 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 82 of 82 statements. [2025-03-16 18:09:49,772 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:49,772 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:49,773 INFO L256 TraceCheckSpWp]: Trace formula consists of 205 conjuncts, 41 conjuncts are in the unsatisfiable core [2025-03-16 18:09:49,775 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:50,167 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 22 proven. 15 refuted. 0 times theorem prover too weak. 157 trivial. 0 not checked. [2025-03-16 18:09:50,167 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:50,455 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 16 proven. 6 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2025-03-16 18:09:50,456 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:50,456 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1204955810] [2025-03-16 18:09:50,456 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:50,456 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1202788762] [2025-03-16 18:09:50,456 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1202788762] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:09:50,456 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:09:50,456 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2025-03-16 18:09:50,456 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1681752905] [2025-03-16 18:09:50,456 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:50,456 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-16 18:09:50,456 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:50,457 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-16 18:09:50,457 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2025-03-16 18:09:50,457 INFO L87 Difference]: Start difference. First operand 122 states and 177 transitions. Second operand has 21 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 18 states have internal predecessors, (28), 10 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2025-03-16 18:09:51,948 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:51,948 INFO L93 Difference]: Finished difference Result 211 states and 334 transitions. [2025-03-16 18:09:51,948 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2025-03-16 18:09:51,949 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 18 states have internal predecessors, (28), 10 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 82 [2025-03-16 18:09:51,949 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:51,950 INFO L225 Difference]: With dead ends: 211 [2025-03-16 18:09:51,950 INFO L226 Difference]: Without dead ends: 207 [2025-03-16 18:09:51,951 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 179 GetRequests, 143 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=255, Invalid=1151, Unknown=0, NotChecked=0, Total=1406 [2025-03-16 18:09:51,951 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 51 mSDsluCounter, 320 mSDsCounter, 0 mSdLazyCounter, 534 mSolverCounterSat, 94 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 359 SdHoareTripleChecker+Invalid, 628 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 94 IncrementalHoareTripleChecker+Valid, 534 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:51,952 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 359 Invalid, 628 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [94 Valid, 534 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2025-03-16 18:09:51,952 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 207 states. [2025-03-16 18:09:52,002 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 207 to 204. [2025-03-16 18:09:52,002 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 204 states, 85 states have (on average 1.3529411764705883) internal successors, (115), 88 states have internal predecessors, (115), 106 states have call successors, (106), 12 states have call predecessors, (106), 12 states have return successors, (104), 103 states have call predecessors, (104), 104 states have call successors, (104) [2025-03-16 18:09:52,004 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 204 states to 204 states and 325 transitions. [2025-03-16 18:09:52,004 INFO L78 Accepts]: Start accepts. Automaton has 204 states and 325 transitions. Word has length 82 [2025-03-16 18:09:52,004 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:52,004 INFO L471 AbstractCegarLoop]: Abstraction has 204 states and 325 transitions. [2025-03-16 18:09:52,004 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 18 states have internal predecessors, (28), 10 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2025-03-16 18:09:52,004 INFO L276 IsEmpty]: Start isEmpty. Operand 204 states and 325 transitions. [2025-03-16 18:09:52,005 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2025-03-16 18:09:52,005 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:52,005 INFO L218 NwaCegarLoop]: trace histogram [11, 10, 10, 6, 6, 6, 3, 3, 3, 3, 3, 3, 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:09:52,011 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:09:52,210 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,SelfDestructingSolverStorable10 [2025-03-16 18:09:52,210 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:52,210 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:52,210 INFO L85 PathProgramCache]: Analyzing trace with hash -431904564, now seen corresponding path program 4 times [2025-03-16 18:09:52,210 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:52,210 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1104022793] [2025-03-16 18:09:52,210 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:09:52,210 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:52,216 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 94 statements into 2 equivalence classes. [2025-03-16 18:09:52,225 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 90 of 94 statements. [2025-03-16 18:09:52,225 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-16 18:09:52,225 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:52,291 INFO L134 CoverageAnalysis]: Checked inductivity of 275 backedges. 35 proven. 0 refuted. 0 times theorem prover too weak. 240 trivial. 0 not checked. [2025-03-16 18:09:52,292 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:52,292 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1104022793] [2025-03-16 18:09:52,292 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1104022793] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:09:52,292 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:09:52,292 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:09:52,292 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1323781388] [2025-03-16 18:09:52,292 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:09:52,292 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:09:52,292 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:52,293 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:09:52,293 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:09:52,293 INFO L87 Difference]: Start difference. First operand 204 states and 325 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 5 states have internal predecessors, (19), 3 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2025-03-16 18:09:52,366 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:52,367 INFO L93 Difference]: Finished difference Result 253 states and 396 transitions. [2025-03-16 18:09:52,368 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-16 18:09:52,368 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 5 states have internal predecessors, (19), 3 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) Word has length 94 [2025-03-16 18:09:52,368 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:52,369 INFO L225 Difference]: With dead ends: 253 [2025-03-16 18:09:52,370 INFO L226 Difference]: Without dead ends: 170 [2025-03-16 18:09:52,370 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 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:09:52,373 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 4 mSDsluCounter, 108 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:52,373 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 153 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:09:52,373 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 170 states. [2025-03-16 18:09:52,409 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 170 to 161. [2025-03-16 18:09:52,410 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 161 states, 70 states have (on average 1.2428571428571429) internal successors, (87), 73 states have internal predecessors, (87), 78 states have call successors, (78), 12 states have call predecessors, (78), 12 states have return successors, (76), 75 states have call predecessors, (76), 76 states have call successors, (76) [2025-03-16 18:09:52,411 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 161 states to 161 states and 241 transitions. [2025-03-16 18:09:52,411 INFO L78 Accepts]: Start accepts. Automaton has 161 states and 241 transitions. Word has length 94 [2025-03-16 18:09:52,411 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:52,411 INFO L471 AbstractCegarLoop]: Abstraction has 161 states and 241 transitions. [2025-03-16 18:09:52,411 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 5 states have internal predecessors, (19), 3 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2025-03-16 18:09:52,411 INFO L276 IsEmpty]: Start isEmpty. Operand 161 states and 241 transitions. [2025-03-16 18:09:52,412 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2025-03-16 18:09:52,412 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:52,412 INFO L218 NwaCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:52,412 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11 [2025-03-16 18:09:52,412 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:52,413 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:52,413 INFO L85 PathProgramCache]: Analyzing trace with hash 974568300, now seen corresponding path program 1 times [2025-03-16 18:09:52,413 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:52,413 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [836217054] [2025-03-16 18:09:52,413 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:52,413 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:52,416 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 97 statements into 1 equivalence classes. [2025-03-16 18:09:52,424 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 97 of 97 statements. [2025-03-16 18:09:52,424 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:52,424 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:52,606 INFO L134 CoverageAnalysis]: Checked inductivity of 316 backedges. 30 proven. 21 refuted. 0 times theorem prover too weak. 265 trivial. 0 not checked. [2025-03-16 18:09:52,606 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:52,606 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [836217054] [2025-03-16 18:09:52,607 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [836217054] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:52,607 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1360294191] [2025-03-16 18:09:52,607 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:09:52,607 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:52,607 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:52,609 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:09:52,611 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:09:52,637 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 97 statements into 1 equivalence classes. [2025-03-16 18:09:52,656 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 97 of 97 statements. [2025-03-16 18:09:52,656 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:09:52,656 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:52,657 INFO L256 TraceCheckSpWp]: Trace formula consists of 235 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-16 18:09:52,658 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:52,713 INFO L134 CoverageAnalysis]: Checked inductivity of 316 backedges. 120 proven. 21 refuted. 0 times theorem prover too weak. 175 trivial. 0 not checked. [2025-03-16 18:09:52,713 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:52,842 INFO L134 CoverageAnalysis]: Checked inductivity of 316 backedges. 30 proven. 21 refuted. 0 times theorem prover too weak. 265 trivial. 0 not checked. [2025-03-16 18:09:52,843 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1360294191] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:09:52,843 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:09:52,843 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 13 [2025-03-16 18:09:52,843 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1686816241] [2025-03-16 18:09:52,843 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:52,843 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2025-03-16 18:09:52,843 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:52,843 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2025-03-16 18:09:52,843 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2025-03-16 18:09:52,844 INFO L87 Difference]: Start difference. First operand 161 states and 241 transitions. Second operand has 13 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 13 states have internal predecessors, (28), 8 states have call successors, (28), 2 states have call predecessors, (28), 3 states have return successors, (28), 7 states have call predecessors, (28), 8 states have call successors, (28) [2025-03-16 18:09:53,030 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:53,030 INFO L93 Difference]: Finished difference Result 218 states and 326 transitions. [2025-03-16 18:09:53,030 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-16 18:09:53,031 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 13 states have internal predecessors, (28), 8 states have call successors, (28), 2 states have call predecessors, (28), 3 states have return successors, (28), 7 states have call predecessors, (28), 8 states have call successors, (28) Word has length 97 [2025-03-16 18:09:53,031 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:53,032 INFO L225 Difference]: With dead ends: 218 [2025-03-16 18:09:53,032 INFO L226 Difference]: Without dead ends: 144 [2025-03-16 18:09:53,032 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 189 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=95, Invalid=325, Unknown=0, NotChecked=0, Total=420 [2025-03-16 18:09:53,033 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 33 mSDsluCounter, 191 mSDsCounter, 0 mSdLazyCounter, 139 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 226 SdHoareTripleChecker+Invalid, 176 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 139 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:53,033 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 226 Invalid, 176 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 139 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:53,033 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 144 states. [2025-03-16 18:09:53,063 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 144 to 144. [2025-03-16 18:09:53,064 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 65 states have (on average 1.2) internal successors, (78), 68 states have internal predecessors, (78), 66 states have call successors, (66), 12 states have call predecessors, (66), 12 states have return successors, (64), 63 states have call predecessors, (64), 64 states have call successors, (64) [2025-03-16 18:09:53,065 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 208 transitions. [2025-03-16 18:09:53,065 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 208 transitions. Word has length 97 [2025-03-16 18:09:53,065 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:53,065 INFO L471 AbstractCegarLoop]: Abstraction has 144 states and 208 transitions. [2025-03-16 18:09:53,066 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 13 states have internal predecessors, (28), 8 states have call successors, (28), 2 states have call predecessors, (28), 3 states have return successors, (28), 7 states have call predecessors, (28), 8 states have call successors, (28) [2025-03-16 18:09:53,067 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 208 transitions. [2025-03-16 18:09:53,068 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2025-03-16 18:09:53,068 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:53,068 INFO L218 NwaCegarLoop]: trace histogram [14, 13, 13, 6, 6, 6, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:53,075 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:09:53,268 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,SelfDestructingSolverStorable12 [2025-03-16 18:09:53,268 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:53,269 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:53,269 INFO L85 PathProgramCache]: Analyzing trace with hash 1849036004, now seen corresponding path program 2 times [2025-03-16 18:09:53,269 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:53,269 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [266523833] [2025-03-16 18:09:53,269 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:09:53,269 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:53,274 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 110 statements into 2 equivalence classes. [2025-03-16 18:09:53,284 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 110 of 110 statements. [2025-03-16 18:09:53,284 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:09:53,284 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:53,438 INFO L134 CoverageAnalysis]: Checked inductivity of 423 backedges. 38 proven. 28 refuted. 0 times theorem prover too weak. 357 trivial. 0 not checked. [2025-03-16 18:09:53,438 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:53,438 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [266523833] [2025-03-16 18:09:53,438 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [266523833] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:53,438 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [328730285] [2025-03-16 18:09:53,438 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:09:53,438 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:53,438 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:53,440 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:09:53,442 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:09:53,467 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 110 statements into 2 equivalence classes. [2025-03-16 18:09:53,489 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 110 of 110 statements. [2025-03-16 18:09:53,490 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:09:53,490 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:53,491 INFO L256 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-16 18:09:53,492 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:53,589 INFO L134 CoverageAnalysis]: Checked inductivity of 423 backedges. 95 proven. 17 refuted. 0 times theorem prover too weak. 311 trivial. 0 not checked. [2025-03-16 18:09:53,589 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:53,693 INFO L134 CoverageAnalysis]: Checked inductivity of 423 backedges. 38 proven. 28 refuted. 0 times theorem prover too weak. 357 trivial. 0 not checked. [2025-03-16 18:09:53,694 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [328730285] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:09:53,694 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:09:53,694 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 16 [2025-03-16 18:09:53,694 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [711101529] [2025-03-16 18:09:53,694 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:53,694 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-16 18:09:53,694 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:53,695 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-16 18:09:53,695 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2025-03-16 18:09:53,695 INFO L87 Difference]: Start difference. First operand 144 states and 208 transitions. Second operand has 16 states, 16 states have (on average 2.0625) internal successors, (33), 14 states have internal predecessors, (33), 9 states have call successors, (31), 2 states have call predecessors, (31), 3 states have return successors, (31), 9 states have call predecessors, (31), 9 states have call successors, (31) [2025-03-16 18:09:53,888 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:53,888 INFO L93 Difference]: Finished difference Result 173 states and 251 transitions. [2025-03-16 18:09:53,888 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-16 18:09:53,888 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.0625) internal successors, (33), 14 states have internal predecessors, (33), 9 states have call successors, (31), 2 states have call predecessors, (31), 3 states have return successors, (31), 9 states have call predecessors, (31), 9 states have call successors, (31) Word has length 110 [2025-03-16 18:09:53,889 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:53,889 INFO L225 Difference]: With dead ends: 173 [2025-03-16 18:09:53,890 INFO L226 Difference]: Without dead ends: 137 [2025-03-16 18:09:53,890 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 234 GetRequests, 209 SyntacticMatches, 5 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=97, Invalid=365, Unknown=0, NotChecked=0, Total=462 [2025-03-16 18:09:53,890 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 12 mSDsluCounter, 268 mSDsCounter, 0 mSdLazyCounter, 193 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 310 SdHoareTripleChecker+Invalid, 211 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 193 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:53,890 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 310 Invalid, 211 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 193 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:53,891 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2025-03-16 18:09:53,915 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 137. [2025-03-16 18:09:53,915 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 137 states, 60 states have (on average 1.15) internal successors, (69), 62 states have internal predecessors, (69), 65 states have call successors, (65), 11 states have call predecessors, (65), 11 states have return successors, (63), 63 states have call predecessors, (63), 63 states have call successors, (63) [2025-03-16 18:09:53,916 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 197 transitions. [2025-03-16 18:09:53,916 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 197 transitions. Word has length 110 [2025-03-16 18:09:53,917 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:53,917 INFO L471 AbstractCegarLoop]: Abstraction has 137 states and 197 transitions. [2025-03-16 18:09:53,917 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.0625) internal successors, (33), 14 states have internal predecessors, (33), 9 states have call successors, (31), 2 states have call predecessors, (31), 3 states have return successors, (31), 9 states have call predecessors, (31), 9 states have call successors, (31) [2025-03-16 18:09:53,917 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 197 transitions. [2025-03-16 18:09:53,918 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 127 [2025-03-16 18:09:53,918 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:53,918 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 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:09:53,924 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:09:54,118 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,SelfDestructingSolverStorable13 [2025-03-16 18:09:54,119 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:54,119 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:54,119 INFO L85 PathProgramCache]: Analyzing trace with hash -41902702, now seen corresponding path program 2 times [2025-03-16 18:09:54,119 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:54,119 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1973810644] [2025-03-16 18:09:54,119 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:09:54,119 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:54,123 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 126 statements into 2 equivalence classes. [2025-03-16 18:09:54,145 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 126 of 126 statements. [2025-03-16 18:09:54,146 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:09:54,146 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-16 18:09:54,148 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1209337553] [2025-03-16 18:09:54,148 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:09:54,148 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:54,148 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:54,151 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:09:54,152 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:09:54,181 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 126 statements into 2 equivalence classes. [2025-03-16 18:09:54,214 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 126 of 126 statements. [2025-03-16 18:09:54,214 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:09:54,214 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:54,219 INFO L256 TraceCheckSpWp]: Trace formula consists of 300 conjuncts, 47 conjuncts are in the unsatisfiable core [2025-03-16 18:09:54,221 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:54,954 INFO L134 CoverageAnalysis]: Checked inductivity of 606 backedges. 76 proven. 50 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2025-03-16 18:09:54,955 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:55,588 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:55,588 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1973810644] [2025-03-16 18:09:55,588 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-16 18:09:55,588 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1209337553] [2025-03-16 18:09:55,588 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1209337553] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:55,588 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-16 18:09:55,588 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2025-03-16 18:09:55,589 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [747571342] [2025-03-16 18:09:55,589 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:55,589 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-16 18:09:55,589 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:55,589 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-16 18:09:55,590 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=803, Unknown=0, NotChecked=0, Total=930 [2025-03-16 18:09:55,590 INFO L87 Difference]: Start difference. First operand 137 states and 197 transitions. Second operand has 20 states, 18 states have (on average 1.5) internal successors, (27), 17 states have internal predecessors, (27), 9 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2025-03-16 18:09:56,157 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:56,157 INFO L93 Difference]: Finished difference Result 169 states and 248 transitions. [2025-03-16 18:09:56,157 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-16 18:09:56,157 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 1.5) internal successors, (27), 17 states have internal predecessors, (27), 9 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) Word has length 126 [2025-03-16 18:09:56,158 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:56,159 INFO L225 Difference]: With dead ends: 169 [2025-03-16 18:09:56,159 INFO L226 Difference]: Without dead ends: 167 [2025-03-16 18:09:56,159 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 203 GetRequests, 167 SyntacticMatches, 2 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 286 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=175, Invalid=1085, Unknown=0, NotChecked=0, Total=1260 [2025-03-16 18:09:56,159 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 30 mSDsluCounter, 349 mSDsCounter, 0 mSdLazyCounter, 819 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 388 SdHoareTripleChecker+Invalid, 833 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 819 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:56,159 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 388 Invalid, 833 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 819 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-03-16 18:09:56,160 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 167 states. [2025-03-16 18:09:56,190 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 167 to 149. [2025-03-16 18:09:56,190 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 149 states, 66 states have (on average 1.1666666666666667) internal successors, (77), 69 states have internal predecessors, (77), 70 states have call successors, (70), 12 states have call predecessors, (70), 12 states have return successors, (68), 67 states have call predecessors, (68), 68 states have call successors, (68) [2025-03-16 18:09:56,191 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 215 transitions. [2025-03-16 18:09:56,191 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 215 transitions. Word has length 126 [2025-03-16 18:09:56,191 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:56,191 INFO L471 AbstractCegarLoop]: Abstraction has 149 states and 215 transitions. [2025-03-16 18:09:56,191 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 1.5) internal successors, (27), 17 states have internal predecessors, (27), 9 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2025-03-16 18:09:56,191 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 215 transitions. [2025-03-16 18:09:56,192 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2025-03-16 18:09:56,192 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:56,192 INFO L218 NwaCegarLoop]: trace histogram [18, 17, 17, 6, 6, 6, 5, 5, 5, 4, 4, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:56,198 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:09:56,393 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:56,393 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:56,393 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:56,393 INFO L85 PathProgramCache]: Analyzing trace with hash 498399703, now seen corresponding path program 3 times [2025-03-16 18:09:56,393 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:56,393 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [882171455] [2025-03-16 18:09:56,393 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:09:56,393 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:56,398 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 131 statements into 11 equivalence classes. [2025-03-16 18:09:56,415 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) and asserted 116 of 131 statements. [2025-03-16 18:09:56,415 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2025-03-16 18:09:56,415 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:56,600 INFO L134 CoverageAnalysis]: Checked inductivity of 680 backedges. 46 proven. 40 refuted. 0 times theorem prover too weak. 594 trivial. 0 not checked. [2025-03-16 18:09:56,600 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:56,600 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [882171455] [2025-03-16 18:09:56,600 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [882171455] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:56,600 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1960364951] [2025-03-16 18:09:56,600 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:09:56,600 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:56,601 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:56,602 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:09:56,604 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:09:56,634 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 131 statements into 11 equivalence classes. [2025-03-16 18:09:56,652 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 61 of 131 statements. [2025-03-16 18:09:56,652 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-16 18:09:56,652 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:56,653 INFO L256 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-03-16 18:09:56,655 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:56,754 INFO L134 CoverageAnalysis]: Checked inductivity of 680 backedges. 104 proven. 10 refuted. 0 times theorem prover too weak. 566 trivial. 0 not checked. [2025-03-16 18:09:56,754 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:56,854 INFO L134 CoverageAnalysis]: Checked inductivity of 680 backedges. 92 proven. 7 refuted. 0 times theorem prover too weak. 581 trivial. 0 not checked. [2025-03-16 18:09:56,854 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1960364951] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:09:56,854 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:09:56,854 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10, 7] total 19 [2025-03-16 18:09:56,855 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2092143610] [2025-03-16 18:09:56,855 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:56,855 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-16 18:09:56,855 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:56,855 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-16 18:09:56,855 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=299, Unknown=0, NotChecked=0, Total=342 [2025-03-16 18:09:56,856 INFO L87 Difference]: Start difference. First operand 149 states and 215 transitions. Second operand has 19 states, 19 states have (on average 2.1578947368421053) internal successors, (41), 17 states have internal predecessors, (41), 8 states have call successors, (32), 4 states have call predecessors, (32), 3 states have return successors, (32), 8 states have call predecessors, (32), 8 states have call successors, (32) [2025-03-16 18:09:57,229 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:57,230 INFO L93 Difference]: Finished difference Result 171 states and 236 transitions. [2025-03-16 18:09:57,230 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-03-16 18:09:57,230 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 2.1578947368421053) internal successors, (41), 17 states have internal predecessors, (41), 8 states have call successors, (32), 4 states have call predecessors, (32), 3 states have return successors, (32), 8 states have call predecessors, (32), 8 states have call successors, (32) Word has length 131 [2025-03-16 18:09:57,231 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:57,231 INFO L225 Difference]: With dead ends: 171 [2025-03-16 18:09:57,231 INFO L226 Difference]: Without dead ends: 134 [2025-03-16 18:09:57,232 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 280 GetRequests, 254 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 88 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=115, Invalid=641, Unknown=0, NotChecked=0, Total=756 [2025-03-16 18:09:57,232 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 25 mSDsluCounter, 316 mSDsCounter, 0 mSdLazyCounter, 508 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 344 SdHoareTripleChecker+Invalid, 536 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 508 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:57,232 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 344 Invalid, 536 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 508 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-16 18:09:57,232 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 134 states. [2025-03-16 18:09:57,260 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 134 to 133. [2025-03-16 18:09:57,260 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 133 states, 64 states have (on average 1.109375) internal successors, (71), 65 states have internal predecessors, (71), 55 states have call successors, (55), 13 states have call predecessors, (55), 13 states have return successors, (54), 54 states have call predecessors, (54), 54 states have call successors, (54) [2025-03-16 18:09:57,261 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 180 transitions. [2025-03-16 18:09:57,262 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 180 transitions. Word has length 131 [2025-03-16 18:09:57,262 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:57,262 INFO L471 AbstractCegarLoop]: Abstraction has 133 states and 180 transitions. [2025-03-16 18:09:57,262 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 2.1578947368421053) internal successors, (41), 17 states have internal predecessors, (41), 8 states have call successors, (32), 4 states have call predecessors, (32), 3 states have return successors, (32), 8 states have call predecessors, (32), 8 states have call successors, (32) [2025-03-16 18:09:57,262 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 180 transitions. [2025-03-16 18:09:57,263 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2025-03-16 18:09:57,263 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:57,263 INFO L218 NwaCegarLoop]: trace histogram [19, 18, 18, 6, 6, 6, 5, 5, 5, 5, 5, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:09:57,270 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2025-03-16 18:09:57,464 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,SelfDestructingSolverStorable15 [2025-03-16 18:09:57,464 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:57,464 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:57,464 INFO L85 PathProgramCache]: Analyzing trace with hash 1859972471, now seen corresponding path program 4 times [2025-03-16 18:09:57,464 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:57,465 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [891752481] [2025-03-16 18:09:57,465 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:09:57,465 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:57,469 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 134 statements into 2 equivalence classes. [2025-03-16 18:09:57,475 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 130 of 134 statements. [2025-03-16 18:09:57,475 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-16 18:09:57,475 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:57,607 INFO L134 CoverageAnalysis]: Checked inductivity of 751 backedges. 49 proven. 45 refuted. 0 times theorem prover too weak. 657 trivial. 0 not checked. [2025-03-16 18:09:57,608 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:57,608 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [891752481] [2025-03-16 18:09:57,608 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [891752481] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:57,608 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [502123403] [2025-03-16 18:09:57,608 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:09:57,608 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:57,608 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:57,610 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:09:57,611 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:09:57,638 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 134 statements into 2 equivalence classes. [2025-03-16 18:09:57,659 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 130 of 134 statements. [2025-03-16 18:09:57,660 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-16 18:09:57,660 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:57,661 INFO L256 TraceCheckSpWp]: Trace formula consists of 277 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-16 18:09:57,663 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:09:57,749 INFO L134 CoverageAnalysis]: Checked inductivity of 751 backedges. 173 proven. 45 refuted. 0 times theorem prover too weak. 533 trivial. 0 not checked. [2025-03-16 18:09:57,750 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:09:57,913 INFO L134 CoverageAnalysis]: Checked inductivity of 751 backedges. 49 proven. 45 refuted. 0 times theorem prover too weak. 657 trivial. 0 not checked. [2025-03-16 18:09:57,913 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [502123403] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:09:57,913 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:09:57,913 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 15 [2025-03-16 18:09:57,913 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [508283789] [2025-03-16 18:09:57,913 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:09:57,913 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-16 18:09:57,913 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:09:57,914 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-16 18:09:57,914 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=174, Unknown=0, NotChecked=0, Total=210 [2025-03-16 18:09:57,914 INFO L87 Difference]: Start difference. First operand 133 states and 180 transitions. Second operand has 15 states, 15 states have (on average 2.2) internal successors, (33), 15 states have internal predecessors, (33), 12 states have call successors, (42), 2 states have call predecessors, (42), 3 states have return successors, (42), 11 states have call predecessors, (42), 12 states have call successors, (42) [2025-03-16 18:09:58,118 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:09:58,119 INFO L93 Difference]: Finished difference Result 150 states and 194 transitions. [2025-03-16 18:09:58,119 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-16 18:09:58,119 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.2) internal successors, (33), 15 states have internal predecessors, (33), 12 states have call successors, (42), 2 states have call predecessors, (42), 3 states have return successors, (42), 11 states have call predecessors, (42), 12 states have call successors, (42) Word has length 134 [2025-03-16 18:09:58,119 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:09:58,120 INFO L225 Difference]: With dead ends: 150 [2025-03-16 18:09:58,120 INFO L226 Difference]: Without dead ends: 84 [2025-03-16 18:09:58,120 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 283 GetRequests, 260 SyntacticMatches, 3 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=94, Invalid=368, Unknown=0, NotChecked=0, Total=462 [2025-03-16 18:09:58,121 INFO L435 NwaCegarLoop]: 49 mSDtfsCounter, 17 mSDsluCounter, 268 mSDsCounter, 0 mSdLazyCounter, 166 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 317 SdHoareTripleChecker+Invalid, 195 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 166 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:09:58,121 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 317 Invalid, 195 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 166 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:09:58,121 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2025-03-16 18:09:58,143 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 84. [2025-03-16 18:09:58,144 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 46 states have (on average 1.0217391304347827) internal successors, (47), 46 states have internal predecessors, (47), 27 states have call successors, (27), 11 states have call predecessors, (27), 10 states have return successors, (26), 26 states have call predecessors, (26), 26 states have call successors, (26) [2025-03-16 18:09:58,144 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 100 transitions. [2025-03-16 18:09:58,145 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 100 transitions. Word has length 134 [2025-03-16 18:09:58,145 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:09:58,145 INFO L471 AbstractCegarLoop]: Abstraction has 84 states and 100 transitions. [2025-03-16 18:09:58,145 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.2) internal successors, (33), 15 states have internal predecessors, (33), 12 states have call successors, (42), 2 states have call predecessors, (42), 3 states have return successors, (42), 11 states have call predecessors, (42), 12 states have call successors, (42) [2025-03-16 18:09:58,145 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 100 transitions. [2025-03-16 18:09:58,146 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 148 [2025-03-16 18:09:58,146 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:09:58,146 INFO L218 NwaCegarLoop]: trace histogram [21, 20, 20, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 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:09:58,152 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2025-03-16 18:09:58,346 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-03-16 18:09:58,347 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:09:58,347 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:09:58,347 INFO L85 PathProgramCache]: Analyzing trace with hash 451232901, now seen corresponding path program 3 times [2025-03-16 18:09:58,347 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:09:58,347 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2016692475] [2025-03-16 18:09:58,347 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:09:58,347 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:09:58,353 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 147 statements into 15 equivalence classes. [2025-03-16 18:09:58,374 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 14 check-sat command(s) and asserted 142 of 147 statements. [2025-03-16 18:09:58,376 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 14 check-sat command(s) [2025-03-16 18:09:58,376 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:58,568 INFO L134 CoverageAnalysis]: Checked inductivity of 914 backedges. 43 proven. 66 refuted. 0 times theorem prover too weak. 805 trivial. 0 not checked. [2025-03-16 18:09:58,568 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:09:58,568 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2016692475] [2025-03-16 18:09:58,568 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2016692475] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:09:58,568 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1997450876] [2025-03-16 18:09:58,568 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:09:58,569 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:09:58,569 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:09:58,570 INFO L229 MonitoredProcess]: Starting monitored process 18 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:09:58,572 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2025-03-16 18:09:58,601 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 147 statements into 15 equivalence classes. [2025-03-16 18:09:58,642 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 72 of 147 statements. [2025-03-16 18:09:58,642 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-16 18:09:58,642 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:09:58,643 INFO L256 TraceCheckSpWp]: Trace formula consists of 187 conjuncts, 48 conjuncts are in the unsatisfiable core [2025-03-16 18:09:58,645 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:10:03,440 INFO L134 CoverageAnalysis]: Checked inductivity of 914 backedges. 253 proven. 22 refuted. 0 times theorem prover too weak. 639 trivial. 0 not checked. [2025-03-16 18:10:03,440 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:10:03,800 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1997450876] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:10:03,801 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-16 18:10:03,801 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 16] total 25 [2025-03-16 18:10:03,801 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [871699208] [2025-03-16 18:10:03,801 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-16 18:10:03,801 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-16 18:10:03,801 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:10:03,801 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-16 18:10:03,802 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=780, Unknown=2, NotChecked=0, Total=870 [2025-03-16 18:10:03,802 INFO L87 Difference]: Start difference. First operand 84 states and 100 transitions. Second operand has 25 states, 21 states have (on average 1.8571428571428572) internal successors, (39), 20 states have internal predecessors, (39), 14 states have call successors, (40), 3 states have call predecessors, (40), 3 states have return successors, (40), 13 states have call predecessors, (40), 12 states have call successors, (40) [2025-03-16 18:10:04,976 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.08s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2025-03-16 18:10:09,048 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2025-03-16 18:10:13,237 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2025-03-16 18:10:17,252 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2025-03-16 18:10:30,220 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.05s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2025-03-16 18:10:43,298 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 [0] [2025-03-16 18:10:55,580 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2025-03-16 18:10:59,750 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.04s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2025-03-16 18:11:03,776 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2025-03-16 18:11:23,963 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.05s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0]