./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound20.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version fca748b1 Calling Ultimate with: /root/.sdkman/candidates/java/current/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.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps6-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 946e199240c0e980bd422384e40e4d2247ef6b3560471b18ba5a354c3628dba9 --- Real Ultimate output --- This is Ultimate 0.2.5-wip.dd.update-z3-fca748b-m [2024-11-19 21:35:35,680 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-19 21:35:35,743 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-19 21:35:35,747 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-19 21:35:35,747 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-19 21:35:35,765 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-19 21:35:35,766 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-19 21:35:35,766 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-19 21:35:35,766 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-19 21:35:35,767 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-19 21:35:35,767 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-19 21:35:35,767 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-19 21:35:35,768 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-19 21:35:35,768 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-19 21:35:35,769 INFO L153 SettingsManager]: * Use SBE=true [2024-11-19 21:35:35,769 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-19 21:35:35,769 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-19 21:35:35,770 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-19 21:35:35,770 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-19 21:35:35,770 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-19 21:35:35,771 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-19 21:35:35,774 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-19 21:35:35,774 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-19 21:35:35,774 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-19 21:35:35,775 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-19 21:35:35,775 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-19 21:35:35,775 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-19 21:35:35,775 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-19 21:35:35,775 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-19 21:35:35,776 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-19 21:35:35,776 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-19 21:35:35,776 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-19 21:35:35,776 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-19 21:35:35,776 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-19 21:35:35,776 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-19 21:35:35,777 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-19 21:35:35,777 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-19 21:35:35,777 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-19 21:35:35,778 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-19 21:35:35,779 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-19 21:35:35,779 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-19 21:35:35,779 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-19 21:35:35,779 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release 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 -> 946e199240c0e980bd422384e40e4d2247ef6b3560471b18ba5a354c3628dba9 [2024-11-19 21:35:36,056 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-19 21:35:36,077 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-19 21:35:36,080 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-19 21:35:36,081 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-19 21:35:36,081 INFO L274 PluginConnector]: CDTParser initialized [2024-11-19 21:35:36,082 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound20.c [2024-11-19 21:35:37,407 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-19 21:35:37,605 INFO L384 CDTParser]: Found 1 translation units. [2024-11-19 21:35:37,605 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps6-ll_unwindbound20.c [2024-11-19 21:35:37,613 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8d9b41383/360d57b664e44e5b95fce06b39aacd23/FLAG4d6626fcb [2024-11-19 21:35:37,984 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8d9b41383/360d57b664e44e5b95fce06b39aacd23 [2024-11-19 21:35:37,988 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-19 21:35:37,989 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-19 21:35:37,990 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-19 21:35:37,990 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-19 21:35:37,995 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-19 21:35:37,996 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 09:35:37" (1/1) ... [2024-11-19 21:35:37,996 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2796711d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:37, skipping insertion in model container [2024-11-19 21:35:37,997 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 09:35:37" (1/1) ... [2024-11-19 21:35:38,013 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-19 21:35:38,195 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/ps6-ll_unwindbound20.c[458,471] [2024-11-19 21:35:38,223 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 21:35:38,233 INFO L200 MainTranslator]: Completed pre-run [2024-11-19 21:35:38,245 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/ps6-ll_unwindbound20.c[458,471] [2024-11-19 21:35:38,255 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 21:35:38,271 INFO L204 MainTranslator]: Completed translation [2024-11-19 21:35:38,272 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38 WrapperNode [2024-11-19 21:35:38,272 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-19 21:35:38,273 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-19 21:35:38,273 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-19 21:35:38,274 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-19 21:35:38,280 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38" (1/1) ... [2024-11-19 21:35:38,286 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38" (1/1) ... [2024-11-19 21:35:38,302 INFO L138 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 43 [2024-11-19 21:35:38,302 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-19 21:35:38,303 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-19 21:35:38,303 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-19 21:35:38,304 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-19 21:35:38,312 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38" (1/1) ... [2024-11-19 21:35:38,312 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38" (1/1) ... [2024-11-19 21:35:38,314 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38" (1/1) ... [2024-11-19 21:35:38,326 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]. [2024-11-19 21:35:38,326 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38" (1/1) ... [2024-11-19 21:35:38,327 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38" (1/1) ... [2024-11-19 21:35:38,329 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38" (1/1) ... [2024-11-19 21:35:38,335 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38" (1/1) ... [2024-11-19 21:35:38,336 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38" (1/1) ... [2024-11-19 21:35:38,337 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38" (1/1) ... [2024-11-19 21:35:38,338 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-19 21:35:38,339 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-19 21:35:38,339 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-19 21:35:38,339 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-19 21:35:38,340 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38" (1/1) ... [2024-11-19 21:35:38,346 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-19 21:35:38,358 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:35:38,374 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) [2024-11-19 21:35:38,377 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 [2024-11-19 21:35:38,416 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-19 21:35:38,417 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-19 21:35:38,417 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-19 21:35:38,418 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-19 21:35:38,418 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-19 21:35:38,418 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-19 21:35:38,466 INFO L238 CfgBuilder]: Building ICFG [2024-11-19 21:35:38,468 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-19 21:35:38,587 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-19 21:35:38,587 INFO L287 CfgBuilder]: Performing block encoding [2024-11-19 21:35:38,604 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-19 21:35:38,606 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-19 21:35:38,606 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 09:35:38 BoogieIcfgContainer [2024-11-19 21:35:38,606 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-19 21:35:38,609 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-19 21:35:38,611 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-19 21:35:38,614 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-19 21:35:38,615 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.11 09:35:37" (1/3) ... [2024-11-19 21:35:38,615 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b068622 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 09:35:38, skipping insertion in model container [2024-11-19 21:35:38,616 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 09:35:38" (2/3) ... [2024-11-19 21:35:38,616 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b068622 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.11 09:35:38, skipping insertion in model container [2024-11-19 21:35:38,617 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 09:35:38" (3/3) ... [2024-11-19 21:35:38,618 INFO L112 eAbstractionObserver]: Analyzing ICFG ps6-ll_unwindbound20.c [2024-11-19 21:35:38,636 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-19 21:35:38,636 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-19 21:35:38,699 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-19 21:35:38,708 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;@486d7710, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-19 21:35:38,709 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-19 21:35:38,713 INFO L276 IsEmpty]: Start isEmpty. Operand has 20 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-19 21:35:38,719 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-19 21:35:38,719 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:35:38,720 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:35:38,720 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:35:38,726 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:35:38,727 INFO L85 PathProgramCache]: Analyzing trace with hash -579246775, now seen corresponding path program 1 times [2024-11-19 21:35:38,734 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:35:38,734 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1024141978] [2024-11-19 21:35:38,734 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:38,735 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:35:38,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:38,893 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 21:35:38,894 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:35:38,894 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1024141978] [2024-11-19 21:35:38,894 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1024141978] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:35:38,895 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:35:38,895 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-19 21:35:38,896 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [290143034] [2024-11-19 21:35:38,897 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:35:38,899 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-19 21:35:38,900 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:35:38,919 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-19 21:35:38,919 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-19 21:35:38,922 INFO L87 Difference]: Start difference. First operand has 20 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) 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) [2024-11-19 21:35:38,937 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:35:38,937 INFO L93 Difference]: Finished difference Result 37 states and 51 transitions. [2024-11-19 21:35:38,938 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-19 21:35:38,939 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 [2024-11-19 21:35:38,939 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:35:38,945 INFO L225 Difference]: With dead ends: 37 [2024-11-19 21:35:38,945 INFO L226 Difference]: Without dead ends: 16 [2024-11-19 21:35:38,948 INFO L431 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 [2024-11-19 21:35:38,953 INFO L432 NwaCegarLoop]: 23 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, 23 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 [2024-11-19 21:35:38,954 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:35:38,969 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2024-11-19 21:35:38,985 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2024-11-19 21:35:38,986 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 11 states have (on average 1.2727272727272727) internal successors, (14), 12 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-19 21:35:38,986 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 19 transitions. [2024-11-19 21:35:38,989 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 19 transitions. Word has length 9 [2024-11-19 21:35:38,989 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:35:38,989 INFO L471 AbstractCegarLoop]: Abstraction has 16 states and 19 transitions. [2024-11-19 21:35:38,990 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) [2024-11-19 21:35:38,990 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 19 transitions. [2024-11-19 21:35:38,990 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-19 21:35:38,990 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:35:38,990 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:35:38,991 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-19 21:35:38,991 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:35:38,991 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:35:38,991 INFO L85 PathProgramCache]: Analyzing trace with hash -1986551203, now seen corresponding path program 1 times [2024-11-19 21:35:38,991 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:35:38,992 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [209302526] [2024-11-19 21:35:38,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:38,992 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:35:39,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:39,087 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 21:35:39,091 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:35:39,091 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [209302526] [2024-11-19 21:35:39,091 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [209302526] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:35:39,091 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:35:39,092 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-19 21:35:39,092 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [63637485] [2024-11-19 21:35:39,092 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:35:39,093 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-19 21:35:39,093 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:35:39,094 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-19 21:35:39,094 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-19 21:35:39,094 INFO L87 Difference]: Start difference. First operand 16 states and 19 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) [2024-11-19 21:35:39,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:35:39,117 INFO L93 Difference]: Finished difference Result 26 states and 30 transitions. [2024-11-19 21:35:39,117 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-19 21:35:39,117 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 [2024-11-19 21:35:39,118 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:35:39,118 INFO L225 Difference]: With dead ends: 26 [2024-11-19 21:35:39,119 INFO L226 Difference]: Without dead ends: 18 [2024-11-19 21:35:39,119 INFO L431 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 [2024-11-19 21:35:39,121 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 0 mSDsluCounter, 28 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 45 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 [2024-11-19 21:35:39,122 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:35:39,122 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2024-11-19 21:35:39,127 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2024-11-19 21:35:39,131 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 14 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-19 21:35:39,132 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 21 transitions. [2024-11-19 21:35:39,132 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 21 transitions. Word has length 10 [2024-11-19 21:35:39,132 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:35:39,132 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 21 transitions. [2024-11-19 21:35:39,132 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) [2024-11-19 21:35:39,132 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 21 transitions. [2024-11-19 21:35:39,133 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-19 21:35:39,133 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:35:39,133 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:35:39,133 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-19 21:35:39,133 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:35:39,134 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:35:39,134 INFO L85 PathProgramCache]: Analyzing trace with hash -1984763743, now seen corresponding path program 1 times [2024-11-19 21:35:39,134 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:35:39,134 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [406072099] [2024-11-19 21:35:39,134 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:39,134 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:35:39,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:35:39,163 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [17330630] [2024-11-19 21:35:39,163 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:39,164 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:35:39,164 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:35:39,168 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) [2024-11-19 21:35:39,169 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-19 21:35:39,222 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:39,223 INFO L255 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-19 21:35:39,228 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:35:39,321 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 21:35:39,321 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-19 21:35:39,321 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:35:39,321 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [406072099] [2024-11-19 21:35:39,322 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:35:39,322 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [17330630] [2024-11-19 21:35:39,322 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [17330630] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 21:35:39,322 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 21:35:39,322 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-19 21:35:39,323 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1808150005] [2024-11-19 21:35:39,323 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:35:39,323 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 21:35:39,323 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:35:39,324 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 21:35:39,324 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-19 21:35:39,324 INFO L87 Difference]: Start difference. First operand 18 states and 21 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 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) [2024-11-19 21:35:39,377 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:35:39,377 INFO L93 Difference]: Finished difference Result 28 states and 33 transitions. [2024-11-19 21:35:39,378 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 21:35:39,378 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 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 [2024-11-19 21:35:39,378 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:35:39,379 INFO L225 Difference]: With dead ends: 28 [2024-11-19 21:35:39,379 INFO L226 Difference]: Without dead ends: 24 [2024-11-19 21:35:39,379 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-19 21:35:39,381 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 4 mSDsluCounter, 43 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 59 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:35:39,381 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 59 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:35:39,382 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2024-11-19 21:35:39,387 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-19 21:35:39,389 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 18 states have internal predecessors, (20), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-19 21:35:39,391 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 27 transitions. [2024-11-19 21:35:39,391 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 27 transitions. Word has length 10 [2024-11-19 21:35:39,392 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:35:39,392 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 27 transitions. [2024-11-19 21:35:39,392 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 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) [2024-11-19 21:35:39,392 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 27 transitions. [2024-11-19 21:35:39,393 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-19 21:35:39,393 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:35:39,394 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:35:39,403 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-19 21:35:39,598 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:35:39,599 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:35:39,599 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:35:39,599 INFO L85 PathProgramCache]: Analyzing trace with hash -69803837, now seen corresponding path program 1 times [2024-11-19 21:35:39,599 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:35:39,600 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1767698691] [2024-11-19 21:35:39,600 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:39,600 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:35:39,637 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:39,765 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-19 21:35:39,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:39,783 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 21:35:39,783 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:35:39,783 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1767698691] [2024-11-19 21:35:39,784 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1767698691] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 21:35:39,784 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [667411168] [2024-11-19 21:35:39,784 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:39,784 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:35:39,784 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:35:39,787 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) [2024-11-19 21:35:39,788 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-19 21:35:39,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:39,839 INFO L255 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-19 21:35:39,841 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:35:39,877 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 21:35:39,877 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:35:39,943 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 21:35:39,943 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [667411168] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:35:39,943 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 21:35:39,943 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 8 [2024-11-19 21:35:39,946 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [309213604] [2024-11-19 21:35:39,946 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 21:35:39,947 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-19 21:35:39,947 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:35:39,948 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-19 21:35:39,948 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2024-11-19 21:35:39,948 INFO L87 Difference]: Start difference. First operand 24 states and 27 transitions. Second operand has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 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) [2024-11-19 21:35:40,043 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:35:40,043 INFO L93 Difference]: Finished difference Result 58 states and 68 transitions. [2024-11-19 21:35:40,044 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-19 21:35:40,044 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 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 18 [2024-11-19 21:35:40,045 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:35:40,045 INFO L225 Difference]: With dead ends: 58 [2024-11-19 21:35:40,046 INFO L226 Difference]: Without dead ends: 50 [2024-11-19 21:35:40,046 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2024-11-19 21:35:40,047 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 23 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:35:40,048 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 67 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:35:40,048 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2024-11-19 21:35:40,056 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 46. [2024-11-19 21:35:40,056 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 31 states have (on average 1.2258064516129032) internal successors, (38), 34 states have internal predecessors, (38), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-19 21:35:40,058 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 55 transitions. [2024-11-19 21:35:40,058 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 55 transitions. Word has length 18 [2024-11-19 21:35:40,058 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:35:40,058 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 55 transitions. [2024-11-19 21:35:40,058 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 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) [2024-11-19 21:35:40,058 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 55 transitions. [2024-11-19 21:35:40,059 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-19 21:35:40,059 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:35:40,059 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:35:40,068 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-19 21:35:40,263 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 [2024-11-19 21:35:40,264 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:35:40,264 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:35:40,264 INFO L85 PathProgramCache]: Analyzing trace with hash -68016377, now seen corresponding path program 1 times [2024-11-19 21:35:40,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:35:40,265 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [838145186] [2024-11-19 21:35:40,265 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:40,265 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:35:40,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:35:40,285 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1964726536] [2024-11-19 21:35:40,285 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:40,285 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:35:40,285 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:35:40,288 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) [2024-11-19 21:35:40,291 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-19 21:35:40,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:40,330 INFO L255 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-19 21:35:40,332 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:35:40,411 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 21:35:40,411 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:35:40,505 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-19 21:35:40,507 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:35:40,507 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [838145186] [2024-11-19 21:35:40,507 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:35:40,507 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1964726536] [2024-11-19 21:35:40,507 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1964726536] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-19 21:35:40,507 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-19 21:35:40,507 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-19 21:35:40,508 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1003366561] [2024-11-19 21:35:40,508 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 21:35:40,509 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-19 21:35:40,509 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:35:40,510 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-19 21:35:40,510 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-19 21:35:40,511 INFO L87 Difference]: Start difference. First operand 46 states and 55 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 21:35:40,569 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:35:40,570 INFO L93 Difference]: Finished difference Result 60 states and 68 transitions. [2024-11-19 21:35:40,570 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-19 21:35:40,570 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 18 [2024-11-19 21:35:40,571 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:35:40,572 INFO L225 Difference]: With dead ends: 60 [2024-11-19 21:35:40,574 INFO L226 Difference]: Without dead ends: 52 [2024-11-19 21:35:40,575 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 27 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-19 21:35:40,576 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 5 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 47 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-19 21:35:40,576 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 47 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-19 21:35:40,577 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2024-11-19 21:35:40,611 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 46. [2024-11-19 21:35:40,612 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 33 states have (on average 1.121212121212121) internal successors, (37), 35 states have internal predecessors, (37), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-19 21:35:40,613 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 52 transitions. [2024-11-19 21:35:40,617 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 52 transitions. Word has length 18 [2024-11-19 21:35:40,617 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:35:40,617 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 52 transitions. [2024-11-19 21:35:40,618 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 21:35:40,618 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 52 transitions. [2024-11-19 21:35:40,618 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-19 21:35:40,618 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:35:40,618 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:35:40,630 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-19 21:35:40,819 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 [2024-11-19 21:35:40,819 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:35:40,820 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:35:40,820 INFO L85 PathProgramCache]: Analyzing trace with hash 156635680, now seen corresponding path program 1 times [2024-11-19 21:35:40,820 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:35:40,820 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [101556097] [2024-11-19 21:35:40,820 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:40,820 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:35:40,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:35:40,840 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [308183203] [2024-11-19 21:35:40,840 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:40,840 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:35:40,841 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:35:40,843 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) [2024-11-19 21:35:40,846 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-19 21:35:40,884 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:40,885 INFO L255 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-19 21:35:40,887 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:35:40,979 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-19 21:35:40,979 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:35:41,095 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-19 21:35:41,097 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:35:41,098 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [101556097] [2024-11-19 21:35:41,098 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:35:41,098 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [308183203] [2024-11-19 21:35:41,098 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [308183203] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:35:41,098 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:35:41,098 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2024-11-19 21:35:41,099 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1462396034] [2024-11-19 21:35:41,099 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:35:41,099 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-19 21:35:41,099 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:35:41,100 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-19 21:35:41,100 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-19 21:35:41,100 INFO L87 Difference]: Start difference. First operand 46 states and 52 transitions. Second operand has 12 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 6 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-19 21:35:41,217 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:35:41,218 INFO L93 Difference]: Finished difference Result 55 states and 63 transitions. [2024-11-19 21:35:41,220 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-19 21:35:41,220 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 6 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 29 [2024-11-19 21:35:41,220 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:35:41,221 INFO L225 Difference]: With dead ends: 55 [2024-11-19 21:35:41,221 INFO L226 Difference]: Without dead ends: 46 [2024-11-19 21:35:41,221 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 46 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2024-11-19 21:35:41,222 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 2 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 53 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:35:41,222 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 118 Invalid, 53 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:35:41,222 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-19 21:35:41,239 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2024-11-19 21:35:41,240 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 34 states have (on average 1.0588235294117647) internal successors, (36), 34 states have internal predecessors, (36), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-19 21:35:41,240 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 49 transitions. [2024-11-19 21:35:41,241 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 49 transitions. Word has length 29 [2024-11-19 21:35:41,241 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:35:41,241 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 49 transitions. [2024-11-19 21:35:41,241 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 6 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-19 21:35:41,241 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 49 transitions. [2024-11-19 21:35:41,242 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-19 21:35:41,242 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:35:41,243 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:35:41,251 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-19 21:35:41,446 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 [2024-11-19 21:35:41,447 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:35:41,447 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:35:41,447 INFO L85 PathProgramCache]: Analyzing trace with hash -1854611729, now seen corresponding path program 1 times [2024-11-19 21:35:41,447 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:35:41,447 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [8440716] [2024-11-19 21:35:41,448 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:41,448 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:35:41,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:41,669 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-19 21:35:41,672 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:41,676 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-19 21:35:41,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:41,685 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-11-19 21:35:41,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:41,692 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-19 21:35:41,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:41,696 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-11-19 21:35:41,700 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:41,702 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-19 21:35:41,702 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:35:41,702 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [8440716] [2024-11-19 21:35:41,702 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [8440716] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 21:35:41,703 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1266959028] [2024-11-19 21:35:41,703 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:41,703 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:35:41,703 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:35:41,707 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) [2024-11-19 21:35:41,708 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-19 21:35:41,762 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 21:35:41,764 INFO L255 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-19 21:35:41,765 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:35:41,845 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 24 proven. 56 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-19 21:35:41,845 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:35:41,984 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-19 21:35:41,985 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1266959028] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:35:41,985 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 21:35:41,985 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 8] total 14 [2024-11-19 21:35:41,985 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [284744955] [2024-11-19 21:35:41,985 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 21:35:41,987 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-19 21:35:41,987 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:35:41,988 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-19 21:35:41,988 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2024-11-19 21:35:41,988 INFO L87 Difference]: Start difference. First operand 46 states and 49 transitions. Second operand has 14 states, 14 states have (on average 4.0) internal successors, (56), 14 states have internal predecessors, (56), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) [2024-11-19 21:35:42,238 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:35:42,238 INFO L93 Difference]: Finished difference Result 132 states and 144 transitions. [2024-11-19 21:35:42,239 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-19 21:35:42,239 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.0) internal successors, (56), 14 states have internal predecessors, (56), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) Word has length 47 [2024-11-19 21:35:42,239 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:35:42,240 INFO L225 Difference]: With dead ends: 132 [2024-11-19 21:35:42,240 INFO L226 Difference]: Without dead ends: 122 [2024-11-19 21:35:42,241 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2024-11-19 21:35:42,242 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 65 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 63 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 72 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 63 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:35:42,242 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 101 Invalid, 72 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 63 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:35:42,243 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2024-11-19 21:35:42,267 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 97. [2024-11-19 21:35:42,267 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 69 states have (on average 1.1014492753623188) internal successors, (76), 74 states have internal predecessors, (76), 17 states have call successors, (17), 11 states have call predecessors, (17), 10 states have return successors, (16), 11 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-19 21:35:42,268 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 109 transitions. [2024-11-19 21:35:42,268 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 109 transitions. Word has length 47 [2024-11-19 21:35:42,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:35:42,269 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 109 transitions. [2024-11-19 21:35:42,269 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.0) internal successors, (56), 14 states have internal predecessors, (56), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) [2024-11-19 21:35:42,269 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 109 transitions. [2024-11-19 21:35:42,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2024-11-19 21:35:42,270 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:35:42,271 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:35:42,279 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-19 21:35:42,474 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 [2024-11-19 21:35:42,475 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:35:42,475 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:35:42,475 INFO L85 PathProgramCache]: Analyzing trace with hash 348710830, now seen corresponding path program 2 times [2024-11-19 21:35:42,475 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:35:42,476 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [574411498] [2024-11-19 21:35:42,476 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:42,476 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:35:42,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:35:42,501 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [425173403] [2024-11-19 21:35:42,501 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 21:35:42,501 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:35:42,501 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:35:42,504 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) [2024-11-19 21:35:42,505 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-19 21:35:42,560 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-19 21:35:42,560 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:35:42,561 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-19 21:35:42,564 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:35:42,814 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 12 proven. 40 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-19 21:35:42,814 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:35:43,125 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 12 proven. 40 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-19 21:35:43,125 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 21:35:43,125 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [574411498] [2024-11-19 21:35:43,125 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-19 21:35:43,126 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [425173403] [2024-11-19 21:35:43,126 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [425173403] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 21:35:43,126 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-19 21:35:43,126 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 20 [2024-11-19 21:35:43,126 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1499621382] [2024-11-19 21:35:43,126 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-19 21:35:43,127 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-19 21:35:43,127 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 21:35:43,128 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-19 21:35:43,128 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=313, Unknown=0, NotChecked=0, Total=380 [2024-11-19 21:35:43,128 INFO L87 Difference]: Start difference. First operand 97 states and 109 transitions. Second operand has 20 states, 18 states have (on average 2.5) internal successors, (45), 18 states have internal predecessors, (45), 12 states have call successors, (14), 3 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-19 21:35:43,557 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 21:35:43,557 INFO L93 Difference]: Finished difference Result 103 states and 114 transitions. [2024-11-19 21:35:43,557 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-19 21:35:43,558 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 2.5) internal successors, (45), 18 states have internal predecessors, (45), 12 states have call successors, (14), 3 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Word has length 53 [2024-11-19 21:35:43,558 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-19 21:35:43,559 INFO L225 Difference]: With dead ends: 103 [2024-11-19 21:35:43,559 INFO L226 Difference]: Without dead ends: 92 [2024-11-19 21:35:43,560 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 86 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 133 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=167, Invalid=703, Unknown=0, NotChecked=0, Total=870 [2024-11-19 21:35:43,560 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 24 mSDsluCounter, 249 mSDsCounter, 0 mSdLazyCounter, 155 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 281 SdHoareTripleChecker+Invalid, 162 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 155 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-19 21:35:43,560 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 281 Invalid, 162 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 155 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-19 21:35:43,561 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2024-11-19 21:35:43,588 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 92. [2024-11-19 21:35:43,590 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 69 states have (on average 1.0289855072463767) internal successors, (71), 69 states have internal predecessors, (71), 12 states have call successors, (12), 11 states have call predecessors, (12), 10 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-19 21:35:43,591 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 94 transitions. [2024-11-19 21:35:43,591 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 94 transitions. Word has length 53 [2024-11-19 21:35:43,591 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-19 21:35:43,591 INFO L471 AbstractCegarLoop]: Abstraction has 92 states and 94 transitions. [2024-11-19 21:35:43,591 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 2.5) internal successors, (45), 18 states have internal predecessors, (45), 12 states have call successors, (14), 3 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-19 21:35:43,591 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 94 transitions. [2024-11-19 21:35:43,593 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2024-11-19 21:35:43,593 INFO L207 NwaCegarLoop]: Found error trace [2024-11-19 21:35:43,593 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 21:35:43,602 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-19 21:35:43,793 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 [2024-11-19 21:35:43,794 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-19 21:35:43,794 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 21:35:43,794 INFO L85 PathProgramCache]: Analyzing trace with hash -1207691024, now seen corresponding path program 3 times [2024-11-19 21:35:43,794 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 21:35:43,794 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [863503082] [2024-11-19 21:35:43,795 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 21:35:43,795 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 21:35:43,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-19 21:35:43,840 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [509474609] [2024-11-19 21:35:43,840 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 21:35:43,840 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 21:35:43,840 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 21:35:43,842 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) [2024-11-19 21:35:43,844 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-19 21:35:43,989 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2024-11-19 21:35:43,989 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-19 21:35:43,991 INFO L255 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 54 conjuncts are in the unsatisfiable core [2024-11-19 21:35:43,994 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 21:35:44,295 INFO L134 CoverageAnalysis]: Checked inductivity of 422 backedges. 45 proven. 187 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2024-11-19 21:35:44,295 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 21:35:52,438 WARN L851 $PredicateComparison]: unable to prove that (let ((.cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|))) (or (= (+ |c_ULTIMATE.start_main_~y~0#1| .cse0) (+ |c_ULTIMATE.start_main_~c~0#1| (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|))) (not (= 0 (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 7) .cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 6)) 12))))) is different from false [2024-11-19 21:36:04,495 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 4 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-19 21:36:16,607 WARN L286 SmtUtils]: Spent 8.10s on a formula simplification that was a NOOP. DAG size: 7 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-19 21:36:24,627 WARN L873 $PredicateComparison]: unable to prove that (or (not (= |c___VERIFIER_assert_#in~cond| 0)) (forall ((|v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_26| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| Int)) (let ((.cse0 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39|))) (or (= (+ |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_26| (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_26|)) (+ |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| .cse0)) (= (mod (+ .cse0 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| 7) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| 10) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| 6)) 12) 0))))) is different from true [2024-11-19 21:36:36,647 WARN L286 SmtUtils]: Spent 8.00s on a formula simplification that was a NOOP. DAG size: 7 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-19 21:36:52,684 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 7 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-19 21:37:00,717 WARN L873 $PredicateComparison]: unable to prove that (or (not (= |c___VERIFIER_assert_#in~cond| 0)) (= c___VERIFIER_assert_~cond 0) (forall ((|v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_26| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| Int)) (let ((.cse0 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39|))) (or (= (+ |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_26| (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~c~0#1_BEFORE_CALL_26|)) (+ |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| .cse0)) (= (mod (+ .cse0 (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| 7) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| 10) (* |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_39| 6)) 12) 0))))) is different from true [2024-11-19 21:37:16,803 WARN L851 $PredicateComparison]: unable to prove that (let ((.cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1|))) (or (not (= 0 (mod (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 10) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 7) .cse0 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| 6)) 12))) (= (+ .cse0 (* |c_ULTIMATE.start_main_~y~0#1| 2)) (+ (* |c_ULTIMATE.start_main_~c~0#1| 2) (* |c_ULTIMATE.start_main_~c~0#1| |c_ULTIMATE.start_main_~y~0#1|))))) is different from false