./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursive-simple/fibo_2calls_8-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3061b6dc Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/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 ../sv-benchmarks/c/recursive-simple/fibo_2calls_8-2.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 5952061731474d390646c291ccf1d0136c1d856e30481accbc86db371431d703 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-18 14:25:17,878 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-18 14:25:17,938 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-18 14:25:17,943 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-18 14:25:17,943 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-18 14:25:17,978 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-18 14:25:17,979 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-18 14:25:17,979 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-18 14:25:17,980 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-18 14:25:17,980 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-18 14:25:17,981 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-18 14:25:17,981 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-18 14:25:17,981 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-18 14:25:17,982 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-18 14:25:17,983 INFO L153 SettingsManager]: * Use SBE=true [2024-11-18 14:25:17,983 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-18 14:25:17,984 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-18 14:25:17,984 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-18 14:25:17,984 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-18 14:25:17,984 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-18 14:25:17,984 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-18 14:25:17,987 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-18 14:25:17,987 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-18 14:25:17,988 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-18 14:25:17,988 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-18 14:25:17,988 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-18 14:25:17,988 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-18 14:25:17,988 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-18 14:25:17,988 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-18 14:25:17,989 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-18 14:25:17,989 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-18 14:25:17,989 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-18 14:25:17,989 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 14:25:17,989 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-18 14:25:17,989 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-18 14:25:17,990 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-18 14:25:17,990 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-18 14:25:17,990 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-18 14:25:17,990 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-18 14:25:17,990 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-18 14:25:17,990 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-18 14:25:17,991 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-18 14:25:17,991 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 -> 5952061731474d390646c291ccf1d0136c1d856e30481accbc86db371431d703 [2024-11-18 14:25:18,201 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-18 14:25:18,221 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-18 14:25:18,224 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-18 14:25:18,225 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-18 14:25:18,225 INFO L274 PluginConnector]: CDTParser initialized [2024-11-18 14:25:18,226 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_2calls_8-2.c [2024-11-18 14:25:19,476 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-18 14:25:19,638 INFO L384 CDTParser]: Found 1 translation units. [2024-11-18 14:25:19,640 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_2calls_8-2.c [2024-11-18 14:25:19,648 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/cda3d1b71/f8c562586a694282a748a3a529344fb1/FLAG05525a5c3 [2024-11-18 14:25:20,045 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/cda3d1b71/f8c562586a694282a748a3a529344fb1 [2024-11-18 14:25:20,047 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-18 14:25:20,048 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-18 14:25:20,051 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-18 14:25:20,051 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-18 14:25:20,055 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-18 14:25:20,056 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,056 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5209e3b3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20, skipping insertion in model container [2024-11-18 14:25:20,056 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,069 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-18 14:25:20,232 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/recursive-simple/fibo_2calls_8-2.c[947,960] [2024-11-18 14:25:20,237 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 14:25:20,247 INFO L200 MainTranslator]: Completed pre-run [2024-11-18 14:25:20,260 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/recursive-simple/fibo_2calls_8-2.c[947,960] [2024-11-18 14:25:20,261 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 14:25:20,274 INFO L204 MainTranslator]: Completed translation [2024-11-18 14:25:20,275 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20 WrapperNode [2024-11-18 14:25:20,275 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-18 14:25:20,276 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-18 14:25:20,276 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-18 14:25:20,276 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-18 14:25:20,282 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,287 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,300 INFO L138 Inliner]: procedures = 14, calls = 12, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2024-11-18 14:25:20,300 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-18 14:25:20,301 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-18 14:25:20,301 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-18 14:25:20,301 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-18 14:25:20,308 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,309 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,309 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,317 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-18 14:25:20,318 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,318 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,322 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,324 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,325 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,325 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,327 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-18 14:25:20,327 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-18 14:25:20,327 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-18 14:25:20,328 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-18 14:25:20,328 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20" (1/1) ... [2024-11-18 14:25:20,332 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 14:25:20,342 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:20,356 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-18 14:25:20,360 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-18 14:25:20,405 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-18 14:25:20,405 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-18 14:25:20,405 INFO L130 BoogieDeclarations]: Found specification of procedure fibo2 [2024-11-18 14:25:20,405 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo2 [2024-11-18 14:25:20,405 INFO L130 BoogieDeclarations]: Found specification of procedure fibo1 [2024-11-18 14:25:20,405 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo1 [2024-11-18 14:25:20,405 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-18 14:25:20,407 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-18 14:25:20,465 INFO L238 CfgBuilder]: Building ICFG [2024-11-18 14:25:20,467 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-18 14:25:20,590 INFO L? ?]: Removed 8 outVars from TransFormulas that were not future-live. [2024-11-18 14:25:20,591 INFO L287 CfgBuilder]: Performing block encoding [2024-11-18 14:25:20,600 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-18 14:25:20,600 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-18 14:25:20,601 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 02:25:20 BoogieIcfgContainer [2024-11-18 14:25:20,601 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-18 14:25:20,603 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-18 14:25:20,603 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-18 14:25:20,606 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-18 14:25:20,606 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.11 02:25:20" (1/3) ... [2024-11-18 14:25:20,606 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@72b4789b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 02:25:20, skipping insertion in model container [2024-11-18 14:25:20,606 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 02:25:20" (2/3) ... [2024-11-18 14:25:20,607 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@72b4789b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 02:25:20, skipping insertion in model container [2024-11-18 14:25:20,607 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 02:25:20" (3/3) ... [2024-11-18 14:25:20,611 INFO L112 eAbstractionObserver]: Analyzing ICFG fibo_2calls_8-2.c [2024-11-18 14:25:20,624 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-18 14:25:20,625 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-18 14:25:20,668 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-18 14:25:20,673 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;@4c0c5277, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-18 14:25:20,674 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-18 14:25:20,677 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-18 14:25:20,682 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-18 14:25:20,682 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:20,682 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:20,683 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:20,686 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:20,687 INFO L85 PathProgramCache]: Analyzing trace with hash 1123300790, now seen corresponding path program 1 times [2024-11-18 14:25:20,693 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:20,693 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1942379333] [2024-11-18 14:25:20,694 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:20,694 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:20,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:20,874 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-18 14:25:20,874 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:20,874 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1942379333] [2024-11-18 14:25:20,875 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1942379333] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 14:25:20,875 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 14:25:20,875 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 14:25:20,876 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1866499059] [2024-11-18 14:25:20,876 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 14:25:20,879 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 14:25:20,880 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:20,896 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 14:25:20,896 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 14:25:20,898 INFO L87 Difference]: Start difference. First operand has 29 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-18 14:25:20,942 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:20,943 INFO L93 Difference]: Finished difference Result 39 states and 48 transitions. [2024-11-18 14:25:20,944 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 14:25:20,945 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 10 [2024-11-18 14:25:20,945 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:20,950 INFO L225 Difference]: With dead ends: 39 [2024-11-18 14:25:20,951 INFO L226 Difference]: Without dead ends: 27 [2024-11-18 14:25:20,953 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 14:25:20,955 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 0 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:20,956 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 124 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 14:25:20,969 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2024-11-18 14:25:20,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2024-11-18 14:25:20,983 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 5 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2024-11-18 14:25:20,984 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 34 transitions. [2024-11-18 14:25:20,985 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 34 transitions. Word has length 10 [2024-11-18 14:25:20,985 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:20,985 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 34 transitions. [2024-11-18 14:25:20,985 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-18 14:25:20,985 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 34 transitions. [2024-11-18 14:25:20,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-18 14:25:20,986 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:20,987 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:20,987 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-18 14:25:20,987 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:20,987 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:20,987 INFO L85 PathProgramCache]: Analyzing trace with hash 1177745932, now seen corresponding path program 1 times [2024-11-18 14:25:20,988 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:20,988 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1622068689] [2024-11-18 14:25:20,988 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:20,988 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:20,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:21,069 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-18 14:25:21,071 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:21,071 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1622068689] [2024-11-18 14:25:21,071 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1622068689] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 14:25:21,071 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 14:25:21,071 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 14:25:21,071 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2057612195] [2024-11-18 14:25:21,072 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 14:25:21,072 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 14:25:21,073 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:21,073 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 14:25:21,075 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 14:25:21,075 INFO L87 Difference]: Start difference. First operand 27 states and 34 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), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-18 14:25:21,103 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:21,103 INFO L93 Difference]: Finished difference Result 33 states and 41 transitions. [2024-11-18 14:25:21,104 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 14:25:21,104 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), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2024-11-18 14:25:21,104 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:21,105 INFO L225 Difference]: With dead ends: 33 [2024-11-18 14:25:21,105 INFO L226 Difference]: Without dead ends: 29 [2024-11-18 14:25:21,105 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 14:25:21,106 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 0 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:21,107 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 125 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 14:25:21,109 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2024-11-18 14:25:21,115 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 27. [2024-11-18 14:25:21,116 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 5 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2024-11-18 14:25:21,117 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 34 transitions. [2024-11-18 14:25:21,117 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 34 transitions. Word has length 11 [2024-11-18 14:25:21,117 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:21,117 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 34 transitions. [2024-11-18 14:25:21,118 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), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-18 14:25:21,118 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 34 transitions. [2024-11-18 14:25:21,118 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-18 14:25:21,119 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:21,119 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:21,119 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-18 14:25:21,119 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:21,119 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:21,120 INFO L85 PathProgramCache]: Analyzing trace with hash 2110588723, now seen corresponding path program 1 times [2024-11-18 14:25:21,120 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:21,120 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2141555380] [2024-11-18 14:25:21,120 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:21,120 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:21,136 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:21,251 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-18 14:25:21,252 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:21,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2141555380] [2024-11-18 14:25:21,252 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2141555380] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:21,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [706335848] [2024-11-18 14:25:21,252 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:21,252 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:21,253 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:21,258 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-18 14:25:21,260 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-18 14:25:21,317 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:21,319 INFO L255 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-18 14:25:21,325 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:21,403 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-18 14:25:21,403 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:21,617 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-18 14:25:21,617 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [706335848] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:21,618 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:21,618 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 7, 7] total 12 [2024-11-18 14:25:21,618 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [894024378] [2024-11-18 14:25:21,618 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:21,619 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-18 14:25:21,619 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:21,620 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-18 14:25:21,620 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2024-11-18 14:25:21,620 INFO L87 Difference]: Start difference. First operand 27 states and 34 transitions. Second operand has 12 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 12 states have internal predecessors, (30), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-18 14:25:21,758 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:21,758 INFO L93 Difference]: Finished difference Result 55 states and 75 transitions. [2024-11-18 14:25:21,759 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-18 14:25:21,759 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 12 states have internal predecessors, (30), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) Word has length 23 [2024-11-18 14:25:21,759 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:21,760 INFO L225 Difference]: With dead ends: 55 [2024-11-18 14:25:21,760 INFO L226 Difference]: Without dead ends: 31 [2024-11-18 14:25:21,761 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 39 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2024-11-18 14:25:21,762 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 22 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 111 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:21,762 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 105 Invalid, 111 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:25:21,763 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-18 14:25:21,767 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 29. [2024-11-18 14:25:21,767 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 21 states have internal predecessors, (23), 5 states have call successors, (5), 2 states have call predecessors, (5), 4 states have return successors, (8), 5 states have call predecessors, (8), 5 states have call successors, (8) [2024-11-18 14:25:21,768 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 36 transitions. [2024-11-18 14:25:21,768 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 36 transitions. Word has length 23 [2024-11-18 14:25:21,769 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:21,769 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 36 transitions. [2024-11-18 14:25:21,769 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 12 states have internal predecessors, (30), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-18 14:25:21,769 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 36 transitions. [2024-11-18 14:25:21,770 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-18 14:25:21,770 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:21,770 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:21,787 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-18 14:25:21,974 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-18 14:25:21,975 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:21,975 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:21,975 INFO L85 PathProgramCache]: Analyzing trace with hash 1277869167, now seen corresponding path program 1 times [2024-11-18 14:25:21,975 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:21,976 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1910448914] [2024-11-18 14:25:21,976 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:21,976 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:21,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:22,071 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-18 14:25:22,071 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:22,072 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1910448914] [2024-11-18 14:25:22,072 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1910448914] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:22,072 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [876560004] [2024-11-18 14:25:22,072 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:22,072 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:22,072 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:22,076 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-18 14:25:22,079 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-18 14:25:22,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:22,119 INFO L255 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-18 14:25:22,120 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:22,174 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-18 14:25:22,174 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:22,350 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-18 14:25:22,351 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [876560004] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:22,351 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:22,351 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 10 [2024-11-18 14:25:22,354 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [547146332] [2024-11-18 14:25:22,355 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:22,355 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-18 14:25:22,355 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:22,356 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-18 14:25:22,356 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2024-11-18 14:25:22,356 INFO L87 Difference]: Start difference. First operand 29 states and 36 transitions. Second operand has 10 states, 8 states have (on average 3.125) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-18 14:25:22,477 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:22,477 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2024-11-18 14:25:22,477 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-18 14:25:22,478 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 3.125) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) Word has length 24 [2024-11-18 14:25:22,478 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:22,479 INFO L225 Difference]: With dead ends: 40 [2024-11-18 14:25:22,480 INFO L226 Difference]: Without dead ends: 36 [2024-11-18 14:25:22,480 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 43 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-11-18 14:25:22,481 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 13 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 142 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 147 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 142 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:22,481 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 135 Invalid, 147 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 142 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:25:22,482 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2024-11-18 14:25:22,489 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 34. [2024-11-18 14:25:22,489 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 6 states have call successors, (6), 2 states have call predecessors, (6), 5 states have return successors, (13), 7 states have call predecessors, (13), 6 states have call successors, (13) [2024-11-18 14:25:22,493 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 45 transitions. [2024-11-18 14:25:22,493 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 45 transitions. Word has length 24 [2024-11-18 14:25:22,495 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:22,495 INFO L471 AbstractCegarLoop]: Abstraction has 34 states and 45 transitions. [2024-11-18 14:25:22,495 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 3.125) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-18 14:25:22,495 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 45 transitions. [2024-11-18 14:25:22,496 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-18 14:25:22,496 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:22,496 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:22,512 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-18 14:25:22,697 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-18 14:25:22,697 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:22,698 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:22,698 INFO L85 PathProgramCache]: Analyzing trace with hash -2061621832, now seen corresponding path program 1 times [2024-11-18 14:25:22,698 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:22,698 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2125475693] [2024-11-18 14:25:22,698 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:22,698 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:22,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:22,787 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 5 proven. 5 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-18 14:25:22,787 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:22,787 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2125475693] [2024-11-18 14:25:22,787 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2125475693] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:22,787 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1494446495] [2024-11-18 14:25:22,788 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:22,788 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:22,788 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:22,790 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-18 14:25:22,792 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-18 14:25:22,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:22,845 INFO L255 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-18 14:25:22,850 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:22,949 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-18 14:25:22,949 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:23,190 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 2 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-18 14:25:23,190 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1494446495] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:23,191 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:23,191 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 8, 9] total 14 [2024-11-18 14:25:23,191 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [130337937] [2024-11-18 14:25:23,191 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:23,191 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-18 14:25:23,192 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:23,192 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-18 14:25:23,192 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2024-11-18 14:25:23,193 INFO L87 Difference]: Start difference. First operand 34 states and 45 transitions. Second operand has 14 states, 11 states have (on average 4.090909090909091) internal successors, (45), 14 states have internal predecessors, (45), 11 states have call successors, (13), 1 states have call predecessors, (13), 5 states have return successors, (13), 3 states have call predecessors, (13), 11 states have call successors, (13) [2024-11-18 14:25:23,314 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:23,315 INFO L93 Difference]: Finished difference Result 69 states and 100 transitions. [2024-11-18 14:25:23,315 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-18 14:25:23,315 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 11 states have (on average 4.090909090909091) internal successors, (45), 14 states have internal predecessors, (45), 11 states have call successors, (13), 1 states have call predecessors, (13), 5 states have return successors, (13), 3 states have call predecessors, (13), 11 states have call successors, (13) Word has length 36 [2024-11-18 14:25:23,316 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:23,316 INFO L225 Difference]: With dead ends: 69 [2024-11-18 14:25:23,317 INFO L226 Difference]: Without dead ends: 38 [2024-11-18 14:25:23,317 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 64 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=54, Invalid=218, Unknown=0, NotChecked=0, Total=272 [2024-11-18 14:25:23,318 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 18 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 147 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 168 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 147 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:23,318 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 146 Invalid, 168 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 147 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:25:23,319 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2024-11-18 14:25:23,322 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 36. [2024-11-18 14:25:23,323 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 23 states have (on average 1.173913043478261) internal successors, (27), 26 states have internal predecessors, (27), 6 states have call successors, (6), 2 states have call predecessors, (6), 6 states have return successors, (14), 7 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-18 14:25:23,324 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 47 transitions. [2024-11-18 14:25:23,324 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 47 transitions. Word has length 36 [2024-11-18 14:25:23,324 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:23,324 INFO L471 AbstractCegarLoop]: Abstraction has 36 states and 47 transitions. [2024-11-18 14:25:23,324 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 11 states have (on average 4.090909090909091) internal successors, (45), 14 states have internal predecessors, (45), 11 states have call successors, (13), 1 states have call predecessors, (13), 5 states have return successors, (13), 3 states have call predecessors, (13), 11 states have call successors, (13) [2024-11-18 14:25:23,324 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 47 transitions. [2024-11-18 14:25:23,325 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-11-18 14:25:23,325 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:23,325 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:23,340 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-18 14:25:23,529 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-18 14:25:23,530 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:23,530 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:23,531 INFO L85 PathProgramCache]: Analyzing trace with hash 1167294498, now seen corresponding path program 1 times [2024-11-18 14:25:23,531 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:23,531 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1681857789] [2024-11-18 14:25:23,531 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:23,531 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:23,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:23,620 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2024-11-18 14:25:23,620 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:23,620 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1681857789] [2024-11-18 14:25:23,620 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1681857789] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:23,620 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [778329847] [2024-11-18 14:25:23,621 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:23,621 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:23,621 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:23,622 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-18 14:25:23,624 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-18 14:25:23,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:23,663 INFO L255 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-18 14:25:23,664 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:23,732 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-18 14:25:23,733 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:24,003 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 11 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-18 14:25:24,003 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [778329847] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:24,003 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:24,003 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 18 [2024-11-18 14:25:24,004 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1655292697] [2024-11-18 14:25:24,004 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:24,004 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-18 14:25:24,004 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:24,005 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-18 14:25:24,005 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=257, Unknown=0, NotChecked=0, Total=306 [2024-11-18 14:25:24,005 INFO L87 Difference]: Start difference. First operand 36 states and 47 transitions. Second operand has 18 states, 16 states have (on average 3.125) internal successors, (50), 18 states have internal predecessors, (50), 11 states have call successors, (13), 1 states have call predecessors, (13), 7 states have return successors, (13), 6 states have call predecessors, (13), 11 states have call successors, (13) [2024-11-18 14:25:24,326 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:24,326 INFO L93 Difference]: Finished difference Result 101 states and 161 transitions. [2024-11-18 14:25:24,326 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-18 14:25:24,327 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 16 states have (on average 3.125) internal successors, (50), 18 states have internal predecessors, (50), 11 states have call successors, (13), 1 states have call predecessors, (13), 7 states have return successors, (13), 6 states have call predecessors, (13), 11 states have call successors, (13) Word has length 37 [2024-11-18 14:25:24,327 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:24,328 INFO L225 Difference]: With dead ends: 101 [2024-11-18 14:25:24,328 INFO L226 Difference]: Without dead ends: 68 [2024-11-18 14:25:24,329 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 69 SyntacticMatches, 3 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 107 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=124, Invalid=578, Unknown=0, NotChecked=0, Total=702 [2024-11-18 14:25:24,330 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 39 mSDsluCounter, 267 mSDsCounter, 0 mSdLazyCounter, 397 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 300 SdHoareTripleChecker+Invalid, 443 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 397 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:24,330 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 300 Invalid, 443 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 397 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 14:25:24,330 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2024-11-18 14:25:24,343 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 56. [2024-11-18 14:25:24,344 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 35 states have (on average 1.1714285714285715) internal successors, (41), 39 states have internal predecessors, (41), 11 states have call successors, (11), 3 states have call predecessors, (11), 9 states have return successors, (34), 13 states have call predecessors, (34), 11 states have call successors, (34) [2024-11-18 14:25:24,345 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 86 transitions. [2024-11-18 14:25:24,345 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 86 transitions. Word has length 37 [2024-11-18 14:25:24,345 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:24,348 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 86 transitions. [2024-11-18 14:25:24,348 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 16 states have (on average 3.125) internal successors, (50), 18 states have internal predecessors, (50), 11 states have call successors, (13), 1 states have call predecessors, (13), 7 states have return successors, (13), 6 states have call predecessors, (13), 11 states have call successors, (13) [2024-11-18 14:25:24,348 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 86 transitions. [2024-11-18 14:25:24,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-18 14:25:24,350 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:24,350 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:24,363 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-18 14:25:24,554 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-18 14:25:24,555 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:24,556 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:24,556 INFO L85 PathProgramCache]: Analyzing trace with hash 384535367, now seen corresponding path program 1 times [2024-11-18 14:25:24,556 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:24,556 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1302377910] [2024-11-18 14:25:24,556 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:24,556 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:24,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:24,667 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 12 proven. 12 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2024-11-18 14:25:24,667 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:24,667 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1302377910] [2024-11-18 14:25:24,667 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1302377910] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:24,667 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [789043758] [2024-11-18 14:25:24,667 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:24,667 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:24,667 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:24,670 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-18 14:25:24,672 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-18 14:25:24,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:24,718 INFO L255 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-18 14:25:24,720 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:24,781 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 4 proven. 23 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2024-11-18 14:25:24,781 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:25,161 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 4 proven. 28 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-18 14:25:25,161 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [789043758] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:25,161 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:25,161 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9, 11] total 17 [2024-11-18 14:25:25,161 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [923967767] [2024-11-18 14:25:25,162 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:25,162 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-18 14:25:25,162 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:25,163 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-18 14:25:25,163 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=217, Unknown=0, NotChecked=0, Total=272 [2024-11-18 14:25:25,163 INFO L87 Difference]: Start difference. First operand 56 states and 86 transitions. Second operand has 17 states, 15 states have (on average 3.6666666666666665) internal successors, (55), 17 states have internal predecessors, (55), 12 states have call successors, (14), 1 states have call predecessors, (14), 8 states have return successors, (18), 8 states have call predecessors, (18), 12 states have call successors, (18) [2024-11-18 14:25:25,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:25,317 INFO L93 Difference]: Finished difference Result 102 states and 193 transitions. [2024-11-18 14:25:25,317 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-18 14:25:25,318 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 3.6666666666666665) internal successors, (55), 17 states have internal predecessors, (55), 12 states have call successors, (14), 1 states have call predecessors, (14), 8 states have return successors, (18), 8 states have call predecessors, (18), 12 states have call successors, (18) Word has length 51 [2024-11-18 14:25:25,318 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:25,319 INFO L225 Difference]: With dead ends: 102 [2024-11-18 14:25:25,319 INFO L226 Difference]: Without dead ends: 98 [2024-11-18 14:25:25,320 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 92 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 95 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=93, Invalid=369, Unknown=0, NotChecked=0, Total=462 [2024-11-18 14:25:25,320 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 35 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 170 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 206 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 170 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:25,321 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 161 Invalid, 206 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 170 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:25:25,321 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2024-11-18 14:25:25,342 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 64. [2024-11-18 14:25:25,344 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 40 states have (on average 1.15) internal successors, (46), 44 states have internal predecessors, (46), 12 states have call successors, (12), 3 states have call predecessors, (12), 11 states have return successors, (48), 16 states have call predecessors, (48), 12 states have call successors, (48) [2024-11-18 14:25:25,345 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 106 transitions. [2024-11-18 14:25:25,346 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 106 transitions. Word has length 51 [2024-11-18 14:25:25,346 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:25,346 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 106 transitions. [2024-11-18 14:25:25,346 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 3.6666666666666665) internal successors, (55), 17 states have internal predecessors, (55), 12 states have call successors, (14), 1 states have call predecessors, (14), 8 states have return successors, (18), 8 states have call predecessors, (18), 12 states have call successors, (18) [2024-11-18 14:25:25,346 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 106 transitions. [2024-11-18 14:25:25,353 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2024-11-18 14:25:25,353 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:25,353 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 7, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:25,370 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-18 14:25:25,557 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-18 14:25:25,557 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:25,560 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:25,560 INFO L85 PathProgramCache]: Analyzing trace with hash 1770426885, now seen corresponding path program 1 times [2024-11-18 14:25:25,560 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:25,560 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [657237582] [2024-11-18 14:25:25,560 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:25,560 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:25,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:25,720 INFO L134 CoverageAnalysis]: Checked inductivity of 276 backedges. 44 proven. 81 refuted. 0 times theorem prover too weak. 151 trivial. 0 not checked. [2024-11-18 14:25:25,720 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:25,721 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [657237582] [2024-11-18 14:25:25,721 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [657237582] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:25,721 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1681257440] [2024-11-18 14:25:25,721 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:25,721 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:25,721 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:25,723 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-18 14:25:25,724 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-18 14:25:25,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:25,782 INFO L255 TraceCheckSpWp]: Trace formula consists of 257 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-18 14:25:25,784 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:25,876 INFO L134 CoverageAnalysis]: Checked inductivity of 276 backedges. 17 proven. 119 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-11-18 14:25:25,876 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:26,574 INFO L134 CoverageAnalysis]: Checked inductivity of 276 backedges. 17 proven. 129 refuted. 0 times theorem prover too weak. 130 trivial. 0 not checked. [2024-11-18 14:25:26,575 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1681257440] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:26,575 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:26,575 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10, 13] total 23 [2024-11-18 14:25:26,575 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [280721981] [2024-11-18 14:25:26,575 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:26,576 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-18 14:25:26,576 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:26,576 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-18 14:25:26,577 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=439, Unknown=0, NotChecked=0, Total=506 [2024-11-18 14:25:26,577 INFO L87 Difference]: Start difference. First operand 64 states and 106 transitions. Second operand has 23 states, 21 states have (on average 3.5714285714285716) internal successors, (75), 23 states have internal predecessors, (75), 18 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (27), 10 states have call predecessors, (27), 18 states have call successors, (27) [2024-11-18 14:25:27,094 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:27,094 INFO L93 Difference]: Finished difference Result 177 states and 369 transitions. [2024-11-18 14:25:27,094 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-18 14:25:27,095 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 3.5714285714285716) internal successors, (75), 23 states have internal predecessors, (75), 18 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (27), 10 states have call predecessors, (27), 18 states have call successors, (27) Word has length 107 [2024-11-18 14:25:27,095 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:27,097 INFO L225 Difference]: With dead ends: 177 [2024-11-18 14:25:27,097 INFO L226 Difference]: Without dead ends: 104 [2024-11-18 14:25:27,103 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 240 GetRequests, 197 SyntacticMatches, 5 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 255 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=263, Invalid=1297, Unknown=0, NotChecked=0, Total=1560 [2024-11-18 14:25:27,103 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 78 mSDsluCounter, 318 mSDsCounter, 0 mSdLazyCounter, 534 mSolverCounterSat, 101 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 352 SdHoareTripleChecker+Invalid, 635 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 101 IncrementalHoareTripleChecker+Valid, 534 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:27,104 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 352 Invalid, 635 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [101 Valid, 534 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-18 14:25:27,105 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2024-11-18 14:25:27,120 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 93. [2024-11-18 14:25:27,121 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 62 states have (on average 1.1774193548387097) internal successors, (73), 64 states have internal predecessors, (73), 16 states have call successors, (16), 8 states have call predecessors, (16), 14 states have return successors, (43), 20 states have call predecessors, (43), 16 states have call successors, (43) [2024-11-18 14:25:27,122 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 132 transitions. [2024-11-18 14:25:27,122 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 132 transitions. Word has length 107 [2024-11-18 14:25:27,122 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:27,122 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 132 transitions. [2024-11-18 14:25:27,122 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 3.5714285714285716) internal successors, (75), 23 states have internal predecessors, (75), 18 states have call successors, (23), 1 states have call predecessors, (23), 9 states have return successors, (27), 10 states have call predecessors, (27), 18 states have call successors, (27) [2024-11-18 14:25:27,123 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 132 transitions. [2024-11-18 14:25:27,124 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 147 [2024-11-18 14:25:27,124 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:27,124 INFO L215 NwaCegarLoop]: trace histogram [12, 12, 9, 9, 9, 7, 6, 6, 6, 6, 6, 6, 6, 5, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:27,137 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-18 14:25:27,325 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-18 14:25:27,325 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:27,326 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:27,326 INFO L85 PathProgramCache]: Analyzing trace with hash -1566869308, now seen corresponding path program 1 times [2024-11-18 14:25:27,326 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:27,326 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [759677349] [2024-11-18 14:25:27,326 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:27,326 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:27,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:27,561 INFO L134 CoverageAnalysis]: Checked inductivity of 549 backedges. 42 proven. 158 refuted. 0 times theorem prover too weak. 349 trivial. 0 not checked. [2024-11-18 14:25:27,561 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:27,561 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [759677349] [2024-11-18 14:25:27,561 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [759677349] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:27,562 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1458778625] [2024-11-18 14:25:27,562 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 14:25:27,562 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:27,562 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:27,564 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-18 14:25:27,569 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-18 14:25:27,640 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:27,642 INFO L255 TraceCheckSpWp]: Trace formula consists of 344 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-18 14:25:27,644 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:27,745 INFO L134 CoverageAnalysis]: Checked inductivity of 549 backedges. 29 proven. 212 refuted. 0 times theorem prover too weak. 308 trivial. 0 not checked. [2024-11-18 14:25:27,745 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:28,651 INFO L134 CoverageAnalysis]: Checked inductivity of 549 backedges. 29 proven. 228 refuted. 0 times theorem prover too weak. 292 trivial. 0 not checked. [2024-11-18 14:25:28,652 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1458778625] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:28,652 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:28,652 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11, 15] total 23 [2024-11-18 14:25:28,652 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1032021362] [2024-11-18 14:25:28,652 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:28,653 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-18 14:25:28,653 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:28,653 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-18 14:25:28,653 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=410, Unknown=0, NotChecked=0, Total=506 [2024-11-18 14:25:28,654 INFO L87 Difference]: Start difference. First operand 93 states and 132 transitions. Second operand has 23 states, 21 states have (on average 3.6666666666666665) internal successors, (77), 23 states have internal predecessors, (77), 18 states have call successors, (22), 1 states have call predecessors, (22), 12 states have return successors, (30), 12 states have call predecessors, (30), 18 states have call successors, (30) [2024-11-18 14:25:28,874 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:28,874 INFO L93 Difference]: Finished difference Result 132 states and 227 transitions. [2024-11-18 14:25:28,874 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-18 14:25:28,874 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 3.6666666666666665) internal successors, (77), 23 states have internal predecessors, (77), 18 states have call successors, (22), 1 states have call predecessors, (22), 12 states have return successors, (30), 12 states have call predecessors, (30), 18 states have call successors, (30) Word has length 146 [2024-11-18 14:25:28,875 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:28,876 INFO L225 Difference]: With dead ends: 132 [2024-11-18 14:25:28,876 INFO L226 Difference]: Without dead ends: 128 [2024-11-18 14:25:28,877 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 312 GetRequests, 276 SyntacticMatches, 6 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 290 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=191, Invalid=801, Unknown=0, NotChecked=0, Total=992 [2024-11-18 14:25:28,877 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 47 mSDsluCounter, 189 mSDsCounter, 0 mSdLazyCounter, 216 mSolverCounterSat, 51 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 209 SdHoareTripleChecker+Invalid, 267 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 216 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:28,878 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [58 Valid, 209 Invalid, 267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 216 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:25:28,878 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2024-11-18 14:25:28,889 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 118. [2024-11-18 14:25:28,889 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 77 states have (on average 1.1428571428571428) internal successors, (88), 79 states have internal predecessors, (88), 21 states have call successors, (21), 8 states have call predecessors, (21), 19 states have return successors, (85), 30 states have call predecessors, (85), 21 states have call successors, (85) [2024-11-18 14:25:28,890 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 194 transitions. [2024-11-18 14:25:28,891 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 194 transitions. Word has length 146 [2024-11-18 14:25:28,895 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:28,895 INFO L471 AbstractCegarLoop]: Abstraction has 118 states and 194 transitions. [2024-11-18 14:25:28,895 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 3.6666666666666665) internal successors, (77), 23 states have internal predecessors, (77), 18 states have call successors, (22), 1 states have call predecessors, (22), 12 states have return successors, (30), 12 states have call predecessors, (30), 18 states have call successors, (30) [2024-11-18 14:25:28,896 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 194 transitions. [2024-11-18 14:25:28,898 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 285 [2024-11-18 14:25:28,898 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:28,898 INFO L215 NwaCegarLoop]: trace histogram [21, 21, 20, 20, 18, 16, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 8, 6, 4, 3, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:28,912 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-18 14:25:29,099 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:29,099 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:29,099 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:29,099 INFO L85 PathProgramCache]: Analyzing trace with hash -1279109938, now seen corresponding path program 2 times [2024-11-18 14:25:29,100 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:29,100 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [161198749] [2024-11-18 14:25:29,100 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 14:25:29,100 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:29,166 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 14:25:29,166 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:29,491 INFO L134 CoverageAnalysis]: Checked inductivity of 2233 backedges. 158 proven. 490 refuted. 0 times theorem prover too weak. 1585 trivial. 0 not checked. [2024-11-18 14:25:29,491 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:29,491 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [161198749] [2024-11-18 14:25:29,492 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [161198749] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:29,492 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [553927399] [2024-11-18 14:25:29,492 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 14:25:29,492 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:29,492 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:29,494 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:25:29,495 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-18 14:25:29,610 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 14:25:29,611 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:29,613 INFO L255 TraceCheckSpWp]: Trace formula consists of 650 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-18 14:25:29,618 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:29,753 INFO L134 CoverageAnalysis]: Checked inductivity of 2233 backedges. 87 proven. 569 refuted. 0 times theorem prover too weak. 1577 trivial. 0 not checked. [2024-11-18 14:25:29,753 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:31,294 INFO L134 CoverageAnalysis]: Checked inductivity of 2233 backedges. 87 proven. 593 refuted. 0 times theorem prover too weak. 1553 trivial. 0 not checked. [2024-11-18 14:25:31,294 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [553927399] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:31,294 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:31,294 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 12, 17] total 28 [2024-11-18 14:25:31,295 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [124682848] [2024-11-18 14:25:31,295 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:31,296 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-11-18 14:25:31,296 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:31,296 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-18 14:25:31,297 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=662, Unknown=0, NotChecked=0, Total=756 [2024-11-18 14:25:31,297 INFO L87 Difference]: Start difference. First operand 118 states and 194 transitions. Second operand has 28 states, 27 states have (on average 3.4814814814814814) internal successors, (94), 28 states have internal predecessors, (94), 23 states have call successors, (29), 1 states have call predecessors, (29), 12 states have return successors, (36), 13 states have call predecessors, (36), 23 states have call successors, (36) [2024-11-18 14:25:31,957 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:31,957 INFO L93 Difference]: Finished difference Result 323 states and 666 transitions. [2024-11-18 14:25:31,957 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2024-11-18 14:25:31,957 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 27 states have (on average 3.4814814814814814) internal successors, (94), 28 states have internal predecessors, (94), 23 states have call successors, (29), 1 states have call predecessors, (29), 12 states have return successors, (36), 13 states have call predecessors, (36), 23 states have call successors, (36) Word has length 284 [2024-11-18 14:25:31,958 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:31,961 INFO L225 Difference]: With dead ends: 323 [2024-11-18 14:25:31,962 INFO L226 Difference]: Without dead ends: 214 [2024-11-18 14:25:31,964 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 606 GetRequests, 547 SyntacticMatches, 8 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 573 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=446, Invalid=2310, Unknown=0, NotChecked=0, Total=2756 [2024-11-18 14:25:31,964 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 110 mSDsluCounter, 513 mSDsCounter, 0 mSdLazyCounter, 868 mSolverCounterSat, 122 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 111 SdHoareTripleChecker+Valid, 558 SdHoareTripleChecker+Invalid, 990 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 122 IncrementalHoareTripleChecker+Valid, 868 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:31,965 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [111 Valid, 558 Invalid, 990 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [122 Valid, 868 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-18 14:25:31,966 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 214 states. [2024-11-18 14:25:31,984 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 214 to 184. [2024-11-18 14:25:31,985 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 184 states, 123 states have (on average 1.1869918699186992) internal successors, (146), 123 states have internal predecessors, (146), 35 states have call successors, (35), 17 states have call predecessors, (35), 25 states have return successors, (120), 43 states have call predecessors, (120), 35 states have call successors, (120) [2024-11-18 14:25:31,989 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 184 states to 184 states and 301 transitions. [2024-11-18 14:25:31,991 INFO L78 Accepts]: Start accepts. Automaton has 184 states and 301 transitions. Word has length 284 [2024-11-18 14:25:31,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:31,992 INFO L471 AbstractCegarLoop]: Abstraction has 184 states and 301 transitions. [2024-11-18 14:25:31,992 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 27 states have (on average 3.4814814814814814) internal successors, (94), 28 states have internal predecessors, (94), 23 states have call successors, (29), 1 states have call predecessors, (29), 12 states have return successors, (36), 13 states have call predecessors, (36), 23 states have call successors, (36) [2024-11-18 14:25:31,992 INFO L276 IsEmpty]: Start isEmpty. Operand 184 states and 301 transitions. [2024-11-18 14:25:31,997 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 351 [2024-11-18 14:25:31,997 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:31,997 INFO L215 NwaCegarLoop]: trace histogram [28, 28, 23, 23, 21, 19, 14, 14, 14, 14, 14, 14, 14, 11, 11, 11, 11, 11, 11, 11, 10, 7, 5, 4, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:32,012 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-18 14:25:32,201 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-18 14:25:32,202 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:32,202 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:32,202 INFO L85 PathProgramCache]: Analyzing trace with hash 1208797511, now seen corresponding path program 3 times [2024-11-18 14:25:32,203 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:32,203 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [516092998] [2024-11-18 14:25:32,203 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 14:25:32,203 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:32,236 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2024-11-18 14:25:32,236 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:32,529 INFO L134 CoverageAnalysis]: Checked inductivity of 3489 backedges. 668 proven. 191 refuted. 0 times theorem prover too weak. 2630 trivial. 0 not checked. [2024-11-18 14:25:32,529 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:32,529 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [516092998] [2024-11-18 14:25:32,529 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [516092998] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:32,529 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1335563277] [2024-11-18 14:25:32,529 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 14:25:32,529 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:32,529 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:32,531 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:25:32,532 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-18 14:25:32,634 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2024-11-18 14:25:32,635 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:32,636 INFO L255 TraceCheckSpWp]: Trace formula consists of 358 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-18 14:25:32,640 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:32,733 INFO L134 CoverageAnalysis]: Checked inductivity of 3489 backedges. 1698 proven. 37 refuted. 0 times theorem prover too weak. 1754 trivial. 0 not checked. [2024-11-18 14:25:32,733 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:33,927 INFO L134 CoverageAnalysis]: Checked inductivity of 3489 backedges. 668 proven. 191 refuted. 0 times theorem prover too weak. 2630 trivial. 0 not checked. [2024-11-18 14:25:33,927 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1335563277] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:33,927 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:33,927 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13, 14] total 25 [2024-11-18 14:25:33,927 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [995835306] [2024-11-18 14:25:33,927 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:33,928 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-18 14:25:33,928 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:33,928 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-18 14:25:33,929 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=511, Unknown=0, NotChecked=0, Total=600 [2024-11-18 14:25:33,929 INFO L87 Difference]: Start difference. First operand 184 states and 301 transitions. Second operand has 25 states, 23 states have (on average 3.9130434782608696) internal successors, (90), 25 states have internal predecessors, (90), 16 states have call successors, (28), 2 states have call predecessors, (28), 8 states have return successors, (32), 10 states have call predecessors, (32), 16 states have call successors, (32) [2024-11-18 14:25:34,217 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:34,218 INFO L93 Difference]: Finished difference Result 395 states and 698 transitions. [2024-11-18 14:25:34,218 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-18 14:25:34,218 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 23 states have (on average 3.9130434782608696) internal successors, (90), 25 states have internal predecessors, (90), 16 states have call successors, (28), 2 states have call predecessors, (28), 8 states have return successors, (32), 10 states have call predecessors, (32), 16 states have call successors, (32) Word has length 350 [2024-11-18 14:25:34,219 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:34,221 INFO L225 Difference]: With dead ends: 395 [2024-11-18 14:25:34,222 INFO L226 Difference]: Without dead ends: 218 [2024-11-18 14:25:34,224 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 725 GetRequests, 685 SyntacticMatches, 7 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 279 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=205, Invalid=985, Unknown=0, NotChecked=0, Total=1190 [2024-11-18 14:25:34,225 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 40 mSDsluCounter, 338 mSDsCounter, 0 mSdLazyCounter, 381 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 372 SdHoareTripleChecker+Invalid, 417 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 381 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:34,225 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 372 Invalid, 417 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 381 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 14:25:34,226 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 218 states. [2024-11-18 14:25:34,265 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 218 to 209. [2024-11-18 14:25:34,266 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 209 states, 143 states have (on average 1.1608391608391608) internal successors, (166), 139 states have internal predecessors, (166), 37 states have call successors, (37), 21 states have call predecessors, (37), 28 states have return successors, (140), 48 states have call predecessors, (140), 37 states have call successors, (140) [2024-11-18 14:25:34,269 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 209 states to 209 states and 343 transitions. [2024-11-18 14:25:34,270 INFO L78 Accepts]: Start accepts. Automaton has 209 states and 343 transitions. Word has length 350 [2024-11-18 14:25:34,270 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:34,270 INFO L471 AbstractCegarLoop]: Abstraction has 209 states and 343 transitions. [2024-11-18 14:25:34,271 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 23 states have (on average 3.9130434782608696) internal successors, (90), 25 states have internal predecessors, (90), 16 states have call successors, (28), 2 states have call predecessors, (28), 8 states have return successors, (32), 10 states have call predecessors, (32), 16 states have call successors, (32) [2024-11-18 14:25:34,271 INFO L276 IsEmpty]: Start isEmpty. Operand 209 states and 343 transitions. [2024-11-18 14:25:34,275 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 437 [2024-11-18 14:25:34,276 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:34,276 INFO L215 NwaCegarLoop]: trace histogram [36, 36, 31, 27, 27, 23, 18, 18, 18, 18, 18, 18, 18, 18, 13, 13, 13, 13, 13, 13, 13, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:34,292 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-18 14:25:34,476 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:34,477 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:34,477 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:34,478 INFO L85 PathProgramCache]: Analyzing trace with hash -366653803, now seen corresponding path program 4 times [2024-11-18 14:25:34,478 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:34,478 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [378018171] [2024-11-18 14:25:34,478 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 14:25:34,478 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:34,518 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 14:25:34,518 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:34,827 INFO L134 CoverageAnalysis]: Checked inductivity of 5566 backedges. 177 proven. 876 refuted. 0 times theorem prover too weak. 4513 trivial. 0 not checked. [2024-11-18 14:25:34,828 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:34,828 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [378018171] [2024-11-18 14:25:34,828 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [378018171] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:34,828 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2140858078] [2024-11-18 14:25:34,828 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 14:25:34,828 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:34,828 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:34,830 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:25:34,835 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-18 14:25:34,982 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 14:25:34,983 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:34,988 INFO L255 TraceCheckSpWp]: Trace formula consists of 776 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-18 14:25:34,993 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:35,061 INFO L134 CoverageAnalysis]: Checked inductivity of 5566 backedges. 177 proven. 876 refuted. 0 times theorem prover too weak. 4513 trivial. 0 not checked. [2024-11-18 14:25:35,062 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:36,963 INFO L134 CoverageAnalysis]: Checked inductivity of 5566 backedges. 177 proven. 897 refuted. 0 times theorem prover too weak. 4492 trivial. 0 not checked. [2024-11-18 14:25:36,963 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2140858078] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:36,963 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:36,964 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 17] total 19 [2024-11-18 14:25:36,964 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1510011082] [2024-11-18 14:25:36,964 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:36,965 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-18 14:25:36,965 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:36,966 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-18 14:25:36,966 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=275, Unknown=0, NotChecked=0, Total=342 [2024-11-18 14:25:36,966 INFO L87 Difference]: Start difference. First operand 209 states and 343 transitions. Second operand has 19 states, 18 states have (on average 3.7777777777777777) internal successors, (68), 19 states have internal predecessors, (68), 15 states have call successors, (20), 1 states have call predecessors, (20), 8 states have return successors, (24), 10 states have call predecessors, (24), 15 states have call successors, (24) [2024-11-18 14:25:37,152 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:37,153 INFO L93 Difference]: Finished difference Result 284 states and 535 transitions. [2024-11-18 14:25:37,153 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-18 14:25:37,153 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 3.7777777777777777) internal successors, (68), 19 states have internal predecessors, (68), 15 states have call successors, (20), 1 states have call predecessors, (20), 8 states have return successors, (24), 10 states have call predecessors, (24), 15 states have call successors, (24) Word has length 436 [2024-11-18 14:25:37,154 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:37,158 INFO L225 Difference]: With dead ends: 284 [2024-11-18 14:25:37,158 INFO L226 Difference]: Without dead ends: 280 [2024-11-18 14:25:37,159 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 893 GetRequests, 862 SyntacticMatches, 8 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=124, Invalid=476, Unknown=0, NotChecked=0, Total=600 [2024-11-18 14:25:37,159 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 52 mSDsluCounter, 140 mSDsCounter, 0 mSdLazyCounter, 163 mSolverCounterSat, 62 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 225 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 163 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:37,159 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 160 Invalid, 225 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 163 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:25:37,160 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 280 states. [2024-11-18 14:25:37,180 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 280 to 219. [2024-11-18 14:25:37,181 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 219 states, 149 states have (on average 1.1543624161073827) internal successors, (172), 145 states have internal predecessors, (172), 39 states have call successors, (39), 21 states have call predecessors, (39), 30 states have return successors, (162), 52 states have call predecessors, (162), 39 states have call successors, (162) [2024-11-18 14:25:37,183 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 219 states to 219 states and 373 transitions. [2024-11-18 14:25:37,183 INFO L78 Accepts]: Start accepts. Automaton has 219 states and 373 transitions. Word has length 436 [2024-11-18 14:25:37,184 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:37,184 INFO L471 AbstractCegarLoop]: Abstraction has 219 states and 373 transitions. [2024-11-18 14:25:37,185 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 3.7777777777777777) internal successors, (68), 19 states have internal predecessors, (68), 15 states have call successors, (20), 1 states have call predecessors, (20), 8 states have return successors, (24), 10 states have call predecessors, (24), 15 states have call successors, (24) [2024-11-18 14:25:37,185 INFO L276 IsEmpty]: Start isEmpty. Operand 219 states and 373 transitions. [2024-11-18 14:25:37,188 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 506 [2024-11-18 14:25:37,188 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:37,188 INFO L215 NwaCegarLoop]: trace histogram [42, 42, 38, 31, 31, 25, 23, 21, 21, 21, 21, 21, 21, 21, 15, 15, 15, 15, 15, 15, 15, 6, 4, 4, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:37,208 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-18 14:25:37,389 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-18 14:25:37,389 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:37,389 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:37,389 INFO L85 PathProgramCache]: Analyzing trace with hash -1094896294, now seen corresponding path program 5 times [2024-11-18 14:25:37,389 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:37,389 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1980944120] [2024-11-18 14:25:37,389 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-18 14:25:37,390 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:37,413 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2024-11-18 14:25:37,413 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:37,465 INFO L134 CoverageAnalysis]: Checked inductivity of 7567 backedges. 244 proven. 612 refuted. 0 times theorem prover too weak. 6711 trivial. 0 not checked. [2024-11-18 14:25:37,466 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:37,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1980944120] [2024-11-18 14:25:37,466 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1980944120] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:37,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [257366240] [2024-11-18 14:25:37,466 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-18 14:25:37,466 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:37,467 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:37,468 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:25:37,470 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-18 14:25:37,598 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2024-11-18 14:25:37,599 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:37,600 INFO L255 TraceCheckSpWp]: Trace formula consists of 171 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-18 14:25:37,607 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:37,632 INFO L134 CoverageAnalysis]: Checked inductivity of 7567 backedges. 2145 proven. 4 refuted. 0 times theorem prover too weak. 5418 trivial. 0 not checked. [2024-11-18 14:25:37,633 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:38,694 INFO L134 CoverageAnalysis]: Checked inductivity of 7567 backedges. 244 proven. 612 refuted. 0 times theorem prover too weak. 6711 trivial. 0 not checked. [2024-11-18 14:25:38,695 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [257366240] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:38,695 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:38,695 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 9 [2024-11-18 14:25:38,695 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1742759556] [2024-11-18 14:25:38,695 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:38,697 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-18 14:25:38,698 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:38,698 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-18 14:25:38,698 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-18 14:25:38,698 INFO L87 Difference]: Start difference. First operand 219 states and 373 transitions. Second operand has 9 states, 9 states have (on average 5.666666666666667) internal successors, (51), 9 states have internal predecessors, (51), 3 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2024-11-18 14:25:38,761 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:38,762 INFO L93 Difference]: Finished difference Result 423 states and 829 transitions. [2024-11-18 14:25:38,762 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-18 14:25:38,762 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 5.666666666666667) internal successors, (51), 9 states have internal predecessors, (51), 3 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) Word has length 505 [2024-11-18 14:25:38,763 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:38,765 INFO L225 Difference]: With dead ends: 423 [2024-11-18 14:25:38,765 INFO L226 Difference]: Without dead ends: 180 [2024-11-18 14:25:38,766 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 1020 GetRequests, 1005 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=123, Unknown=0, NotChecked=0, Total=182 [2024-11-18 14:25:38,768 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 20 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 70 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 82 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 70 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:38,768 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 116 Invalid, 82 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 70 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 14:25:38,769 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 180 states. [2024-11-18 14:25:38,783 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 180 to 180. [2024-11-18 14:25:38,783 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 180 states, 123 states have (on average 1.1626016260162602) internal successors, (143), 120 states have internal predecessors, (143), 31 states have call successors, (31), 18 states have call predecessors, (31), 25 states have return successors, (129), 41 states have call predecessors, (129), 31 states have call successors, (129) [2024-11-18 14:25:38,784 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 180 states to 180 states and 303 transitions. [2024-11-18 14:25:38,785 INFO L78 Accepts]: Start accepts. Automaton has 180 states and 303 transitions. Word has length 505 [2024-11-18 14:25:38,785 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:38,785 INFO L471 AbstractCegarLoop]: Abstraction has 180 states and 303 transitions. [2024-11-18 14:25:38,785 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 5.666666666666667) internal successors, (51), 9 states have internal predecessors, (51), 3 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2024-11-18 14:25:38,785 INFO L276 IsEmpty]: Start isEmpty. Operand 180 states and 303 transitions. [2024-11-18 14:25:38,787 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 394 [2024-11-18 14:25:38,787 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:38,787 INFO L215 NwaCegarLoop]: trace histogram [32, 32, 25, 25, 24, 23, 16, 16, 16, 16, 16, 16, 16, 12, 12, 12, 12, 12, 12, 12, 12, 8, 7, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:38,803 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-18 14:25:38,987 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-18 14:25:38,988 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:38,988 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:38,988 INFO L85 PathProgramCache]: Analyzing trace with hash -1643088490, now seen corresponding path program 6 times [2024-11-18 14:25:38,988 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:38,988 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1208718858] [2024-11-18 14:25:38,989 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-18 14:25:38,989 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:39,008 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2024-11-18 14:25:39,008 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:39,098 INFO L134 CoverageAnalysis]: Checked inductivity of 4457 backedges. 629 proven. 7 refuted. 0 times theorem prover too weak. 3821 trivial. 0 not checked. [2024-11-18 14:25:39,099 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:39,099 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1208718858] [2024-11-18 14:25:39,099 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1208718858] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:39,099 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [617863856] [2024-11-18 14:25:39,100 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-18 14:25:39,100 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:39,100 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:39,101 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:25:39,102 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-18 14:25:39,227 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2024-11-18 14:25:39,227 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:39,229 INFO L255 TraceCheckSpWp]: Trace formula consists of 195 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-18 14:25:39,232 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:39,272 INFO L134 CoverageAnalysis]: Checked inductivity of 4457 backedges. 627 proven. 9 refuted. 0 times theorem prover too weak. 3821 trivial. 0 not checked. [2024-11-18 14:25:39,272 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:40,091 INFO L134 CoverageAnalysis]: Checked inductivity of 4457 backedges. 627 proven. 9 refuted. 0 times theorem prover too weak. 3821 trivial. 0 not checked. [2024-11-18 14:25:40,092 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [617863856] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:40,092 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:40,092 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 9] total 15 [2024-11-18 14:25:40,092 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1301622164] [2024-11-18 14:25:40,092 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:40,093 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-18 14:25:40,093 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:40,093 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-18 14:25:40,094 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2024-11-18 14:25:40,094 INFO L87 Difference]: Start difference. First operand 180 states and 303 transitions. Second operand has 15 states, 15 states have (on average 3.8666666666666667) internal successors, (58), 15 states have internal predecessors, (58), 6 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (17), 8 states have call predecessors, (17), 6 states have call successors, (17) [2024-11-18 14:25:40,200 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:40,200 INFO L93 Difference]: Finished difference Result 354 states and 657 transitions. [2024-11-18 14:25:40,201 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-18 14:25:40,201 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 3.8666666666666667) internal successors, (58), 15 states have internal predecessors, (58), 6 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (17), 8 states have call predecessors, (17), 6 states have call successors, (17) Word has length 393 [2024-11-18 14:25:40,202 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:40,204 INFO L225 Difference]: With dead ends: 354 [2024-11-18 14:25:40,204 INFO L226 Difference]: Without dead ends: 177 [2024-11-18 14:25:40,206 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 796 GetRequests, 777 SyntacticMatches, 4 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 53 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=213, Unknown=0, NotChecked=0, Total=272 [2024-11-18 14:25:40,206 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 18 mSDsluCounter, 147 mSDsCounter, 0 mSdLazyCounter, 177 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 177 SdHoareTripleChecker+Invalid, 190 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 177 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:40,207 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 177 Invalid, 190 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 177 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:25:40,207 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2024-11-18 14:25:40,216 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 167. [2024-11-18 14:25:40,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 167 states, 115 states have (on average 1.173913043478261) internal successors, (135), 112 states have internal predecessors, (135), 29 states have call successors, (29), 18 states have call predecessors, (29), 22 states have return successors, (105), 36 states have call predecessors, (105), 29 states have call successors, (105) [2024-11-18 14:25:40,217 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 167 states to 167 states and 269 transitions. [2024-11-18 14:25:40,218 INFO L78 Accepts]: Start accepts. Automaton has 167 states and 269 transitions. Word has length 393 [2024-11-18 14:25:40,218 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:40,218 INFO L471 AbstractCegarLoop]: Abstraction has 167 states and 269 transitions. [2024-11-18 14:25:40,218 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 3.8666666666666667) internal successors, (58), 15 states have internal predecessors, (58), 6 states have call successors, (14), 1 states have call predecessors, (14), 5 states have return successors, (17), 8 states have call predecessors, (17), 6 states have call successors, (17) [2024-11-18 14:25:40,218 INFO L276 IsEmpty]: Start isEmpty. Operand 167 states and 269 transitions. [2024-11-18 14:25:40,220 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 382 [2024-11-18 14:25:40,220 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:40,220 INFO L215 NwaCegarLoop]: trace histogram [29, 29, 26, 26, 25, 22, 14, 14, 14, 14, 14, 14, 14, 13, 13, 13, 13, 13, 13, 13, 12, 8, 4, 4, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:40,237 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-18 14:25:40,421 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-18 14:25:40,421 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:40,421 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:40,421 INFO L85 PathProgramCache]: Analyzing trace with hash -1042913477, now seen corresponding path program 7 times [2024-11-18 14:25:40,421 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:40,421 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [117295087] [2024-11-18 14:25:40,421 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-18 14:25:40,421 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:40,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:40,740 INFO L134 CoverageAnalysis]: Checked inductivity of 4131 backedges. 376 proven. 304 refuted. 0 times theorem prover too weak. 3451 trivial. 0 not checked. [2024-11-18 14:25:40,741 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:40,741 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [117295087] [2024-11-18 14:25:40,741 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [117295087] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:40,741 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2134175029] [2024-11-18 14:25:40,741 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-18 14:25:40,741 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:40,741 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:40,743 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:25:40,744 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-18 14:25:40,916 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 14:25:40,918 INFO L255 TraceCheckSpWp]: Trace formula consists of 865 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-18 14:25:40,922 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:41,063 INFO L134 CoverageAnalysis]: Checked inductivity of 4131 backedges. 234 proven. 705 refuted. 0 times theorem prover too weak. 3192 trivial. 0 not checked. [2024-11-18 14:25:41,063 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:42,607 INFO L134 CoverageAnalysis]: Checked inductivity of 4131 backedges. 242 proven. 718 refuted. 0 times theorem prover too weak. 3171 trivial. 0 not checked. [2024-11-18 14:25:42,608 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2134175029] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:42,608 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:42,608 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 12, 17] total 27 [2024-11-18 14:25:42,608 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1357951032] [2024-11-18 14:25:42,608 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:42,609 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-18 14:25:42,609 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:42,609 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-18 14:25:42,609 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=615, Unknown=0, NotChecked=0, Total=702 [2024-11-18 14:25:42,610 INFO L87 Difference]: Start difference. First operand 167 states and 269 transitions. Second operand has 27 states, 25 states have (on average 3.6) internal successors, (90), 27 states have internal predecessors, (90), 19 states have call successors, (27), 1 states have call predecessors, (27), 13 states have return successors, (33), 17 states have call predecessors, (33), 19 states have call successors, (33) [2024-11-18 14:25:43,315 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:43,316 INFO L93 Difference]: Finished difference Result 591 states and 1482 transitions. [2024-11-18 14:25:43,318 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2024-11-18 14:25:43,319 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 25 states have (on average 3.6) internal successors, (90), 27 states have internal predecessors, (90), 19 states have call successors, (27), 1 states have call predecessors, (27), 13 states have return successors, (33), 17 states have call predecessors, (33), 19 states have call successors, (33) Word has length 381 [2024-11-18 14:25:43,319 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:43,324 INFO L225 Difference]: With dead ends: 591 [2024-11-18 14:25:43,324 INFO L226 Difference]: Without dead ends: 357 [2024-11-18 14:25:43,329 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 800 GetRequests, 740 SyntacticMatches, 8 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 624 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=409, Invalid=2453, Unknown=0, NotChecked=0, Total=2862 [2024-11-18 14:25:43,329 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 122 mSDsluCounter, 530 mSDsCounter, 0 mSdLazyCounter, 1102 mSolverCounterSat, 165 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 122 SdHoareTripleChecker+Valid, 575 SdHoareTripleChecker+Invalid, 1267 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 165 IncrementalHoareTripleChecker+Valid, 1102 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:43,329 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [122 Valid, 575 Invalid, 1267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [165 Valid, 1102 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-18 14:25:43,330 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 357 states. [2024-11-18 14:25:43,352 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 357 to 280. [2024-11-18 14:25:43,353 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 280 states, 194 states have (on average 1.1443298969072164) internal successors, (222), 185 states have internal predecessors, (222), 56 states have call successors, (56), 36 states have call predecessors, (56), 29 states have return successors, (262), 58 states have call predecessors, (262), 56 states have call successors, (262) [2024-11-18 14:25:43,355 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 280 states to 280 states and 540 transitions. [2024-11-18 14:25:43,356 INFO L78 Accepts]: Start accepts. Automaton has 280 states and 540 transitions. Word has length 381 [2024-11-18 14:25:43,356 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:43,356 INFO L471 AbstractCegarLoop]: Abstraction has 280 states and 540 transitions. [2024-11-18 14:25:43,356 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 25 states have (on average 3.6) internal successors, (90), 27 states have internal predecessors, (90), 19 states have call successors, (27), 1 states have call predecessors, (27), 13 states have return successors, (33), 17 states have call predecessors, (33), 19 states have call successors, (33) [2024-11-18 14:25:43,357 INFO L276 IsEmpty]: Start isEmpty. Operand 280 states and 540 transitions. [2024-11-18 14:25:43,359 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 459 [2024-11-18 14:25:43,359 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:43,360 INFO L215 NwaCegarLoop]: trace histogram [36, 36, 31, 31, 28, 24, 18, 18, 18, 18, 18, 18, 18, 15, 15, 15, 15, 15, 15, 15, 13, 8, 7, 6, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:43,373 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2024-11-18 14:25:43,563 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-18 14:25:43,564 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:43,564 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:43,564 INFO L85 PathProgramCache]: Analyzing trace with hash -1933234059, now seen corresponding path program 8 times [2024-11-18 14:25:43,564 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:43,564 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [371991977] [2024-11-18 14:25:43,564 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 14:25:43,564 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:43,606 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 14:25:43,606 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:43,879 INFO L134 CoverageAnalysis]: Checked inductivity of 6066 backedges. 300 proven. 695 refuted. 0 times theorem prover too weak. 5071 trivial. 0 not checked. [2024-11-18 14:25:43,879 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:43,879 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [371991977] [2024-11-18 14:25:43,879 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [371991977] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:43,880 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [417021136] [2024-11-18 14:25:43,880 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 14:25:43,880 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:43,880 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:43,882 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:25:43,884 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-18 14:25:44,084 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 14:25:44,084 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:44,087 INFO L255 TraceCheckSpWp]: Trace formula consists of 1037 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-18 14:25:44,093 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:44,266 INFO L134 CoverageAnalysis]: Checked inductivity of 6066 backedges. 312 proven. 994 refuted. 0 times theorem prover too weak. 4760 trivial. 0 not checked. [2024-11-18 14:25:44,266 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:46,481 INFO L134 CoverageAnalysis]: Checked inductivity of 6066 backedges. 314 proven. 1022 refuted. 0 times theorem prover too weak. 4730 trivial. 0 not checked. [2024-11-18 14:25:46,481 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [417021136] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:46,481 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:46,482 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 13, 19] total 30 [2024-11-18 14:25:46,482 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1393040784] [2024-11-18 14:25:46,482 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:46,483 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2024-11-18 14:25:46,483 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:46,483 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2024-11-18 14:25:46,484 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=767, Unknown=0, NotChecked=0, Total=870 [2024-11-18 14:25:46,484 INFO L87 Difference]: Start difference. First operand 280 states and 540 transitions. Second operand has 30 states, 28 states have (on average 3.5357142857142856) internal successors, (99), 30 states have internal predecessors, (99), 24 states have call successors, (30), 1 states have call predecessors, (30), 15 states have return successors, (38), 17 states have call predecessors, (38), 24 states have call successors, (38) [2024-11-18 14:25:47,377 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:47,377 INFO L93 Difference]: Finished difference Result 737 states and 1840 transitions. [2024-11-18 14:25:47,379 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2024-11-18 14:25:47,380 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 28 states have (on average 3.5357142857142856) internal successors, (99), 30 states have internal predecessors, (99), 24 states have call successors, (30), 1 states have call predecessors, (30), 15 states have return successors, (38), 17 states have call predecessors, (38), 24 states have call successors, (38) Word has length 458 [2024-11-18 14:25:47,380 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:47,385 INFO L225 Difference]: With dead ends: 737 [2024-11-18 14:25:47,386 INFO L226 Difference]: Without dead ends: 295 [2024-11-18 14:25:47,391 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 962 GetRequests, 892 SyntacticMatches, 9 SemanticMatches, 61 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 930 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=531, Invalid=3375, Unknown=0, NotChecked=0, Total=3906 [2024-11-18 14:25:47,392 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 126 mSDsluCounter, 555 mSDsCounter, 0 mSdLazyCounter, 1146 mSolverCounterSat, 145 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 126 SdHoareTripleChecker+Valid, 602 SdHoareTripleChecker+Invalid, 1291 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 145 IncrementalHoareTripleChecker+Valid, 1146 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:47,392 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [126 Valid, 602 Invalid, 1291 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [145 Valid, 1146 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-18 14:25:47,393 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 295 states. [2024-11-18 14:25:47,410 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 295 to 233. [2024-11-18 14:25:47,410 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 233 states, 161 states have (on average 1.1366459627329193) internal successors, (183), 155 states have internal predecessors, (183), 48 states have call successors, (48), 31 states have call predecessors, (48), 23 states have return successors, (163), 46 states have call predecessors, (163), 48 states have call successors, (163) [2024-11-18 14:25:47,412 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 233 states to 233 states and 394 transitions. [2024-11-18 14:25:47,413 INFO L78 Accepts]: Start accepts. Automaton has 233 states and 394 transitions. Word has length 458 [2024-11-18 14:25:47,413 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:47,413 INFO L471 AbstractCegarLoop]: Abstraction has 233 states and 394 transitions. [2024-11-18 14:25:47,413 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 28 states have (on average 3.5357142857142856) internal successors, (99), 30 states have internal predecessors, (99), 24 states have call successors, (30), 1 states have call predecessors, (30), 15 states have return successors, (38), 17 states have call predecessors, (38), 24 states have call successors, (38) [2024-11-18 14:25:47,414 INFO L276 IsEmpty]: Start isEmpty. Operand 233 states and 394 transitions. [2024-11-18 14:25:47,416 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 418 [2024-11-18 14:25:47,416 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:47,416 INFO L215 NwaCegarLoop]: trace histogram [31, 31, 30, 30, 24, 23, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 9, 8, 8, 6, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:47,432 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-11-18 14:25:47,617 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:47,617 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:47,618 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:47,618 INFO L85 PathProgramCache]: Analyzing trace with hash -2085485860, now seen corresponding path program 9 times [2024-11-18 14:25:47,618 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:47,618 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1313146286] [2024-11-18 14:25:47,618 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 14:25:47,618 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:47,640 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-18 14:25:47,640 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:47,736 INFO L134 CoverageAnalysis]: Checked inductivity of 4969 backedges. 629 proven. 17 refuted. 0 times theorem prover too weak. 4323 trivial. 0 not checked. [2024-11-18 14:25:47,736 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:47,737 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1313146286] [2024-11-18 14:25:47,737 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1313146286] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:47,737 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [657799784] [2024-11-18 14:25:47,737 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 14:25:47,737 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:47,737 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:47,738 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:25:47,739 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-18 14:25:47,880 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-18 14:25:47,880 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:47,882 INFO L255 TraceCheckSpWp]: Trace formula consists of 220 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-18 14:25:47,886 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:47,931 INFO L134 CoverageAnalysis]: Checked inductivity of 4969 backedges. 731 proven. 20 refuted. 0 times theorem prover too weak. 4218 trivial. 0 not checked. [2024-11-18 14:25:47,932 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:48,728 INFO L134 CoverageAnalysis]: Checked inductivity of 4969 backedges. 731 proven. 20 refuted. 0 times theorem prover too weak. 4218 trivial. 0 not checked. [2024-11-18 14:25:48,728 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [657799784] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:48,728 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:48,728 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 18 [2024-11-18 14:25:48,728 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1503500066] [2024-11-18 14:25:48,729 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:48,729 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-18 14:25:48,729 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:48,730 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-18 14:25:48,730 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=256, Unknown=0, NotChecked=0, Total=306 [2024-11-18 14:25:48,730 INFO L87 Difference]: Start difference. First operand 233 states and 394 transitions. Second operand has 18 states, 18 states have (on average 3.3333333333333335) internal successors, (60), 18 states have internal predecessors, (60), 8 states have call successors, (15), 1 states have call predecessors, (15), 6 states have return successors, (18), 8 states have call predecessors, (18), 8 states have call successors, (18) [2024-11-18 14:25:48,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:48,978 INFO L93 Difference]: Finished difference Result 453 states and 796 transitions. [2024-11-18 14:25:48,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-18 14:25:48,978 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 3.3333333333333335) internal successors, (60), 18 states have internal predecessors, (60), 8 states have call successors, (15), 1 states have call predecessors, (15), 6 states have return successors, (18), 8 states have call predecessors, (18), 8 states have call successors, (18) Word has length 417 [2024-11-18 14:25:48,979 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:48,981 INFO L225 Difference]: With dead ends: 453 [2024-11-18 14:25:48,981 INFO L226 Difference]: Without dead ends: 223 [2024-11-18 14:25:48,983 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 853 GetRequests, 822 SyntacticMatches, 5 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 95 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=148, Invalid=608, Unknown=0, NotChecked=0, Total=756 [2024-11-18 14:25:48,984 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 37 mSDsluCounter, 218 mSDsCounter, 0 mSdLazyCounter, 323 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 242 SdHoareTripleChecker+Invalid, 355 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 323 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:48,984 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 242 Invalid, 355 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 323 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:25:48,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 223 states. [2024-11-18 14:25:48,996 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 223 to 216. [2024-11-18 14:25:48,997 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 151 states have (on average 1.119205298013245) internal successors, (169), 145 states have internal predecessors, (169), 44 states have call successors, (44), 31 states have call predecessors, (44), 20 states have return successors, (121), 39 states have call predecessors, (121), 44 states have call successors, (121) [2024-11-18 14:25:48,998 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 334 transitions. [2024-11-18 14:25:48,998 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 334 transitions. Word has length 417 [2024-11-18 14:25:48,999 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:48,999 INFO L471 AbstractCegarLoop]: Abstraction has 216 states and 334 transitions. [2024-11-18 14:25:48,999 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 3.3333333333333335) internal successors, (60), 18 states have internal predecessors, (60), 8 states have call successors, (15), 1 states have call predecessors, (15), 6 states have return successors, (18), 8 states have call predecessors, (18), 8 states have call successors, (18) [2024-11-18 14:25:48,999 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 334 transitions. [2024-11-18 14:25:49,002 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 583 [2024-11-18 14:25:49,003 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:49,003 INFO L215 NwaCegarLoop]: trace histogram [43, 43, 42, 42, 35, 33, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 14, 12, 10, 7, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:49,018 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-18 14:25:49,207 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-18 14:25:49,208 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:49,208 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:49,208 INFO L85 PathProgramCache]: Analyzing trace with hash -1284951694, now seen corresponding path program 10 times [2024-11-18 14:25:49,209 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:49,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [65031755] [2024-11-18 14:25:49,209 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 14:25:49,209 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:49,252 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 14:25:49,252 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:49,427 INFO L134 CoverageAnalysis]: Checked inductivity of 9859 backedges. 722 proven. 129 refuted. 0 times theorem prover too weak. 9008 trivial. 0 not checked. [2024-11-18 14:25:49,427 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:49,427 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [65031755] [2024-11-18 14:25:49,427 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [65031755] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:49,427 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1177105999] [2024-11-18 14:25:49,427 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 14:25:49,427 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:49,427 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:49,429 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:25:49,433 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-18 14:25:49,645 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 14:25:49,646 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:49,649 INFO L255 TraceCheckSpWp]: Trace formula consists of 1035 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-18 14:25:49,678 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:49,830 INFO L134 CoverageAnalysis]: Checked inductivity of 9859 backedges. 810 proven. 964 refuted. 0 times theorem prover too weak. 8085 trivial. 0 not checked. [2024-11-18 14:25:49,831 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:52,177 INFO L134 CoverageAnalysis]: Checked inductivity of 9859 backedges. 810 proven. 994 refuted. 0 times theorem prover too weak. 8055 trivial. 0 not checked. [2024-11-18 14:25:52,178 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1177105999] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:52,178 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:52,178 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 13, 19] total 28 [2024-11-18 14:25:52,178 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [694312998] [2024-11-18 14:25:52,178 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:52,179 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-11-18 14:25:52,179 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:52,179 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-18 14:25:52,180 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=661, Unknown=0, NotChecked=0, Total=756 [2024-11-18 14:25:52,180 INFO L87 Difference]: Start difference. First operand 216 states and 334 transitions. Second operand has 28 states, 26 states have (on average 3.6153846153846154) internal successors, (94), 28 states have internal predecessors, (94), 21 states have call successors, (29), 1 states have call predecessors, (29), 13 states have return successors, (35), 17 states have call predecessors, (35), 21 states have call successors, (35) [2024-11-18 14:25:52,858 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:52,858 INFO L93 Difference]: Finished difference Result 360 states and 544 transitions. [2024-11-18 14:25:52,859 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2024-11-18 14:25:52,859 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 26 states have (on average 3.6153846153846154) internal successors, (94), 28 states have internal predecessors, (94), 21 states have call successors, (29), 1 states have call predecessors, (29), 13 states have return successors, (35), 17 states have call predecessors, (35), 21 states have call successors, (35) Word has length 582 [2024-11-18 14:25:52,860 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:52,863 INFO L225 Difference]: With dead ends: 360 [2024-11-18 14:25:52,863 INFO L226 Difference]: Without dead ends: 254 [2024-11-18 14:25:52,865 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 1201 GetRequests, 1138 SyntacticMatches, 9 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 691 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=435, Invalid=2645, Unknown=0, NotChecked=0, Total=3080 [2024-11-18 14:25:52,866 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 76 mSDsluCounter, 532 mSDsCounter, 0 mSdLazyCounter, 1028 mSolverCounterSat, 82 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 76 SdHoareTripleChecker+Valid, 581 SdHoareTripleChecker+Invalid, 1110 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 82 IncrementalHoareTripleChecker+Valid, 1028 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:52,866 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [76 Valid, 581 Invalid, 1110 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [82 Valid, 1028 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-18 14:25:52,867 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 254 states. [2024-11-18 14:25:52,883 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 254 to 227. [2024-11-18 14:25:52,883 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 227 states, 157 states have (on average 1.0955414012738853) internal successors, (172), 154 states have internal predecessors, (172), 49 states have call successors, (49), 33 states have call predecessors, (49), 20 states have return successors, (104), 39 states have call predecessors, (104), 49 states have call successors, (104) [2024-11-18 14:25:52,885 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 227 states to 227 states and 325 transitions. [2024-11-18 14:25:52,886 INFO L78 Accepts]: Start accepts. Automaton has 227 states and 325 transitions. Word has length 582 [2024-11-18 14:25:52,886 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:52,886 INFO L471 AbstractCegarLoop]: Abstraction has 227 states and 325 transitions. [2024-11-18 14:25:52,887 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 26 states have (on average 3.6153846153846154) internal successors, (94), 28 states have internal predecessors, (94), 21 states have call successors, (29), 1 states have call predecessors, (29), 13 states have return successors, (35), 17 states have call predecessors, (35), 21 states have call successors, (35) [2024-11-18 14:25:52,887 INFO L276 IsEmpty]: Start isEmpty. Operand 227 states and 325 transitions. [2024-11-18 14:25:52,889 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 420 [2024-11-18 14:25:52,889 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:52,890 INFO L215 NwaCegarLoop]: trace histogram [31, 31, 30, 30, 25, 24, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 10, 9, 6, 6, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:52,910 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2024-11-18 14:25:53,090 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-18 14:25:53,091 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:53,091 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:53,091 INFO L85 PathProgramCache]: Analyzing trace with hash 1862425916, now seen corresponding path program 11 times [2024-11-18 14:25:53,091 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:53,092 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [80362691] [2024-11-18 14:25:53,092 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-18 14:25:53,092 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:53,142 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 20 check-sat command(s) [2024-11-18 14:25:53,143 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:54,335 INFO L134 CoverageAnalysis]: Checked inductivity of 5016 backedges. 811 proven. 923 refuted. 0 times theorem prover too weak. 3282 trivial. 0 not checked. [2024-11-18 14:25:54,335 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:54,335 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [80362691] [2024-11-18 14:25:54,335 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [80362691] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:54,335 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2146331381] [2024-11-18 14:25:54,335 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-18 14:25:54,335 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:54,335 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:54,336 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:25:54,337 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-18 14:25:54,557 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 20 check-sat command(s) [2024-11-18 14:25:54,557 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:54,560 INFO L255 TraceCheckSpWp]: Trace formula consists of 806 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-18 14:25:54,564 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:54,682 INFO L134 CoverageAnalysis]: Checked inductivity of 5016 backedges. 921 proven. 579 refuted. 0 times theorem prover too weak. 3516 trivial. 0 not checked. [2024-11-18 14:25:54,682 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:56,814 INFO L134 CoverageAnalysis]: Checked inductivity of 5016 backedges. 921 proven. 598 refuted. 0 times theorem prover too weak. 3497 trivial. 0 not checked. [2024-11-18 14:25:56,814 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2146331381] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:56,814 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:56,814 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 17, 23] total 43 [2024-11-18 14:25:56,814 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [33862715] [2024-11-18 14:25:56,814 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:56,815 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 43 states [2024-11-18 14:25:56,815 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:56,815 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2024-11-18 14:25:56,816 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=167, Invalid=1639, Unknown=0, NotChecked=0, Total=1806 [2024-11-18 14:25:56,816 INFO L87 Difference]: Start difference. First operand 227 states and 325 transitions. Second operand has 43 states, 42 states have (on average 2.9523809523809526) internal successors, (124), 41 states have internal predecessors, (124), 25 states have call successors, (34), 1 states have call predecessors, (34), 18 states have return successors, (43), 21 states have call predecessors, (43), 25 states have call successors, (43) [2024-11-18 14:25:57,796 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:57,796 INFO L93 Difference]: Finished difference Result 290 states and 418 transitions. [2024-11-18 14:25:57,797 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2024-11-18 14:25:57,797 INFO L78 Accepts]: Start accepts. Automaton has has 43 states, 42 states have (on average 2.9523809523809526) internal successors, (124), 41 states have internal predecessors, (124), 25 states have call successors, (34), 1 states have call predecessors, (34), 18 states have return successors, (43), 21 states have call predecessors, (43), 25 states have call successors, (43) Word has length 419 [2024-11-18 14:25:57,798 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:57,800 INFO L225 Difference]: With dead ends: 290 [2024-11-18 14:25:57,801 INFO L226 Difference]: Without dead ends: 270 [2024-11-18 14:25:57,803 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 907 GetRequests, 822 SyntacticMatches, 12 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1360 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=700, Invalid=4850, Unknown=0, NotChecked=0, Total=5550 [2024-11-18 14:25:57,803 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 125 mSDsluCounter, 708 mSDsCounter, 0 mSdLazyCounter, 1492 mSolverCounterSat, 139 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 125 SdHoareTripleChecker+Valid, 749 SdHoareTripleChecker+Invalid, 1631 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 139 IncrementalHoareTripleChecker+Valid, 1492 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:57,804 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [125 Valid, 749 Invalid, 1631 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [139 Valid, 1492 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-18 14:25:57,804 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 270 states. [2024-11-18 14:25:57,817 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 270 to 241. [2024-11-18 14:25:57,818 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 241 states, 168 states have (on average 1.0892857142857142) internal successors, (183), 165 states have internal predecessors, (183), 52 states have call successors, (52), 37 states have call predecessors, (52), 20 states have return successors, (109), 38 states have call predecessors, (109), 52 states have call successors, (109) [2024-11-18 14:25:57,819 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 241 states to 241 states and 344 transitions. [2024-11-18 14:25:57,819 INFO L78 Accepts]: Start accepts. Automaton has 241 states and 344 transitions. Word has length 419 [2024-11-18 14:25:57,820 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:57,820 INFO L471 AbstractCegarLoop]: Abstraction has 241 states and 344 transitions. [2024-11-18 14:25:57,820 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 43 states, 42 states have (on average 2.9523809523809526) internal successors, (124), 41 states have internal predecessors, (124), 25 states have call successors, (34), 1 states have call predecessors, (34), 18 states have return successors, (43), 21 states have call predecessors, (43), 25 states have call successors, (43) [2024-11-18 14:25:57,820 INFO L276 IsEmpty]: Start isEmpty. Operand 241 states and 344 transitions. [2024-11-18 14:25:57,823 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 541 [2024-11-18 14:25:57,823 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:57,823 INFO L215 NwaCegarLoop]: trace histogram [40, 40, 39, 39, 32, 30, 20, 20, 20, 20, 20, 20, 20, 19, 19, 19, 19, 19, 19, 19, 13, 10, 9, 8, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:57,844 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2024-11-18 14:25:58,024 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:58,024 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:58,025 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:58,025 INFO L85 PathProgramCache]: Analyzing trace with hash -354325783, now seen corresponding path program 12 times [2024-11-18 14:25:58,025 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:58,025 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1081082922] [2024-11-18 14:25:58,025 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-18 14:25:58,025 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:58,061 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 15 check-sat command(s) [2024-11-18 14:25:58,061 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:58,162 INFO L134 CoverageAnalysis]: Checked inductivity of 8459 backedges. 685 proven. 75 refuted. 0 times theorem prover too weak. 7699 trivial. 0 not checked. [2024-11-18 14:25:58,162 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 14:25:58,163 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1081082922] [2024-11-18 14:25:58,163 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1081082922] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 14:25:58,163 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [491848474] [2024-11-18 14:25:58,163 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-18 14:25:58,163 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:58,163 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 14:25:58,165 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 14:25:58,166 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-18 14:25:58,392 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 15 check-sat command(s) [2024-11-18 14:25:58,392 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 14:25:58,394 INFO L255 TraceCheckSpWp]: Trace formula consists of 478 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-18 14:25:58,399 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 14:25:58,439 INFO L134 CoverageAnalysis]: Checked inductivity of 8459 backedges. 2468 proven. 6 refuted. 0 times theorem prover too weak. 5985 trivial. 0 not checked. [2024-11-18 14:25:58,440 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 14:25:59,556 INFO L134 CoverageAnalysis]: Checked inductivity of 8459 backedges. 811 proven. 93 refuted. 0 times theorem prover too weak. 7555 trivial. 0 not checked. [2024-11-18 14:25:59,556 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [491848474] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 14:25:59,556 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 14:25:59,557 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 15 [2024-11-18 14:25:59,557 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1843701154] [2024-11-18 14:25:59,557 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 14:25:59,557 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-18 14:25:59,557 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 14:25:59,558 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-18 14:25:59,558 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=166, Unknown=0, NotChecked=0, Total=210 [2024-11-18 14:25:59,558 INFO L87 Difference]: Start difference. First operand 241 states and 344 transitions. Second operand has 15 states, 15 states have (on average 4.2) internal successors, (63), 15 states have internal predecessors, (63), 7 states have call successors, (16), 2 states have call predecessors, (16), 5 states have return successors, (19), 5 states have call predecessors, (19), 7 states have call successors, (19) [2024-11-18 14:25:59,650 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 14:25:59,651 INFO L93 Difference]: Finished difference Result 438 states and 646 transitions. [2024-11-18 14:25:59,651 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-18 14:25:59,651 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 4.2) internal successors, (63), 15 states have internal predecessors, (63), 7 states have call successors, (16), 2 states have call predecessors, (16), 5 states have return successors, (19), 5 states have call predecessors, (19), 7 states have call successors, (19) Word has length 540 [2024-11-18 14:25:59,652 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 14:25:59,653 INFO L225 Difference]: With dead ends: 438 [2024-11-18 14:25:59,653 INFO L226 Difference]: Without dead ends: 212 [2024-11-18 14:25:59,655 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 1092 GetRequests, 1070 SyntacticMatches, 4 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 74 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=84, Invalid=296, Unknown=0, NotChecked=0, Total=380 [2024-11-18 14:25:59,655 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 25 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 160 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 191 SdHoareTripleChecker+Invalid, 175 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 160 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 14:25:59,656 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 191 Invalid, 175 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 160 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 14:25:59,656 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 212 states. [2024-11-18 14:25:59,666 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 212 to 199. [2024-11-18 14:25:59,666 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 199 states, 139 states have (on average 1.064748201438849) internal successors, (148), 138 states have internal predecessors, (148), 42 states have call successors, (42), 31 states have call predecessors, (42), 17 states have return successors, (67), 29 states have call predecessors, (67), 42 states have call successors, (67) [2024-11-18 14:25:59,667 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 257 transitions. [2024-11-18 14:25:59,668 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 257 transitions. Word has length 540 [2024-11-18 14:25:59,668 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 14:25:59,668 INFO L471 AbstractCegarLoop]: Abstraction has 199 states and 257 transitions. [2024-11-18 14:25:59,668 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 4.2) internal successors, (63), 15 states have internal predecessors, (63), 7 states have call successors, (16), 2 states have call predecessors, (16), 5 states have return successors, (19), 5 states have call predecessors, (19), 7 states have call successors, (19) [2024-11-18 14:25:59,668 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 257 transitions. [2024-11-18 14:25:59,670 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 461 [2024-11-18 14:25:59,670 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 14:25:59,670 INFO L215 NwaCegarLoop]: trace histogram [34, 34, 33, 33, 27, 27, 17, 17, 17, 17, 17, 17, 17, 16, 16, 16, 16, 16, 16, 16, 11, 10, 7, 6, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:25:59,683 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2024-11-18 14:25:59,874 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 14:25:59,875 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 14:25:59,875 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 14:25:59,875 INFO L85 PathProgramCache]: Analyzing trace with hash 1402769443, now seen corresponding path program 13 times [2024-11-18 14:25:59,875 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 14:25:59,875 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1188440527] [2024-11-18 14:25:59,876 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-18 14:25:59,876 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 14:25:59,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-18 14:25:59,946 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-18 14:25:59,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-18 14:26:00,031 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-18 14:26:00,031 INFO L325 BasicCegarLoop]: Counterexample is feasible [2024-11-18 14:26:00,032 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-18 14:26:00,034 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20 [2024-11-18 14:26:00,036 INFO L407 BasicCegarLoop]: Path program histogram: [13, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 14:26:00,122 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-18 14:26:00,127 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.11 02:26:00 BoogieIcfgContainer [2024-11-18 14:26:00,127 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-18 14:26:00,128 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-18 14:26:00,128 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-18 14:26:00,128 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-18 14:26:00,129 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 02:25:20" (3/4) ... [2024-11-18 14:26:00,129 INFO L136 WitnessPrinter]: Generating witness for reachability counterexample [2024-11-18 14:26:00,211 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-18 14:26:00,214 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-18 14:26:00,215 INFO L158 Benchmark]: Toolchain (without parser) took 40166.82ms. Allocated memory was 151.0MB in the beginning and 627.0MB in the end (delta: 476.1MB). Free memory was 97.6MB in the beginning and 517.3MB in the end (delta: -419.8MB). Peak memory consumption was 57.9MB. Max. memory is 16.1GB. [2024-11-18 14:26:00,215 INFO L158 Benchmark]: CDTParser took 0.19ms. Allocated memory is still 151.0MB. Free memory is still 116.4MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-18 14:26:00,215 INFO L158 Benchmark]: CACSL2BoogieTranslator took 224.12ms. Allocated memory is still 151.0MB. Free memory was 97.6MB in the beginning and 85.6MB in the end (delta: 12.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-18 14:26:00,215 INFO L158 Benchmark]: Boogie Procedure Inliner took 24.69ms. Allocated memory is still 151.0MB. Free memory was 85.6MB in the beginning and 83.9MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-18 14:26:00,215 INFO L158 Benchmark]: Boogie Preprocessor took 26.06ms. Allocated memory is still 151.0MB. Free memory was 83.9MB in the beginning and 82.3MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-18 14:26:00,215 INFO L158 Benchmark]: RCFGBuilder took 273.55ms. Allocated memory is still 151.0MB. Free memory was 82.3MB in the beginning and 71.3MB in the end (delta: 11.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-18 14:26:00,216 INFO L158 Benchmark]: TraceAbstraction took 39524.45ms. Allocated memory was 151.0MB in the beginning and 627.0MB in the end (delta: 476.1MB). Free memory was 70.9MB in the beginning and 525.7MB in the end (delta: -454.8MB). Peak memory consumption was 24.4MB. Max. memory is 16.1GB. [2024-11-18 14:26:00,216 INFO L158 Benchmark]: Witness Printer took 86.41ms. Allocated memory is still 627.0MB. Free memory was 525.7MB in the beginning and 517.3MB in the end (delta: 8.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-18 14:26:00,217 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.19ms. Allocated memory is still 151.0MB. Free memory is still 116.4MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 224.12ms. Allocated memory is still 151.0MB. Free memory was 97.6MB in the beginning and 85.6MB in the end (delta: 12.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 24.69ms. Allocated memory is still 151.0MB. Free memory was 85.6MB in the beginning and 83.9MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 26.06ms. Allocated memory is still 151.0MB. Free memory was 83.9MB in the beginning and 82.3MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 273.55ms. Allocated memory is still 151.0MB. Free memory was 82.3MB in the beginning and 71.3MB in the end (delta: 11.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * TraceAbstraction took 39524.45ms. Allocated memory was 151.0MB in the beginning and 627.0MB in the end (delta: 476.1MB). Free memory was 70.9MB in the beginning and 525.7MB in the end (delta: -454.8MB). Peak memory consumption was 24.4MB. Max. memory is 16.1GB. * Witness Printer took 86.41ms. Allocated memory is still 627.0MB. Free memory was 525.7MB in the beginning and 517.3MB in the end (delta: 8.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 41]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L38] int x = 8; VAL [x=8] [L39] CALL, EXPR fibo1(x) VAL [\old(n)=8] [L10] COND FALSE !(n < 1) VAL [\old(n)=8, n=8] [L12] COND FALSE !(n == 1) VAL [\old(n)=8, n=8] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=7] [L20] COND FALSE !(n < 1) VAL [\old(n)=7, n=7] [L22] COND FALSE !(n == 1) VAL [\old(n)=7, n=7] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=6] [L10] COND FALSE !(n < 1) VAL [\old(n)=6, n=6] [L12] COND FALSE !(n == 1) VAL [\old(n)=6, n=6] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=5] [L20] COND FALSE !(n < 1) VAL [\old(n)=5, n=5] [L22] COND FALSE !(n == 1) VAL [\old(n)=5, n=5] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=4] [L10] COND FALSE !(n < 1) VAL [\old(n)=4, n=4] [L12] COND FALSE !(n == 1) VAL [\old(n)=4, n=4] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=3] [L20] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L22] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=2] [L10] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L12] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=1] [L20] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L22] COND TRUE n == 1 [L23] return 1; VAL [\old(n)=1, \result=1] [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=0] [L20] COND TRUE n < 1 [L21] return 0; VAL [\old(n)=0, \result=0] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=2, n=2] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=3, n=3] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=3, n=3] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=4, n=4] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=2] [L20] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L22] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1] [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=0] [L10] COND TRUE n < 1 [L11] return 0; VAL [\old(n)=0, \result=0] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=2, n=2] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=4, n=4] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=5, n=5] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=3] [L10] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L12] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=2] [L20] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L22] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1] [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=0] [L10] COND TRUE n < 1 [L11] return 0; VAL [\old(n)=0, \result=0] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=2, n=2] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=3, n=3] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=1] [L20] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L22] COND TRUE n == 1 [L23] return 1; VAL [\old(n)=1, \result=1] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=3, n=3] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=5, n=5] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=6, n=6] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=4] [L20] COND FALSE !(n < 1) VAL [\old(n)=4, n=4] [L22] COND FALSE !(n == 1) VAL [\old(n)=4, n=4] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=3] [L10] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L12] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=2] [L20] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L22] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1] [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=0] [L10] COND TRUE n < 1 [L11] return 0; VAL [\old(n)=0, \result=0] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=2, n=2] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=3, n=3] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=1] [L20] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L22] COND TRUE n == 1 [L23] return 1; VAL [\old(n)=1, \result=1] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=3, n=3] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=4, n=4] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=2] [L10] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L12] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=1] [L20] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L22] COND TRUE n == 1 [L23] return 1; VAL [\old(n)=1, \result=1] [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=0] [L20] COND TRUE n < 1 [L21] return 0; VAL [\old(n)=0, \result=0] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=2, n=2] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=4, n=4] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=6, n=6] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=7, n=7] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=5] [L10] COND FALSE !(n < 1) VAL [\old(n)=5, n=5] [L12] COND FALSE !(n == 1) VAL [\old(n)=5, n=5] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=4] [L20] COND FALSE !(n < 1) VAL [\old(n)=4, n=4] [L22] COND FALSE !(n == 1) VAL [\old(n)=4, n=4] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=3] [L10] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L12] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=2] [L20] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L22] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1] [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=0] [L10] COND TRUE n < 1 [L11] return 0; VAL [\old(n)=0, \result=0] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=2, n=2] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=3, n=3] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=1] [L20] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L22] COND TRUE n == 1 [L23] return 1; VAL [\old(n)=1, \result=1] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=3, n=3] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=4, n=4] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=2] [L10] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L12] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=1] [L20] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L22] COND TRUE n == 1 [L23] return 1; VAL [\old(n)=1, \result=1] [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=0] [L20] COND TRUE n < 1 [L21] return 0; VAL [\old(n)=0, \result=0] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=2, n=2] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=4, n=4] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=5, n=5] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=3] [L20] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L22] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=2] [L10] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L12] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=1] [L20] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L22] COND TRUE n == 1 [L23] return 1; VAL [\old(n)=1, \result=1] [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=0] [L20] COND TRUE n < 1 [L21] return 0; VAL [\old(n)=0, \result=0] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=2, n=2] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=3, n=3] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=3, n=3] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=5, n=5] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=7, n=7] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=8, n=8] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=6] [L20] COND FALSE !(n < 1) VAL [\old(n)=6, n=6] [L22] COND FALSE !(n == 1) VAL [\old(n)=6, n=6] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=5] [L10] COND FALSE !(n < 1) VAL [\old(n)=5, n=5] [L12] COND FALSE !(n == 1) VAL [\old(n)=5, n=5] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=4] [L20] COND FALSE !(n < 1) VAL [\old(n)=4, n=4] [L22] COND FALSE !(n == 1) VAL [\old(n)=4, n=4] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=3] [L10] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L12] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=2] [L20] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L22] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1] [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=0] [L10] COND TRUE n < 1 [L11] return 0; VAL [\old(n)=0, \result=0] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=2, n=2] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=3, n=3] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=1] [L20] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L22] COND TRUE n == 1 [L23] return 1; VAL [\old(n)=1, \result=1] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=3, n=3] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=4, n=4] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=2] [L10] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L12] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=1] [L20] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L22] COND TRUE n == 1 [L23] return 1; VAL [\old(n)=1, \result=1] [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=0] [L20] COND TRUE n < 1 [L21] return 0; VAL [\old(n)=0, \result=0] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=2, n=2] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=4, n=4] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=5, n=5] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=3] [L20] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L22] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=2] [L10] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L12] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=1] [L20] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L22] COND TRUE n == 1 [L23] return 1; VAL [\old(n)=1, \result=1] [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=0] [L20] COND TRUE n < 1 [L21] return 0; VAL [\old(n)=0, \result=0] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=2, n=2] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=3, n=3] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=3, n=3] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=5, n=5] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=6, n=6] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=4] [L10] COND FALSE !(n < 1) VAL [\old(n)=4, n=4] [L12] COND FALSE !(n == 1) VAL [\old(n)=4, n=4] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=3] [L20] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L22] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=2] [L10] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L12] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=1] [L20] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L22] COND TRUE n == 1 [L23] return 1; VAL [\old(n)=1, \result=1] [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=0] [L20] COND TRUE n < 1 [L21] return 0; VAL [\old(n)=0, \result=0] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=2, n=2] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=3, n=3] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=3, n=3] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=4, n=4] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=2] [L20] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L22] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1] [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=0] [L10] COND TRUE n < 1 [L11] return 0; VAL [\old(n)=0, \result=0] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=2, n=2] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=4, n=4] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=6, n=6] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=8, n=8] [L15] return fibo2(n-1) + fibo2(n-2); [L39] RET, EXPR fibo1(x) VAL [x=8] [L39] int result = fibo1(x); [L40] COND TRUE result == 21 VAL [x=8] [L41] reach_error() VAL [x=8] - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 29 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 39.4s, OverallIterations: 21, TraceHistogramMax: 43, PathProgramHistogramMax: 13, EmptinessCheckTime: 0.1s, AutomataDifference: 6.8s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 1067 SdHoareTripleChecker+Valid, 3.9s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 1003 mSDsluCounter, 5980 SdHoareTripleChecker+Invalid, 3.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 5354 mSDsCounter, 1098 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 8636 IncrementalHoareTripleChecker+Invalid, 9734 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 1098 mSolverCounterUnsat, 626 mSDtfsCounter, 8636 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 10819 GetRequests, 10144 SyntacticMatches, 102 SemanticMatches, 573 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5601 ImplicationChecksByTransitivity, 5.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=280occurred in iteration=15, InterpolantAutomatonStates: 386, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 20 MinimizatonAttempts, 400 StatesRemovedByMinimization, 18 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.3s SsaConstructionTime, 1.1s SatisfiabilityAnalysisTime, 25.4s InterpolantComputationTime, 10859 NumberOfCodeBlocks, 7233 NumberOfCodeBlocksAsserted, 155 NumberOfCheckSat, 15532 ConstructedInterpolants, 0 QuantifiedInterpolants, 20477 SizeOfPredicates, 74 NumberOfNonLiveVariables, 7671 ConjunctsInSsa, 215 ConjunctsInUnsatCore, 56 InterpolantComputations, 2 PerfectInterpolantSequences, 172282/188166 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2024-11-18 14:26:00,249 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE