./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_valuebound20.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 023d838f 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/nla-digbench-scaling/dijkstra-u_valuebound20.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 ec2a850a3cd9252437037b0e2bf289d9622078bb11b0dcb40fb1cb3d7147f7c5 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-09 22:30:27,807 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 22:30:27,889 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-09 22:30:27,893 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 22:30:27,893 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 22:30:27,914 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 22:30:27,914 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 22:30:27,914 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 22:30:27,915 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 22:30:27,918 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 22:30:27,918 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 22:30:27,918 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 22:30:27,918 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 22:30:27,918 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 22:30:27,919 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 22:30:27,919 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 22:30:27,919 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 22:30:27,919 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 22:30:27,919 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 22:30:27,919 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 22:30:27,919 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 22:30:27,922 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 22:30:27,922 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 22:30:27,922 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 22:30:27,922 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 22:30:27,922 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 22:30:27,923 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 22:30:27,923 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 22:30:27,923 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-09 22:30:27,923 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 22:30:27,924 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 22:30:27,924 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 22:30:27,924 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:30:27,924 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 22:30:27,925 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 22:30:27,925 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 22:30:27,925 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 22:30:27,925 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 22:30:27,925 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 22:30:27,925 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-09 22:30:27,926 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-09 22:30:27,926 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 22:30:27,926 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 -> ec2a850a3cd9252437037b0e2bf289d9622078bb11b0dcb40fb1cb3d7147f7c5 [2024-11-09 22:30:28,121 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 22:30:28,141 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 22:30:28,144 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 22:30:28,145 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 22:30:28,145 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 22:30:28,146 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_valuebound20.c [2024-11-09 22:30:29,353 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 22:30:29,513 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 22:30:29,514 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_valuebound20.c [2024-11-09 22:30:29,520 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a307d5a89/0848d6014cde41c5837793057cca004a/FLAGbcad7635e [2024-11-09 22:30:29,936 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a307d5a89/0848d6014cde41c5837793057cca004a [2024-11-09 22:30:29,942 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 22:30:29,943 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 22:30:29,944 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 22:30:29,945 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 22:30:29,949 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 22:30:29,950 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:30:29" (1/1) ... [2024-11-09 22:30:29,951 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@550d9ede and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:29, skipping insertion in model container [2024-11-09 22:30:29,951 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:30:29" (1/1) ... [2024-11-09 22:30:29,969 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 22:30:30,116 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_valuebound20.c[525,538] [2024-11-09 22:30:30,140 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:30:30,153 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 22:30:30,161 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_valuebound20.c[525,538] [2024-11-09 22:30:30,171 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:30:30,185 INFO L204 MainTranslator]: Completed translation [2024-11-09 22:30:30,186 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30 WrapperNode [2024-11-09 22:30:30,186 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 22:30:30,187 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 22:30:30,187 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 22:30:30,187 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 22:30:30,192 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30" (1/1) ... [2024-11-09 22:30:30,199 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30" (1/1) ... [2024-11-09 22:30:30,212 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 51 [2024-11-09 22:30:30,212 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 22:30:30,213 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 22:30:30,213 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 22:30:30,213 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 22:30:30,221 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30" (1/1) ... [2024-11-09 22:30:30,221 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30" (1/1) ... [2024-11-09 22:30:30,223 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30" (1/1) ... [2024-11-09 22:30:30,247 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-09 22:30:30,248 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30" (1/1) ... [2024-11-09 22:30:30,248 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30" (1/1) ... [2024-11-09 22:30:30,250 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30" (1/1) ... [2024-11-09 22:30:30,250 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30" (1/1) ... [2024-11-09 22:30:30,251 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30" (1/1) ... [2024-11-09 22:30:30,252 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30" (1/1) ... [2024-11-09 22:30:30,253 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 22:30:30,254 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-09 22:30:30,254 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-09 22:30:30,254 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-09 22:30:30,255 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30" (1/1) ... [2024-11-09 22:30:30,260 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:30:30,274 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:30:30,292 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-09 22:30:30,299 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-09 22:30:30,330 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 22:30:30,331 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-09 22:30:30,331 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-09 22:30:30,331 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 22:30:30,331 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 22:30:30,331 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 22:30:30,331 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 22:30:30,335 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 22:30:30,397 INFO L256 CfgBuilder]: Building ICFG [2024-11-09 22:30:30,399 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 22:30:30,566 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-09 22:30:30,567 INFO L307 CfgBuilder]: Performing block encoding [2024-11-09 22:30:30,580 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 22:30:30,580 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 22:30:30,580 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:30:30 BoogieIcfgContainer [2024-11-09 22:30:30,581 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-09 22:30:30,582 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 22:30:30,583 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 22:30:30,586 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 22:30:30,586 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 10:30:29" (1/3) ... [2024-11-09 22:30:30,587 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1f8ecd89 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:30:30, skipping insertion in model container [2024-11-09 22:30:30,587 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:30:30" (2/3) ... [2024-11-09 22:30:30,587 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1f8ecd89 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:30:30, skipping insertion in model container [2024-11-09 22:30:30,588 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:30:30" (3/3) ... [2024-11-09 22:30:30,589 INFO L112 eAbstractionObserver]: Analyzing ICFG dijkstra-u_valuebound20.c [2024-11-09 22:30:30,602 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 22:30:30,602 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 22:30:30,642 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 22:30:30,652 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;@1b070295, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 22:30:30,653 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 22:30:30,660 INFO L276 IsEmpty]: Start isEmpty. Operand has 36 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-09 22:30:30,666 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2024-11-09 22:30:30,666 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:30:30,667 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:30:30,667 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:30:30,671 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:30:30,671 INFO L85 PathProgramCache]: Analyzing trace with hash -1944071338, now seen corresponding path program 1 times [2024-11-09 22:30:30,678 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:30:30,679 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [777304406] [2024-11-09 22:30:30,679 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:30,679 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:30:30,800 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:30,868 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 22:30:30,870 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:30,877 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 22:30:30,881 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:30,887 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 22:30:30,888 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:30:30,888 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [777304406] [2024-11-09 22:30:30,889 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [777304406] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:30:30,889 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:30:30,890 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 22:30:30,891 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [931302267] [2024-11-09 22:30:30,892 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:30:30,895 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-09 22:30:30,895 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:30:30,912 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-09 22:30:30,912 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 22:30:30,914 INFO L87 Difference]: Start difference. First operand has 36 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 22:30:30,933 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:30:30,934 INFO L93 Difference]: Finished difference Result 69 states and 113 transitions. [2024-11-09 22:30:30,935 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 22:30:30,936 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2024-11-09 22:30:30,936 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:30:30,942 INFO L225 Difference]: With dead ends: 69 [2024-11-09 22:30:30,942 INFO L226 Difference]: Without dead ends: 32 [2024-11-09 22:30:30,946 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 22:30:30,949 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 47 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:30:30,951 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:30:30,964 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2024-11-09 22:30:30,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2024-11-09 22:30:30,983 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-09 22:30:30,985 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 43 transitions. [2024-11-09 22:30:30,987 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 43 transitions. Word has length 20 [2024-11-09 22:30:30,988 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:30:30,988 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 43 transitions. [2024-11-09 22:30:30,988 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 22:30:30,988 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 43 transitions. [2024-11-09 22:30:30,989 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-09 22:30:30,990 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:30:30,990 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-09 22:30:30,991 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 22:30:30,991 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:30:30,992 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:30:30,992 INFO L85 PathProgramCache]: Analyzing trace with hash -242934201, now seen corresponding path program 1 times [2024-11-09 22:30:30,992 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:30:30,993 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1332904466] [2024-11-09 22:30:30,993 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:30,994 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:30:31,038 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:31,399 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 22:30:31,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:31,403 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 22:30:31,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:31,407 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 22:30:31,408 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:30:31,408 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1332904466] [2024-11-09 22:30:31,408 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1332904466] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:30:31,408 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:30:31,408 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-09 22:30:31,409 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1566521280] [2024-11-09 22:30:31,409 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:30:31,410 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-09 22:30:31,410 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:30:31,411 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 22:30:31,411 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:30:31,411 INFO L87 Difference]: Start difference. First operand 32 states and 43 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 22:30:31,676 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:30:31,676 INFO L93 Difference]: Finished difference Result 68 states and 96 transitions. [2024-11-09 22:30:31,677 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 22:30:31,677 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 23 [2024-11-09 22:30:31,677 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:30:31,678 INFO L225 Difference]: With dead ends: 68 [2024-11-09 22:30:31,678 INFO L226 Difference]: Without dead ends: 48 [2024-11-09 22:30:31,678 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-09 22:30:31,679 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 6 mSDsluCounter, 135 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 174 SdHoareTripleChecker+Invalid, 61 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 22:30:31,680 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 174 Invalid, 61 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 22:30:31,680 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2024-11-09 22:30:31,690 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2024-11-09 22:30:31,691 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 28 states have internal predecessors, (32), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-09 22:30:31,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 65 transitions. [2024-11-09 22:30:31,692 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 65 transitions. Word has length 23 [2024-11-09 22:30:31,693 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:30:31,693 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 65 transitions. [2024-11-09 22:30:31,693 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 22:30:31,693 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 65 transitions. [2024-11-09 22:30:31,694 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-11-09 22:30:31,694 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:30:31,694 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:30:31,694 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-09 22:30:31,694 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:30:31,695 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:30:31,695 INFO L85 PathProgramCache]: Analyzing trace with hash -756934275, now seen corresponding path program 1 times [2024-11-09 22:30:31,695 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:30:31,695 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2030633991] [2024-11-09 22:30:31,695 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:31,696 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:30:31,707 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:31,946 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 22:30:31,947 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:31,950 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 22:30:31,952 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:31,953 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 22:30:31,954 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:30:31,954 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2030633991] [2024-11-09 22:30:31,954 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2030633991] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:30:31,954 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2141399398] [2024-11-09 22:30:31,954 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:31,955 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:30:31,955 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:30:31,962 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-09 22:30:31,967 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-09 22:30:32,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:32,014 INFO L255 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-09 22:30:32,018 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:30:32,171 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 22:30:32,171 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:30:32,319 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 22:30:32,319 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2141399398] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:30:32,319 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 22:30:32,320 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 15 [2024-11-09 22:30:32,320 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1098296482] [2024-11-09 22:30:32,320 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 22:30:32,320 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-09 22:30:32,320 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:30:32,321 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-09 22:30:32,321 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=162, Unknown=0, NotChecked=0, Total=210 [2024-11-09 22:30:32,321 INFO L87 Difference]: Start difference. First operand 48 states and 65 transitions. Second operand has 15 states, 15 states have (on average 2.533333333333333) internal successors, (38), 13 states have internal predecessors, (38), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 22:30:37,865 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-09 22:30:37,994 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:30:37,997 INFO L93 Difference]: Finished difference Result 125 states and 191 transitions. [2024-11-09 22:30:37,997 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-09 22:30:37,997 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.533333333333333) internal successors, (38), 13 states have internal predecessors, (38), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 26 [2024-11-09 22:30:37,998 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:30:37,999 INFO L225 Difference]: With dead ends: 125 [2024-11-09 22:30:38,000 INFO L226 Difference]: Without dead ends: 105 [2024-11-09 22:30:38,001 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 47 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 84 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=93, Invalid=287, Unknown=0, NotChecked=0, Total=380 [2024-11-09 22:30:38,002 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 30 mSDsluCounter, 267 mSDsCounter, 0 mSdLazyCounter, 233 mSolverCounterSat, 92 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 308 SdHoareTripleChecker+Invalid, 326 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 92 IncrementalHoareTripleChecker+Valid, 233 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.6s IncrementalHoareTripleChecker+Time [2024-11-09 22:30:38,003 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 308 Invalid, 326 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [92 Valid, 233 Invalid, 1 Unknown, 0 Unchecked, 5.6s Time] [2024-11-09 22:30:38,004 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states. [2024-11-09 22:30:38,024 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 71. [2024-11-09 22:30:38,025 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 41 states have (on average 1.170731707317073) internal successors, (48), 44 states have internal predecessors, (48), 25 states have call successors, (25), 4 states have call predecessors, (25), 4 states have return successors, (24), 22 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-09 22:30:38,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 97 transitions. [2024-11-09 22:30:38,029 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 97 transitions. Word has length 26 [2024-11-09 22:30:38,029 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:30:38,029 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 97 transitions. [2024-11-09 22:30:38,029 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.533333333333333) internal successors, (38), 13 states have internal predecessors, (38), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 22:30:38,029 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 97 transitions. [2024-11-09 22:30:38,031 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-11-09 22:30:38,031 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:30:38,031 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:30:38,043 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-09 22:30:38,231 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-09 22:30:38,232 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:30:38,233 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:30:38,233 INFO L85 PathProgramCache]: Analyzing trace with hash 607497479, now seen corresponding path program 1 times [2024-11-09 22:30:38,233 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:30:38,233 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [711174526] [2024-11-09 22:30:38,233 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:38,233 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:30:38,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:30:38,260 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1728205281] [2024-11-09 22:30:38,262 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:38,263 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:30:38,263 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:30:38,267 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-09 22:30:38,268 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-09 22:30:38,300 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:38,301 INFO L255 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 22:30:38,303 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:30:38,351 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-09 22:30:38,351 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:30:38,352 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:30:38,352 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [711174526] [2024-11-09 22:30:38,352 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:30:38,352 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1728205281] [2024-11-09 22:30:38,353 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1728205281] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:30:38,353 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:30:38,353 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:30:38,353 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1968093911] [2024-11-09 22:30:38,353 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:30:38,353 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:30:38,353 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:30:38,354 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:30:38,354 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:30:38,354 INFO L87 Difference]: Start difference. First operand 71 states and 97 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-09 22:30:38,403 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:30:38,404 INFO L93 Difference]: Finished difference Result 97 states and 134 transitions. [2024-11-09 22:30:38,404 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:30:38,404 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 33 [2024-11-09 22:30:38,404 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:30:38,405 INFO L225 Difference]: With dead ends: 97 [2024-11-09 22:30:38,405 INFO L226 Difference]: Without dead ends: 93 [2024-11-09 22:30:38,406 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:30:38,406 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 5 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:30:38,406 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 141 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:30:38,407 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2024-11-09 22:30:38,420 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2024-11-09 22:30:38,421 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 49 states have (on average 1.163265306122449) internal successors, (57), 51 states have internal predecessors, (57), 37 states have call successors, (37), 6 states have call predecessors, (37), 6 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2024-11-09 22:30:38,422 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 129 transitions. [2024-11-09 22:30:38,422 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 129 transitions. Word has length 33 [2024-11-09 22:30:38,422 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:30:38,426 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 129 transitions. [2024-11-09 22:30:38,426 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-09 22:30:38,430 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 129 transitions. [2024-11-09 22:30:38,431 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-11-09 22:30:38,431 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:30:38,431 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:30:38,443 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-09 22:30:38,631 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-09 22:30:38,632 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:30:38,632 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:30:38,632 INFO L85 PathProgramCache]: Analyzing trace with hash -1281427681, now seen corresponding path program 1 times [2024-11-09 22:30:38,634 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:30:38,634 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [378972262] [2024-11-09 22:30:38,635 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:38,635 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:30:38,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:30:38,646 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [930538711] [2024-11-09 22:30:38,646 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:30:38,647 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:30:38,647 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:30:38,648 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-09 22:30:38,649 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-09 22:30:38,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:30:38,714 INFO L255 TraceCheckSpWp]: Trace formula consists of 82 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-09 22:30:38,715 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:30:38,802 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 22:30:38,802 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:30:40,787 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 22:30:40,787 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:30:40,787 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [378972262] [2024-11-09 22:30:40,787 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:30:40,788 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [930538711] [2024-11-09 22:30:40,788 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [930538711] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:30:40,788 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:30:40,788 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-11-09 22:30:40,788 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [410275477] [2024-11-09 22:30:40,788 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:30:40,788 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 22:30:40,789 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:30:40,789 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 22:30:40,789 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2024-11-09 22:30:40,789 INFO L87 Difference]: Start difference. First operand 93 states and 129 transitions. Second operand has 10 states, 10 states have (on average 3.6) internal successors, (36), 9 states have internal predecessors, (36), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 22:30:50,580 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:56,638 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:30:59,364 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.99s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:01,236 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.87s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:06,574 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:10,578 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:14,582 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:18,596 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:22,600 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:26,614 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:30,630 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:33,061 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.34s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:37,064 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:40,274 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.73s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:44,280 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:44,301 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:31:44,301 INFO L93 Difference]: Finished difference Result 168 states and 238 transitions. [2024-11-09 22:31:44,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-09 22:31:44,301 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.6) internal successors, (36), 9 states have internal predecessors, (36), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 34 [2024-11-09 22:31:44,302 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:31:44,303 INFO L225 Difference]: With dead ends: 168 [2024-11-09 22:31:44,303 INFO L226 Difference]: Without dead ends: 142 [2024-11-09 22:31:44,304 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 57 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 7.7s TimeCoverageRelationStatistics Valid=38, Invalid=93, Unknown=1, NotChecked=0, Total=132 [2024-11-09 22:31:44,304 INFO L432 NwaCegarLoop]: 60 mSDtfsCounter, 31 mSDsluCounter, 258 mSDsCounter, 0 mSdLazyCounter, 188 mSolverCounterSat, 70 mSolverCounterUnsat, 11 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 57.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 318 SdHoareTripleChecker+Invalid, 269 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 70 IncrementalHoareTripleChecker+Valid, 188 IncrementalHoareTripleChecker+Invalid, 11 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 57.7s IncrementalHoareTripleChecker+Time [2024-11-09 22:31:44,305 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 318 Invalid, 269 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [70 Valid, 188 Invalid, 11 Unknown, 0 Unchecked, 57.7s Time] [2024-11-09 22:31:44,305 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2024-11-09 22:31:44,345 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 136. [2024-11-09 22:31:44,346 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 71 states have (on average 1.1549295774647887) internal successors, (82), 74 states have internal predecessors, (82), 55 states have call successors, (55), 9 states have call predecessors, (55), 9 states have return successors, (53), 52 states have call predecessors, (53), 53 states have call successors, (53) [2024-11-09 22:31:44,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 190 transitions. [2024-11-09 22:31:44,347 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 190 transitions. Word has length 34 [2024-11-09 22:31:44,347 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:31:44,347 INFO L471 AbstractCegarLoop]: Abstraction has 136 states and 190 transitions. [2024-11-09 22:31:44,348 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.6) internal successors, (36), 9 states have internal predecessors, (36), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 22:31:44,348 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 190 transitions. [2024-11-09 22:31:44,349 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-09 22:31:44,349 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:31:44,349 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:31:44,365 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-09 22:31:44,549 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-09 22:31:44,550 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:31:44,550 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:31:44,550 INFO L85 PathProgramCache]: Analyzing trace with hash -1421249943, now seen corresponding path program 1 times [2024-11-09 22:31:44,550 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:31:44,550 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1564179659] [2024-11-09 22:31:44,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:31:44,550 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:31:44,571 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:31:44,572 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [989915371] [2024-11-09 22:31:44,572 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:31:44,572 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:31:44,572 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:31:44,579 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-09 22:31:44,580 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-09 22:31:44,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:31:44,628 INFO L255 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 22:31:44,629 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:31:44,790 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 24 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-09 22:31:44,791 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:31:44,791 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:31:44,791 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1564179659] [2024-11-09 22:31:44,791 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:31:44,791 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [989915371] [2024-11-09 22:31:44,791 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [989915371] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:31:44,791 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:31:44,791 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-11-09 22:31:44,792 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [540874510] [2024-11-09 22:31:44,792 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:31:44,792 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-09 22:31:44,792 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:31:44,792 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-09 22:31:44,792 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2024-11-09 22:31:44,793 INFO L87 Difference]: Start difference. First operand 136 states and 190 transitions. Second operand has 8 states, 8 states have (on average 3.375) internal successors, (27), 7 states have internal predecessors, (27), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-09 22:31:49,061 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-09 22:31:53,118 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:31:53,160 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:31:53,160 INFO L93 Difference]: Finished difference Result 151 states and 202 transitions. [2024-11-09 22:31:53,161 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-09 22:31:53,161 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 7 states have internal predecessors, (27), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 47 [2024-11-09 22:31:53,161 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:31:53,163 INFO L225 Difference]: With dead ends: 151 [2024-11-09 22:31:53,163 INFO L226 Difference]: Without dead ends: 148 [2024-11-09 22:31:53,164 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=49, Unknown=0, NotChecked=0, Total=72 [2024-11-09 22:31:53,164 INFO L432 NwaCegarLoop]: 69 mSDtfsCounter, 12 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 101 mSolverCounterSat, 7 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 243 SdHoareTripleChecker+Invalid, 110 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 101 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.3s IncrementalHoareTripleChecker+Time [2024-11-09 22:31:53,164 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 243 Invalid, 110 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 101 Invalid, 2 Unknown, 0 Unchecked, 8.3s Time] [2024-11-09 22:31:53,165 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 148 states. [2024-11-09 22:31:53,181 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 148 to 148. [2024-11-09 22:31:53,182 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 80 states have (on average 1.1375) internal successors, (91), 83 states have internal predecessors, (91), 55 states have call successors, (55), 12 states have call predecessors, (55), 12 states have return successors, (53), 52 states have call predecessors, (53), 53 states have call successors, (53) [2024-11-09 22:31:53,183 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 199 transitions. [2024-11-09 22:31:53,183 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 199 transitions. Word has length 47 [2024-11-09 22:31:53,184 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:31:53,184 INFO L471 AbstractCegarLoop]: Abstraction has 148 states and 199 transitions. [2024-11-09 22:31:53,184 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 7 states have internal predecessors, (27), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-09 22:31:53,184 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 199 transitions. [2024-11-09 22:31:53,185 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-11-09 22:31:53,185 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:31:53,186 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 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, 1, 1, 1, 1, 1, 1] [2024-11-09 22:31:53,200 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-09 22:31:53,386 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-09 22:31:53,386 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:31:53,386 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:31:53,387 INFO L85 PathProgramCache]: Analyzing trace with hash 530225078, now seen corresponding path program 1 times [2024-11-09 22:31:53,387 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:31:53,387 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1385803491] [2024-11-09 22:31:53,387 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:31:53,387 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:31:53,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:31:53,417 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1653073901] [2024-11-09 22:31:53,417 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:31:53,417 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:31:53,417 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:31:53,424 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-09 22:31:53,430 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-09 22:31:53,475 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:31:53,476 INFO L255 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 22:31:53,477 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:31:53,584 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2024-11-09 22:31:53,585 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:31:53,585 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:31:53,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1385803491] [2024-11-09 22:31:53,585 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:31:53,586 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1653073901] [2024-11-09 22:31:53,588 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1653073901] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:31:53,588 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:31:53,589 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:31:53,589 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1547544961] [2024-11-09 22:31:53,589 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:31:53,589 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:31:53,589 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:31:53,590 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:31:53,590 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:31:53,590 INFO L87 Difference]: Start difference. First operand 148 states and 199 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-09 22:31:53,717 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:31:53,718 INFO L93 Difference]: Finished difference Result 172 states and 231 transitions. [2024-11-09 22:31:53,718 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:31:53,718 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 59 [2024-11-09 22:31:53,719 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:31:53,721 INFO L225 Difference]: With dead ends: 172 [2024-11-09 22:31:53,721 INFO L226 Difference]: Without dead ends: 152 [2024-11-09 22:31:53,721 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 55 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:31:53,722 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 5 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:31:53,725 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 129 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:31:53,725 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2024-11-09 22:31:53,747 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 152. [2024-11-09 22:31:53,748 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 84 states have (on average 1.130952380952381) internal successors, (95), 87 states have internal predecessors, (95), 54 states have call successors, (54), 13 states have call predecessors, (54), 13 states have return successors, (52), 51 states have call predecessors, (52), 52 states have call successors, (52) [2024-11-09 22:31:53,751 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 201 transitions. [2024-11-09 22:31:53,751 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 201 transitions. Word has length 59 [2024-11-09 22:31:53,754 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:31:53,754 INFO L471 AbstractCegarLoop]: Abstraction has 152 states and 201 transitions. [2024-11-09 22:31:53,754 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-09 22:31:53,754 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 201 transitions. [2024-11-09 22:31:53,756 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-11-09 22:31:53,756 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:31:53,756 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:31:53,782 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-09 22:31:53,956 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-09 22:31:53,957 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:31:53,957 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:31:53,958 INFO L85 PathProgramCache]: Analyzing trace with hash 1426900463, now seen corresponding path program 1 times [2024-11-09 22:31:53,958 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:31:53,958 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [350288006] [2024-11-09 22:31:53,958 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:31:53,958 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:31:53,981 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:31:54,598 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 22:31:54,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:31:54,605 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 22:31:54,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:31:54,607 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-09 22:31:54,609 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:31:54,622 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-09 22:31:54,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:31:54,637 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-09 22:31:54,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:31:54,656 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-11-09 22:31:54,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:31:54,672 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-11-09 22:31:54,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:31:54,687 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-11-09 22:31:54,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:31:54,709 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2024-11-09 22:31:54,709 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:31:54,710 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [350288006] [2024-11-09 22:31:54,710 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [350288006] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:31:54,710 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [684492652] [2024-11-09 22:31:54,710 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:31:54,710 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:31:54,710 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:31:54,717 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-09 22:31:54,722 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-09 22:31:54,798 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:31:54,799 INFO L255 TraceCheckSpWp]: Trace formula consists of 136 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-09 22:31:54,801 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:31:56,985 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 23 proven. 13 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2024-11-09 22:31:56,985 INFO L311 TraceCheckSpWp]: Computing backward predicates...