./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound20.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 798a7b37 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound20.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 be4e75b70a907f4bb3fe11ead30460ebebe535afde280ea19731f48bb2dd2cd7 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 14:07:40,239 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 14:07:40,296 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-03 14:07:40,300 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 14:07:40,302 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 14:07:40,322 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 14:07:40,322 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 14:07:40,323 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 14:07:40,323 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 14:07:40,323 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 14:07:40,324 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 14:07:40,324 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 14:07:40,324 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 14:07:40,324 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 14:07:40,324 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 14:07:40,324 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 14:07:40,324 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 14:07:40,325 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 14:07:40,325 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 14:07:40,325 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 14:07:40,325 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 14:07:40,325 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 14:07:40,325 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 14:07:40,325 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 14:07:40,325 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 14:07:40,325 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 14:07:40,325 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 14:07:40,325 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 14:07:40,326 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 14:07:40,326 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 14:07:40,326 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 14:07:40,326 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 14:07:40,326 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:07:40,326 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 14:07:40,327 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 14:07:40,327 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 14:07:40,327 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 14:07:40,327 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 14:07:40,327 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 14:07:40,327 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 14:07:40,327 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 14:07:40,327 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 14:07:40,327 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 14:07:40,327 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 -> be4e75b70a907f4bb3fe11ead30460ebebe535afde280ea19731f48bb2dd2cd7 [2025-03-03 14:07:40,537 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 14:07:40,544 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 14:07:40,546 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 14:07:40,547 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 14:07:40,548 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 14:07:40,549 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound20.c [2025-03-03 14:07:41,642 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3bb3c720b/52c74ea057ea44bea5c3eb79482fb4fd/FLAG3e8bfe390 [2025-03-03 14:07:41,845 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 14:07:41,845 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/prodbin-ll_unwindbound20.c [2025-03-03 14:07:41,850 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3bb3c720b/52c74ea057ea44bea5c3eb79482fb4fd/FLAG3e8bfe390 [2025-03-03 14:07:42,209 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3bb3c720b/52c74ea057ea44bea5c3eb79482fb4fd [2025-03-03 14:07:42,211 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 14:07:42,212 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 14:07:42,213 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 14:07:42,213 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 14:07:42,216 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 14:07:42,217 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,217 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@9bc58a4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42, skipping insertion in model container [2025-03-03 14:07:42,217 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,230 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 14:07:42,317 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/prodbin-ll_unwindbound20.c[1176,1189] [2025-03-03 14:07:42,329 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:07:42,335 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 14:07:42,344 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/prodbin-ll_unwindbound20.c[1176,1189] [2025-03-03 14:07:42,349 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:07:42,360 INFO L204 MainTranslator]: Completed translation [2025-03-03 14:07:42,361 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42 WrapperNode [2025-03-03 14:07:42,361 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 14:07:42,362 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 14:07:42,362 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 14:07:42,362 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 14:07:42,366 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,371 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,380 INFO L138 Inliner]: procedures = 14, calls = 10, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 48 [2025-03-03 14:07:42,381 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 14:07:42,381 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 14:07:42,381 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 14:07:42,381 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 14:07:42,388 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,388 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,392 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,404 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2025-03-03 14:07:42,404 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,404 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,407 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,410 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,411 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,411 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,412 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 14:07:42,412 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 14:07:42,412 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 14:07:42,413 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 14:07:42,413 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42" (1/1) ... [2025-03-03 14:07:42,417 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:07:42,425 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:42,438 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-03 14:07:42,443 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-03 14:07:42,461 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 14:07:42,461 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 14:07:42,461 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 14:07:42,462 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 14:07:42,462 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-03-03 14:07:42,462 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-03-03 14:07:42,504 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 14:07:42,505 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 14:07:42,620 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2025-03-03 14:07:42,620 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 14:07:42,627 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 14:07:42,628 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 14:07:42,629 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:07:42 BoogieIcfgContainer [2025-03-03 14:07:42,629 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 14:07:42,631 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 14:07:42,632 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 14:07:42,635 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 14:07:42,635 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 02:07:42" (1/3) ... [2025-03-03 14:07:42,636 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@10028fa2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:07:42, skipping insertion in model container [2025-03-03 14:07:42,636 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:07:42" (2/3) ... [2025-03-03 14:07:42,636 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@10028fa2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:07:42, skipping insertion in model container [2025-03-03 14:07:42,637 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:07:42" (3/3) ... [2025-03-03 14:07:42,637 INFO L128 eAbstractionObserver]: Analyzing ICFG prodbin-ll_unwindbound20.c [2025-03-03 14:07:42,648 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 14:07:42,649 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG prodbin-ll_unwindbound20.c that has 2 procedures, 21 locations, 1 initial locations, 1 loop locations, and 1 error locations. [2025-03-03 14:07:42,686 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 14:07:42,694 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;@611b65d1, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 14:07:42,694 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-03 14:07:42,703 INFO L276 IsEmpty]: Start isEmpty. Operand has 21 states, 16 states have (on average 1.4375) internal successors, (23), 17 states have internal predecessors, (23), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-03 14:07:42,708 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2025-03-03 14:07:42,708 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:42,709 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:42,709 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:42,712 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:42,712 INFO L85 PathProgramCache]: Analyzing trace with hash -1374148916, now seen corresponding path program 1 times [2025-03-03 14:07:42,716 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:42,717 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1492867368] [2025-03-03 14:07:42,717 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:42,717 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:42,768 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-03 14:07:42,783 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-03 14:07:42,783 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:42,783 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:42,823 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:07:42,824 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:42,824 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1492867368] [2025-03-03 14:07:42,825 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1492867368] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:07:42,825 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:07:42,825 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-03-03 14:07:42,826 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1505082624] [2025-03-03 14:07:42,827 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:07:42,829 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-03-03 14:07:42,829 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:42,843 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-03-03 14:07:42,844 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-03 14:07:42,845 INFO L87 Difference]: Start difference. First operand has 21 states, 16 states have (on average 1.4375) internal successors, (23), 17 states have internal predecessors, (23), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Second operand has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 14:07:42,854 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:42,854 INFO L93 Difference]: Finished difference Result 39 states and 52 transitions. [2025-03-03 14:07:42,855 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-03 14:07:42,856 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2025-03-03 14:07:42,856 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:42,859 INFO L225 Difference]: With dead ends: 39 [2025-03-03 14:07:42,859 INFO L226 Difference]: Without dead ends: 17 [2025-03-03 14:07:42,862 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-03-03 14:07:42,864 INFO L435 NwaCegarLoop]: 24 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, 24 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:42,865 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:07:42,873 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2025-03-03 14:07:42,882 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2025-03-03 14:07:42,882 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 14 states have internal predecessors, (17), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-03 14:07:42,885 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 20 transitions. [2025-03-03 14:07:42,886 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 20 transitions. Word has length 9 [2025-03-03 14:07:42,886 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:42,886 INFO L471 AbstractCegarLoop]: Abstraction has 17 states and 20 transitions. [2025-03-03 14:07:42,886 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 14:07:42,886 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 20 transitions. [2025-03-03 14:07:42,887 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2025-03-03 14:07:42,887 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:42,887 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:42,887 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-03 14:07:42,887 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:42,888 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:42,888 INFO L85 PathProgramCache]: Analyzing trace with hash 307772215, now seen corresponding path program 1 times [2025-03-03 14:07:42,888 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:42,888 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [770192449] [2025-03-03 14:07:42,888 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:42,888 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:42,894 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-03 14:07:42,904 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-03 14:07:42,905 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:42,905 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:07:42,907 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1910798749] [2025-03-03 14:07:42,907 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:42,907 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:42,907 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:42,912 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:07:42,913 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-03 14:07:42,945 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-03 14:07:42,969 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-03 14:07:42,969 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:42,969 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:42,971 INFO L256 TraceCheckSpWp]: Trace formula consists of 52 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-03 14:07:42,974 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:43,135 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:07:43,135 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 14:07:43,135 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:43,135 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [770192449] [2025-03-03 14:07:43,136 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:07:43,136 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1910798749] [2025-03-03 14:07:43,136 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1910798749] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:07:43,136 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:07:43,136 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-03 14:07:43,137 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1383808087] [2025-03-03 14:07:43,137 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:07:43,137 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2025-03-03 14:07:43,137 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:43,139 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2025-03-03 14:07:43,139 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2025-03-03 14:07:43,139 INFO L87 Difference]: Start difference. First operand 17 states and 20 transitions. Second operand has 7 states, 7 states have (on average 1.2857142857142858) internal successors, (9), 6 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 14:07:43,209 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:43,209 INFO L93 Difference]: Finished difference Result 35 states and 41 transitions. [2025-03-03 14:07:43,209 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-03-03 14:07:43,210 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 1.2857142857142858) internal successors, (9), 6 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2025-03-03 14:07:43,210 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:43,211 INFO L225 Difference]: With dead ends: 35 [2025-03-03 14:07:43,211 INFO L226 Difference]: Without dead ends: 28 [2025-03-03 14:07:43,211 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2025-03-03 14:07:43,212 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 18 mSDsluCounter, 42 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 54 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:43,213 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 54 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:07:43,213 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2025-03-03 14:07:43,217 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 25. [2025-03-03 14:07:43,217 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-03 14:07:43,217 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 29 transitions. [2025-03-03 14:07:43,219 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 29 transitions. Word has length 10 [2025-03-03 14:07:43,219 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:43,219 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 29 transitions. [2025-03-03 14:07:43,219 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 1.2857142857142858) internal successors, (9), 6 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 14:07:43,219 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 29 transitions. [2025-03-03 14:07:43,219 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2025-03-03 14:07:43,220 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:43,220 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:43,226 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-03 14:07:43,424 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:43,424 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:43,424 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:43,424 INFO L85 PathProgramCache]: Analyzing trace with hash 308636154, now seen corresponding path program 1 times [2025-03-03 14:07:43,425 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:43,425 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1559402167] [2025-03-03 14:07:43,425 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:43,425 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:43,430 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-03 14:07:43,438 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-03 14:07:43,438 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:43,438 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:43,501 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:07:43,501 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:43,501 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1559402167] [2025-03-03 14:07:43,501 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1559402167] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:07:43,501 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:07:43,501 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-03 14:07:43,501 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1620199002] [2025-03-03 14:07:43,501 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:07:43,502 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-03 14:07:43,502 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:43,502 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-03 14:07:43,502 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-03 14:07:43,502 INFO L87 Difference]: Start difference. First operand 25 states and 29 transitions. Second operand has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 14:07:43,513 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:43,513 INFO L93 Difference]: Finished difference Result 32 states and 35 transitions. [2025-03-03 14:07:43,514 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-03 14:07:43,514 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2025-03-03 14:07:43,514 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:43,514 INFO L225 Difference]: With dead ends: 32 [2025-03-03 14:07:43,514 INFO L226 Difference]: Without dead ends: 25 [2025-03-03 14:07:43,514 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-03 14:07:43,515 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 0 mSDsluCounter, 30 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:43,515 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 48 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:07:43,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2025-03-03 14:07:43,518 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2025-03-03 14:07:43,518 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 20 states have internal predecessors, (23), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-03 14:07:43,519 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 28 transitions. [2025-03-03 14:07:43,519 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 28 transitions. Word has length 10 [2025-03-03 14:07:43,519 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:43,519 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 28 transitions. [2025-03-03 14:07:43,519 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 14:07:43,519 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 28 transitions. [2025-03-03 14:07:43,520 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2025-03-03 14:07:43,520 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:43,520 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:43,520 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-03-03 14:07:43,520 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:43,521 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:43,521 INFO L85 PathProgramCache]: Analyzing trace with hash 1350144637, now seen corresponding path program 1 times [2025-03-03 14:07:43,521 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:43,521 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1034820612] [2025-03-03 14:07:43,521 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:43,521 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:43,537 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 20 statements into 1 equivalence classes. [2025-03-03 14:07:43,566 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 20 of 20 statements. [2025-03-03 14:07:43,567 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:43,567 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:07:43,567 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2087394764] [2025-03-03 14:07:43,568 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:43,568 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:43,568 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:43,569 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:07:43,571 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-03 14:07:43,593 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 20 statements into 1 equivalence classes. [2025-03-03 14:07:43,604 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 20 of 20 statements. [2025-03-03 14:07:43,605 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:43,605 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:43,605 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 23 conjuncts are in the unsatisfiable core [2025-03-03 14:07:43,607 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:43,844 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:07:43,844 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:07:44,685 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:07:44,685 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:44,685 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1034820612] [2025-03-03 14:07:44,685 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:07:44,685 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2087394764] [2025-03-03 14:07:44,685 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2087394764] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:07:44,685 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:07:44,685 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 16 [2025-03-03 14:07:44,685 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [188683199] [2025-03-03 14:07:44,685 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:07:44,686 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-03 14:07:44,686 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:44,686 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-03 14:07:44,687 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=191, Unknown=0, NotChecked=0, Total=240 [2025-03-03 14:07:44,687 INFO L87 Difference]: Start difference. First operand 25 states and 28 transitions. Second operand has 16 states, 16 states have (on average 1.8125) internal successors, (29), 14 states have internal predecessors, (29), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-03 14:07:44,923 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:44,923 INFO L93 Difference]: Finished difference Result 46 states and 55 transitions. [2025-03-03 14:07:44,923 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-03-03 14:07:44,923 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 1.8125) internal successors, (29), 14 states have internal predecessors, (29), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2025-03-03 14:07:44,924 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:44,925 INFO L225 Difference]: With dead ends: 46 [2025-03-03 14:07:44,925 INFO L226 Difference]: Without dead ends: 44 [2025-03-03 14:07:44,925 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2025-03-03 14:07:44,926 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 15 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 158 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:44,926 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 116 Invalid, 158 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 14:07:44,926 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2025-03-03 14:07:44,935 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 40. [2025-03-03 14:07:44,936 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 31 states have (on average 1.2903225806451613) internal successors, (40), 33 states have internal predecessors, (40), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-03 14:07:44,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 49 transitions. [2025-03-03 14:07:44,938 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 49 transitions. Word has length 20 [2025-03-03 14:07:44,938 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:44,939 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 49 transitions. [2025-03-03 14:07:44,940 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 1.8125) internal successors, (29), 14 states have internal predecessors, (29), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-03 14:07:44,940 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 49 transitions. [2025-03-03 14:07:44,940 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2025-03-03 14:07:44,940 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:44,940 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:44,955 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-03 14:07:45,141 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2025-03-03 14:07:45,141 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:45,142 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:45,142 INFO L85 PathProgramCache]: Analyzing trace with hash 1351008576, now seen corresponding path program 1 times [2025-03-03 14:07:45,143 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:45,143 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [233371420] [2025-03-03 14:07:45,143 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:45,143 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:45,148 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 20 statements into 1 equivalence classes. [2025-03-03 14:07:45,163 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 20 of 20 statements. [2025-03-03 14:07:45,163 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:45,163 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:45,259 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:07:45,260 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:45,260 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [233371420] [2025-03-03 14:07:45,260 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [233371420] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:07:45,260 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2091340245] [2025-03-03 14:07:45,260 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:45,260 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:45,260 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:45,262 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:07:45,264 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-03 14:07:45,285 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 20 statements into 1 equivalence classes. [2025-03-03 14:07:45,297 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 20 of 20 statements. [2025-03-03 14:07:45,297 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:45,297 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:45,297 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 5 conjuncts are in the unsatisfiable core [2025-03-03 14:07:45,299 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:45,323 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:07:45,324 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:07:45,357 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:07:45,358 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2091340245] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:07:45,358 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:07:45,358 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2025-03-03 14:07:45,358 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1759993259] [2025-03-03 14:07:45,358 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:07:45,358 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-03-03 14:07:45,358 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:45,359 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-03-03 14:07:45,359 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2025-03-03 14:07:45,359 INFO L87 Difference]: Start difference. First operand 40 states and 49 transitions. Second operand has 10 states, 10 states have (on average 3.7) internal successors, (37), 10 states have internal predecessors, (37), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-03 14:07:45,415 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:45,415 INFO L93 Difference]: Finished difference Result 91 states and 107 transitions. [2025-03-03 14:07:45,416 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-03 14:07:45,416 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.7) internal successors, (37), 10 states have internal predecessors, (37), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 20 [2025-03-03 14:07:45,416 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:45,416 INFO L225 Difference]: With dead ends: 91 [2025-03-03 14:07:45,416 INFO L226 Difference]: Without dead ends: 84 [2025-03-03 14:07:45,417 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 36 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2025-03-03 14:07:45,417 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 25 mSDsluCounter, 68 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:45,417 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 86 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:07:45,418 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2025-03-03 14:07:45,432 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 80. [2025-03-03 14:07:45,432 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 62 states have (on average 1.2258064516129032) internal successors, (76), 67 states have internal predecessors, (76), 10 states have call successors, (10), 7 states have call predecessors, (10), 7 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2025-03-03 14:07:45,433 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 93 transitions. [2025-03-03 14:07:45,435 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 93 transitions. Word has length 20 [2025-03-03 14:07:45,435 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:45,435 INFO L471 AbstractCegarLoop]: Abstraction has 80 states and 93 transitions. [2025-03-03 14:07:45,435 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.7) internal successors, (37), 10 states have internal predecessors, (37), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-03-03 14:07:45,435 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 93 transitions. [2025-03-03 14:07:45,436 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2025-03-03 14:07:45,436 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:45,436 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:45,442 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-03 14:07:45,636 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:45,637 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:45,637 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:45,637 INFO L85 PathProgramCache]: Analyzing trace with hash -1202012324, now seen corresponding path program 1 times [2025-03-03 14:07:45,637 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:45,637 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1595729033] [2025-03-03 14:07:45,637 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:45,637 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:45,641 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 20 statements into 1 equivalence classes. [2025-03-03 14:07:45,649 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 20 of 20 statements. [2025-03-03 14:07:45,651 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:45,651 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:07:45,654 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1722328163] [2025-03-03 14:07:45,654 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:45,654 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:45,654 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:45,656 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:07:45,658 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-03 14:07:45,680 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 20 statements into 1 equivalence classes. [2025-03-03 14:07:45,690 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 20 of 20 statements. [2025-03-03 14:07:45,690 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:45,690 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:45,691 INFO L256 TraceCheckSpWp]: Trace formula consists of 72 conjuncts, 22 conjuncts are in the unsatisfiable core [2025-03-03 14:07:45,692 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:45,927 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:07:45,927 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:07:46,338 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:07:46,339 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:46,339 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1595729033] [2025-03-03 14:07:46,339 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:07:46,339 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1722328163] [2025-03-03 14:07:46,339 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1722328163] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:07:46,339 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:07:46,339 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2025-03-03 14:07:46,339 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [552747482] [2025-03-03 14:07:46,339 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:07:46,339 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-03 14:07:46,339 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:46,340 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-03 14:07:46,340 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2025-03-03 14:07:46,340 INFO L87 Difference]: Start difference. First operand 80 states and 93 transitions. Second operand has 19 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 18 states have internal predecessors, (29), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-03 14:07:46,641 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:46,641 INFO L93 Difference]: Finished difference Result 114 states and 129 transitions. [2025-03-03 14:07:46,642 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-03 14:07:46,642 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 18 states have internal predecessors, (29), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2025-03-03 14:07:46,643 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:46,644 INFO L225 Difference]: With dead ends: 114 [2025-03-03 14:07:46,645 INFO L226 Difference]: Without dead ends: 103 [2025-03-03 14:07:46,645 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 19 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 106 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=123, Invalid=429, Unknown=0, NotChecked=0, Total=552 [2025-03-03 14:07:46,646 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 44 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 184 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 205 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 184 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:46,647 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 114 Invalid, 205 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 184 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 14:07:46,647 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2025-03-03 14:07:46,657 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 83. [2025-03-03 14:07:46,660 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 66 states have (on average 1.196969696969697) internal successors, (79), 68 states have internal predecessors, (79), 9 states have call successors, (9), 8 states have call predecessors, (9), 7 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2025-03-03 14:07:46,660 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 95 transitions. [2025-03-03 14:07:46,661 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 95 transitions. Word has length 20 [2025-03-03 14:07:46,661 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:46,661 INFO L471 AbstractCegarLoop]: Abstraction has 83 states and 95 transitions. [2025-03-03 14:07:46,662 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 18 states have internal predecessors, (29), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-03 14:07:46,662 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 95 transitions. [2025-03-03 14:07:46,662 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-03-03 14:07:46,662 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:46,662 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:46,668 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-03 14:07:46,863 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:46,863 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:46,863 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:46,863 INFO L85 PathProgramCache]: Analyzing trace with hash -514558041, now seen corresponding path program 1 times [2025-03-03 14:07:46,863 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:46,864 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1028151970] [2025-03-03 14:07:46,864 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:46,864 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:46,867 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-03 14:07:46,877 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-03 14:07:46,877 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:46,877 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:07:46,878 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1797729819] [2025-03-03 14:07:46,878 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:46,878 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:46,878 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:46,881 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:07:46,886 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-03 14:07:46,910 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-03-03 14:07:46,921 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-03-03 14:07:46,922 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:46,922 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:46,923 INFO L256 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-03 14:07:46,924 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:46,986 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-03 14:07:46,987 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:07:47,040 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-03 14:07:47,041 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:47,041 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1028151970] [2025-03-03 14:07:47,041 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:07:47,041 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1797729819] [2025-03-03 14:07:47,041 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1797729819] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:07:47,041 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:07:47,041 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 11 [2025-03-03 14:07:47,041 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [399015392] [2025-03-03 14:07:47,041 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:07:47,042 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-03 14:07:47,043 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:47,043 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-03 14:07:47,043 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2025-03-03 14:07:47,044 INFO L87 Difference]: Start difference. First operand 83 states and 95 transitions. Second operand has 11 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2025-03-03 14:07:47,100 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:47,100 INFO L93 Difference]: Finished difference Result 92 states and 103 transitions. [2025-03-03 14:07:47,101 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-03 14:07:47,101 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) Word has length 26 [2025-03-03 14:07:47,101 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:47,102 INFO L225 Difference]: With dead ends: 92 [2025-03-03 14:07:47,102 INFO L226 Difference]: Without dead ends: 82 [2025-03-03 14:07:47,102 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2025-03-03 14:07:47,102 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 12 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 84 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.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:47,103 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 84 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:07:47,103 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2025-03-03 14:07:47,121 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 80. [2025-03-03 14:07:47,121 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 64 states have (on average 1.140625) internal successors, (73), 66 states have internal predecessors, (73), 8 states have call successors, (8), 7 states have call predecessors, (8), 7 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2025-03-03 14:07:47,122 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 88 transitions. [2025-03-03 14:07:47,122 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 88 transitions. Word has length 26 [2025-03-03 14:07:47,122 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:47,122 INFO L471 AbstractCegarLoop]: Abstraction has 80 states and 88 transitions. [2025-03-03 14:07:47,122 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 2 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2025-03-03 14:07:47,122 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 88 transitions. [2025-03-03 14:07:47,125 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2025-03-03 14:07:47,125 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:47,126 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:47,131 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-03-03 14:07:47,326 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:47,326 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:47,327 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:47,327 INFO L85 PathProgramCache]: Analyzing trace with hash 1097281384, now seen corresponding path program 1 times [2025-03-03 14:07:47,327 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:47,327 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1528960180] [2025-03-03 14:07:47,327 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:47,327 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:47,330 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 40 statements into 1 equivalence classes. [2025-03-03 14:07:47,347 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 40 of 40 statements. [2025-03-03 14:07:47,347 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:47,347 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:07:47,348 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [155163364] [2025-03-03 14:07:47,348 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:07:47,349 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:47,352 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:47,354 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:07:47,355 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-03 14:07:47,375 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 40 statements into 1 equivalence classes. [2025-03-03 14:07:47,389 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 40 of 40 statements. [2025-03-03 14:07:47,389 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:07:47,390 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:47,390 INFO L256 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 31 conjuncts are in the unsatisfiable core [2025-03-03 14:07:47,392 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:47,727 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 8 proven. 31 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-03 14:07:47,728 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:07:49,752 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 26 proven. 10 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2025-03-03 14:07:49,753 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:07:49,753 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1528960180] [2025-03-03 14:07:49,753 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:07:49,753 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [155163364] [2025-03-03 14:07:49,753 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [155163364] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:07:49,753 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:07:49,753 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 10] total 21 [2025-03-03 14:07:49,753 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [61032020] [2025-03-03 14:07:49,753 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:07:49,753 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-03 14:07:49,753 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:07:49,754 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-03 14:07:49,754 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=348, Unknown=0, NotChecked=0, Total=420 [2025-03-03 14:07:49,754 INFO L87 Difference]: Start difference. First operand 80 states and 88 transitions. Second operand has 21 states, 21 states have (on average 2.380952380952381) internal successors, (50), 19 states have internal predecessors, (50), 7 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-03 14:07:52,764 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:07:52,765 INFO L93 Difference]: Finished difference Result 123 states and 140 transitions. [2025-03-03 14:07:52,765 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-03-03 14:07:52,765 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.380952380952381) internal successors, (50), 19 states have internal predecessors, (50), 7 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) Word has length 40 [2025-03-03 14:07:52,766 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:07:52,766 INFO L225 Difference]: With dead ends: 123 [2025-03-03 14:07:52,766 INFO L226 Difference]: Without dead ends: 121 [2025-03-03 14:07:52,767 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 62 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 160 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=169, Invalid=761, Unknown=0, NotChecked=0, Total=930 [2025-03-03 14:07:52,767 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 18 mSDsluCounter, 200 mSDsCounter, 0 mSdLazyCounter, 289 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 220 SdHoareTripleChecker+Invalid, 308 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 289 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-03-03 14:07:52,767 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 220 Invalid, 308 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 289 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-03-03 14:07:52,768 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2025-03-03 14:07:52,783 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 118. [2025-03-03 14:07:52,784 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 94 states have (on average 1.148936170212766) internal successors, (108), 99 states have internal predecessors, (108), 14 states have call successors, (14), 9 states have call predecessors, (14), 9 states have return successors, (13), 9 states have call predecessors, (13), 13 states have call successors, (13) [2025-03-03 14:07:52,785 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 135 transitions. [2025-03-03 14:07:52,785 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 135 transitions. Word has length 40 [2025-03-03 14:07:52,785 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:07:52,785 INFO L471 AbstractCegarLoop]: Abstraction has 118 states and 135 transitions. [2025-03-03 14:07:52,785 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.380952380952381) internal successors, (50), 19 states have internal predecessors, (50), 7 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-03 14:07:52,785 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 135 transitions. [2025-03-03 14:07:52,786 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2025-03-03 14:07:52,786 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:07:52,786 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:07:52,791 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-03 14:07:52,986 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:52,987 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:07:52,987 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:07:52,987 INFO L85 PathProgramCache]: Analyzing trace with hash 100209031, now seen corresponding path program 2 times [2025-03-03 14:07:52,987 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:07:52,987 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [293216606] [2025-03-03 14:07:52,987 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:07:52,987 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:07:52,993 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 40 statements into 2 equivalence classes. [2025-03-03 14:07:53,026 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 40 of 40 statements. [2025-03-03 14:07:53,027 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:07:53,027 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:07:53,028 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1353806753] [2025-03-03 14:07:53,028 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:07:53,028 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:07:53,028 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:07:53,031 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:07:53,032 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-03 14:07:53,054 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 40 statements into 2 equivalence classes. [2025-03-03 14:07:53,081 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 40 of 40 statements. [2025-03-03 14:07:53,081 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:07:53,081 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:07:53,082 INFO L256 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 33 conjuncts are in the unsatisfiable core [2025-03-03 14:07:53,084 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:07:53,640 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 5 proven. 34 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-03 14:07:53,640 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:08:11,952 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 14 proven. 25 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-03-03 14:08:11,952 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:08:11,952 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [293216606] [2025-03-03 14:08:11,952 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:08:11,952 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1353806753] [2025-03-03 14:08:11,952 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1353806753] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:08:11,953 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 14:08:11,953 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14] total 25 [2025-03-03 14:08:11,953 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2092899197] [2025-03-03 14:08:11,953 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 14:08:11,953 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-03 14:08:11,953 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:08:11,954 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-03 14:08:11,954 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=489, Unknown=1, NotChecked=0, Total=600 [2025-03-03 14:08:11,954 INFO L87 Difference]: Start difference. First operand 118 states and 135 transitions. Second operand has 25 states, 25 states have (on average 2.0) internal successors, (50), 23 states have internal predecessors, (50), 8 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-03 14:08:27,252 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:08:27,253 INFO L93 Difference]: Finished difference Result 168 states and 202 transitions. [2025-03-03 14:08:27,253 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-03 14:08:27,253 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 2.0) internal successors, (50), 23 states have internal predecessors, (50), 8 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 40 [2025-03-03 14:08:27,253 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:08:27,254 INFO L225 Difference]: With dead ends: 168 [2025-03-03 14:08:27,254 INFO L226 Difference]: Without dead ends: 166 [2025-03-03 14:08:27,255 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 55 SyntacticMatches, 2 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 220 ImplicationChecksByTransitivity, 28.0s TimeCoverageRelationStatistics Valid=217, Invalid=838, Unknown=1, NotChecked=0, Total=1056 [2025-03-03 14:08:27,255 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 24 mSDsluCounter, 195 mSDsCounter, 0 mSdLazyCounter, 292 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 215 SdHoareTripleChecker+Invalid, 309 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 292 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.2s IncrementalHoareTripleChecker+Time [2025-03-03 14:08:27,255 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 215 Invalid, 309 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 292 Invalid, 0 Unknown, 0 Unchecked, 4.2s Time] [2025-03-03 14:08:27,256 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2025-03-03 14:08:27,271 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 158. [2025-03-03 14:08:27,272 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 158 states, 127 states have (on average 1.204724409448819) internal successors, (153), 132 states have internal predecessors, (153), 20 states have call successors, (20), 10 states have call predecessors, (20), 10 states have return successors, (19), 15 states have call predecessors, (19), 19 states have call successors, (19) [2025-03-03 14:08:27,272 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 192 transitions. [2025-03-03 14:08:27,272 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 192 transitions. Word has length 40 [2025-03-03 14:08:27,273 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:08:27,273 INFO L471 AbstractCegarLoop]: Abstraction has 158 states and 192 transitions. [2025-03-03 14:08:27,273 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 2.0) internal successors, (50), 23 states have internal predecessors, (50), 8 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-03 14:08:27,273 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 192 transitions. [2025-03-03 14:08:27,274 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2025-03-03 14:08:27,274 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:08:27,274 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:08:27,280 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2025-03-03 14:08:27,474 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:08:27,474 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:08:27,474 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:08:27,475 INFO L85 PathProgramCache]: Analyzing trace with hash 1000933906, now seen corresponding path program 2 times [2025-03-03 14:08:27,475 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:08:27,475 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1963885318] [2025-03-03 14:08:27,475 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:08:27,475 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:08:27,478 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 50 statements into 2 equivalence classes. [2025-03-03 14:08:27,491 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 50 of 50 statements. [2025-03-03 14:08:27,492 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:08:27,492 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:08:27,719 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 8 proven. 44 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-03 14:08:27,719 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:08:27,719 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1963885318] [2025-03-03 14:08:27,719 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1963885318] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:08:27,719 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [350459375] [2025-03-03 14:08:27,720 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:08:27,720 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:08:27,720 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:08:27,722 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:08:27,724 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-03 14:08:27,753 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 50 statements into 2 equivalence classes. [2025-03-03 14:08:27,768 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 50 of 50 statements. [2025-03-03 14:08:27,768 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:08:27,768 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:08:27,768 INFO L256 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-03-03 14:08:27,769 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:08:27,808 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 8 proven. 68 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 14:08:27,808 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:08:27,879 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 8 proven. 44 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-03-03 14:08:27,879 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [350459375] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:08:27,879 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:08:27,879 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 7, 8] total 17 [2025-03-03 14:08:27,879 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [483683165] [2025-03-03 14:08:27,879 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:08:27,880 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-03 14:08:27,880 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:08:27,880 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-03 14:08:27,880 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=166, Unknown=0, NotChecked=0, Total=272 [2025-03-03 14:08:27,881 INFO L87 Difference]: Start difference. First operand 158 states and 192 transitions. Second operand has 17 states, 17 states have (on average 4.588235294117647) internal successors, (78), 17 states have internal predecessors, (78), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2025-03-03 14:08:27,989 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:08:27,989 INFO L93 Difference]: Finished difference Result 395 states and 465 transitions. [2025-03-03 14:08:27,989 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-03-03 14:08:27,989 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 4.588235294117647) internal successors, (78), 17 states have internal predecessors, (78), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) Word has length 50 [2025-03-03 14:08:27,990 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:08:27,991 INFO L225 Difference]: With dead ends: 395 [2025-03-03 14:08:27,991 INFO L226 Difference]: Without dead ends: 388 [2025-03-03 14:08:27,992 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 92 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=215, Invalid=385, Unknown=0, NotChecked=0, Total=600 [2025-03-03 14:08:27,992 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 92 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 92 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:08:27,992 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [92 Valid, 142 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:08:27,993 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 388 states. [2025-03-03 14:08:28,018 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 388 to 344. [2025-03-03 14:08:28,019 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 344 states, 275 states have (on average 1.1418181818181818) internal successors, (314), 282 states have internal predecessors, (314), 36 states have call successors, (36), 32 states have call predecessors, (36), 32 states have return successors, (35), 29 states have call predecessors, (35), 35 states have call successors, (35) [2025-03-03 14:08:28,020 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 344 states to 344 states and 385 transitions. [2025-03-03 14:08:28,020 INFO L78 Accepts]: Start accepts. Automaton has 344 states and 385 transitions. Word has length 50 [2025-03-03 14:08:28,020 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:08:28,021 INFO L471 AbstractCegarLoop]: Abstraction has 344 states and 385 transitions. [2025-03-03 14:08:28,021 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 4.588235294117647) internal successors, (78), 17 states have internal predecessors, (78), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2025-03-03 14:08:28,021 INFO L276 IsEmpty]: Start isEmpty. Operand 344 states and 385 transitions. [2025-03-03 14:08:28,022 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2025-03-03 14:08:28,022 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:08:28,022 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1] [2025-03-03 14:08:28,028 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-03-03 14:08:28,222 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-03 14:08:28,222 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:08:28,223 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:08:28,223 INFO L85 PathProgramCache]: Analyzing trace with hash -1171091893, now seen corresponding path program 2 times [2025-03-03 14:08:28,223 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:08:28,223 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1926159902] [2025-03-03 14:08:28,223 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:08:28,223 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:08:28,226 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 50 statements into 2 equivalence classes. [2025-03-03 14:08:28,245 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 50 of 50 statements. [2025-03-03 14:08:28,245 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:08:28,245 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:08:28,246 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1534770372] [2025-03-03 14:08:28,246 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:08:28,246 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:08:28,246 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:08:28,251 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:08:28,252 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-03 14:08:28,274 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 50 statements into 2 equivalence classes. [2025-03-03 14:08:28,291 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 50 of 50 statements. [2025-03-03 14:08:28,291 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:08:28,291 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:08:28,292 INFO L256 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 42 conjuncts are in the unsatisfiable core [2025-03-03 14:08:28,294 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:08:29,009 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 18 proven. 50 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-03-03 14:08:29,010 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:08:30,296 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:08:30,296 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1926159902] [2025-03-03 14:08:30,296 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:08:30,296 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1534770372] [2025-03-03 14:08:30,296 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1534770372] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:08:30,296 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:08:30,296 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2025-03-03 14:08:30,297 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [4078420] [2025-03-03 14:08:30,297 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:08:30,297 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2025-03-03 14:08:30,297 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:08:30,297 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2025-03-03 14:08:30,297 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=575, Unknown=0, NotChecked=0, Total=702 [2025-03-03 14:08:30,298 INFO L87 Difference]: Start difference. First operand 344 states and 385 transitions. Second operand has 18 states, 18 states have (on average 1.9444444444444444) internal successors, (35), 17 states have internal predecessors, (35), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-03 14:08:30,636 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:08:30,637 INFO L93 Difference]: Finished difference Result 346 states and 386 transitions. [2025-03-03 14:08:30,637 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2025-03-03 14:08:30,637 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 1.9444444444444444) internal successors, (35), 17 states have internal predecessors, (35), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 50 [2025-03-03 14:08:30,637 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:08:30,639 INFO L225 Difference]: With dead ends: 346 [2025-03-03 14:08:30,639 INFO L226 Difference]: Without dead ends: 344 [2025-03-03 14:08:30,639 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 51 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 252 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=135, Invalid=621, Unknown=0, NotChecked=0, Total=756 [2025-03-03 14:08:30,639 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 13 mSDsluCounter, 209 mSDsCounter, 0 mSdLazyCounter, 439 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 233 SdHoareTripleChecker+Invalid, 440 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 439 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-03 14:08:30,640 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 233 Invalid, 440 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 439 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-03 14:08:30,640 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 344 states. [2025-03-03 14:08:30,672 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 344 to 344. [2025-03-03 14:08:30,673 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 344 states, 275 states have (on average 1.1381818181818182) internal successors, (313), 282 states have internal predecessors, (313), 36 states have call successors, (36), 32 states have call predecessors, (36), 32 states have return successors, (35), 29 states have call predecessors, (35), 35 states have call successors, (35) [2025-03-03 14:08:30,674 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 344 states to 344 states and 384 transitions. [2025-03-03 14:08:30,674 INFO L78 Accepts]: Start accepts. Automaton has 344 states and 384 transitions. Word has length 50 [2025-03-03 14:08:30,674 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:08:30,674 INFO L471 AbstractCegarLoop]: Abstraction has 344 states and 384 transitions. [2025-03-03 14:08:30,675 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 1.9444444444444444) internal successors, (35), 17 states have internal predecessors, (35), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-03 14:08:30,675 INFO L276 IsEmpty]: Start isEmpty. Operand 344 states and 384 transitions. [2025-03-03 14:08:30,676 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2025-03-03 14:08:30,676 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:08:30,676 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1] [2025-03-03 14:08:30,682 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-03-03 14:08:30,876 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:08:30,877 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:08:30,877 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:08:30,877 INFO L85 PathProgramCache]: Analyzing trace with hash -1618523792, now seen corresponding path program 3 times [2025-03-03 14:08:30,877 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:08:30,877 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [317474921] [2025-03-03 14:08:30,877 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:08:30,877 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:08:30,882 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 60 statements into 6 equivalence classes. [2025-03-03 14:08:30,926 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 60 of 60 statements. [2025-03-03 14:08:30,927 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-03 14:08:30,927 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:08:30,930 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [176079745] [2025-03-03 14:08:30,934 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:08:30,935 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:08:30,935 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:08:30,936 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:08:30,937 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-03 14:08:30,959 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 60 statements into 6 equivalence classes. [2025-03-03 14:08:31,010 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 60 of 60 statements. [2025-03-03 14:08:31,011 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-03 14:08:31,011 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:08:31,011 INFO L256 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 47 conjuncts are in the unsatisfiable core [2025-03-03 14:08:31,013 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:08:44,062 INFO L134 CoverageAnalysis]: Checked inductivity of 125 backedges. 26 proven. 77 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2025-03-03 14:08:44,062 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:08:52,124 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:08:52,124 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [317474921] [2025-03-03 14:08:52,124 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:08:52,124 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [176079745] [2025-03-03 14:08:52,124 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [176079745] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:08:52,124 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:08:52,124 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2025-03-03 14:08:52,124 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1890088326] [2025-03-03 14:08:52,124 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:08:52,124 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-03-03 14:08:52,124 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:08:52,125 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-03-03 14:08:52,125 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=140, Invalid=616, Unknown=0, NotChecked=0, Total=756 [2025-03-03 14:08:52,125 INFO L87 Difference]: Start difference. First operand 344 states and 384 transitions. Second operand has 20 states, 20 states have (on average 2.0) internal successors, (40), 19 states have internal predecessors, (40), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-03 14:08:56,936 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.16s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2025-03-03 14:08:57,739 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:08:57,739 INFO L93 Difference]: Finished difference Result 349 states and 389 transitions. [2025-03-03 14:08:57,739 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2025-03-03 14:08:57,740 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 2.0) internal successors, (40), 19 states have internal predecessors, (40), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Word has length 60 [2025-03-03 14:08:57,740 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:08:57,741 INFO L225 Difference]: With dead ends: 349 [2025-03-03 14:08:57,741 INFO L226 Difference]: Without dead ends: 347 [2025-03-03 14:08:57,741 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 59 SyntacticMatches, 4 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 300 ImplicationChecksByTransitivity, 12.3s TimeCoverageRelationStatistics Valid=147, Invalid=665, Unknown=0, NotChecked=0, Total=812 [2025-03-03 14:08:57,742 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 13 mSDsluCounter, 256 mSDsCounter, 0 mSdLazyCounter, 500 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 283 SdHoareTripleChecker+Invalid, 501 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 500 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.6s IncrementalHoareTripleChecker+Time [2025-03-03 14:08:57,742 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 283 Invalid, 501 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 500 Invalid, 0 Unknown, 0 Unchecked, 5.6s Time] [2025-03-03 14:08:57,742 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 347 states. [2025-03-03 14:08:57,764 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 347 to 334. [2025-03-03 14:08:57,765 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 334 states, 267 states have (on average 1.1348314606741574) internal successors, (303), 274 states have internal predecessors, (303), 35 states have call successors, (35), 31 states have call predecessors, (35), 31 states have return successors, (34), 28 states have call predecessors, (34), 34 states have call successors, (34) [2025-03-03 14:08:57,766 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 334 states to 334 states and 372 transitions. [2025-03-03 14:08:57,766 INFO L78 Accepts]: Start accepts. Automaton has 334 states and 372 transitions. Word has length 60 [2025-03-03 14:08:57,766 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:08:57,766 INFO L471 AbstractCegarLoop]: Abstraction has 334 states and 372 transitions. [2025-03-03 14:08:57,767 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 2.0) internal successors, (40), 19 states have internal predecessors, (40), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-03 14:08:57,767 INFO L276 IsEmpty]: Start isEmpty. Operand 334 states and 372 transitions. [2025-03-03 14:08:57,767 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2025-03-03 14:08:57,767 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:08:57,767 INFO L218 NwaCegarLoop]: trace histogram [7, 7, 7, 7, 6, 6, 6, 6, 6, 3, 3, 1, 1, 1, 1, 1, 1] [2025-03-03 14:08:57,773 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-03 14:08:57,968 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2025-03-03 14:08:57,968 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:08:57,968 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:08:57,968 INFO L85 PathProgramCache]: Analyzing trace with hash 1467073720, now seen corresponding path program 3 times [2025-03-03 14:08:57,968 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:08:57,968 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2054112816] [2025-03-03 14:08:57,968 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:08:57,968 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:08:57,972 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 70 statements into 7 equivalence classes. [2025-03-03 14:08:57,997 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) and asserted 70 of 70 statements. [2025-03-03 14:08:57,998 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2025-03-03 14:08:57,998 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:08:57,999 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [908057827] [2025-03-03 14:08:57,999 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:08:57,999 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:08:57,999 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:08:58,000 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:08:58,002 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-03 14:08:58,047 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 70 statements into 7 equivalence classes. [2025-03-03 14:08:58,065 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 50 of 70 statements. [2025-03-03 14:08:58,065 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-03-03 14:08:58,065 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:08:58,066 INFO L256 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 35 conjuncts are in the unsatisfiable core [2025-03-03 14:08:58,068 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:09:04,367 INFO L134 CoverageAnalysis]: Checked inductivity of 180 backedges. 122 proven. 8 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2025-03-03 14:09:04,367 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:09:08,806 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:09:08,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2054112816] [2025-03-03 14:09:08,806 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-03-03 14:09:08,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [908057827] [2025-03-03 14:09:08,809 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [908057827] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:09:08,809 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2025-03-03 14:09:08,809 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2025-03-03 14:09:08,810 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [722650799] [2025-03-03 14:09:08,810 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2025-03-03 14:09:08,810 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-03 14:09:08,810 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:09:08,810 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-03 14:09:08,810 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=158, Invalid=492, Unknown=0, NotChecked=0, Total=650 [2025-03-03 14:09:08,810 INFO L87 Difference]: Start difference. First operand 334 states and 372 transitions. Second operand has 17 states, 17 states have (on average 2.235294117647059) internal successors, (38), 15 states have internal predecessors, (38), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-03 14:09:13,511 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-03 14:09:14,950 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:09:14,950 INFO L93 Difference]: Finished difference Result 494 states and 553 transitions. [2025-03-03 14:09:14,950 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2025-03-03 14:09:14,951 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.235294117647059) internal successors, (38), 15 states have internal predecessors, (38), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 70 [2025-03-03 14:09:14,951 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:09:14,953 INFO L225 Difference]: With dead ends: 494 [2025-03-03 14:09:14,953 INFO L226 Difference]: Without dead ends: 492 [2025-03-03 14:09:14,953 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 69 SyntacticMatches, 6 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 295 ImplicationChecksByTransitivity, 8.3s TimeCoverageRelationStatistics Valid=203, Invalid=609, Unknown=0, NotChecked=0, Total=812 [2025-03-03 14:09:14,954 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 15 mSDsluCounter, 214 mSDsCounter, 0 mSdLazyCounter, 244 mSolverCounterSat, 4 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 249 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 244 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.4s IncrementalHoareTripleChecker+Time [2025-03-03 14:09:14,954 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 249 Invalid, 249 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 244 Invalid, 1 Unknown, 0 Unchecked, 4.4s Time] [2025-03-03 14:09:14,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 492 states. [2025-03-03 14:09:14,989 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 492 to 202. [2025-03-03 14:09:14,989 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 202 states, 162 states have (on average 1.154320987654321) internal successors, (187), 163 states have internal predecessors, (187), 20 states have call successors, (20), 19 states have call predecessors, (20), 19 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2025-03-03 14:09:14,990 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 202 states to 202 states and 226 transitions. [2025-03-03 14:09:14,990 INFO L78 Accepts]: Start accepts. Automaton has 202 states and 226 transitions. Word has length 70 [2025-03-03 14:09:14,990 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:09:14,991 INFO L471 AbstractCegarLoop]: Abstraction has 202 states and 226 transitions. [2025-03-03 14:09:14,991 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.235294117647059) internal successors, (38), 15 states have internal predecessors, (38), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-03-03 14:09:14,991 INFO L276 IsEmpty]: Start isEmpty. Operand 202 states and 226 transitions. [2025-03-03 14:09:14,991 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2025-03-03 14:09:14,991 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:09:14,991 INFO L218 NwaCegarLoop]: trace histogram [7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1] [2025-03-03 14:09:14,997 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-03 14:09:15,192 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-03-03 14:09:15,192 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:09:15,192 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:09:15,192 INFO L85 PathProgramCache]: Analyzing trace with hash 2138839637, now seen corresponding path program 4 times [2025-03-03 14:09:15,192 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:09:15,192 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1907430870] [2025-03-03 14:09:15,192 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-03 14:09:15,193 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:09:15,196 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 70 statements into 2 equivalence classes. [2025-03-03 14:09:15,222 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 70 of 70 statements. [2025-03-03 14:09:15,222 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-03 14:09:15,222 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-03-03 14:09:15,223 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [660910958] [2025-03-03 14:09:15,223 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-03 14:09:15,223 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:09:15,223 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:09:15,225 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:09:15,226 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-03 14:09:15,252 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 70 statements into 2 equivalence classes. [2025-03-03 14:09:15,283 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 70 of 70 statements. [2025-03-03 14:09:15,284 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-03 14:09:15,284 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:09:15,290 INFO L256 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 55 conjuncts are in the unsatisfiable core [2025-03-03 14:09:15,292 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:09:16,269 INFO L134 CoverageAnalysis]: Checked inductivity of 180 backedges. 19 proven. 125 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-03-03 14:09:16,269 INFO L312 TraceCheckSpWp]: Computing backward predicates...