./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps5-ll_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 84cfde4a Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps5-ll_unwindbound10.c -s /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-clean/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 1c50dd7e64abcc7a7eef6ea31e37156afb1e4322422284686cac6e6613b192c7 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-84cfde4 [2024-10-11 02:27:48,004 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-11 02:27:48,061 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-11 02:27:48,066 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-11 02:27:48,067 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-11 02:27:48,090 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-11 02:27:48,092 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-11 02:27:48,092 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-11 02:27:48,093 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-11 02:27:48,096 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-11 02:27:48,096 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-11 02:27:48,096 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-11 02:27:48,097 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-11 02:27:48,097 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-11 02:27:48,097 INFO L153 SettingsManager]: * Use SBE=true [2024-10-11 02:27:48,097 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-11 02:27:48,099 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-11 02:27:48,099 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-11 02:27:48,099 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-11 02:27:48,099 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-11 02:27:48,099 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-11 02:27:48,100 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-11 02:27:48,100 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-11 02:27:48,100 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-11 02:27:48,101 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-11 02:27:48,101 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-11 02:27:48,102 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-11 02:27:48,102 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-11 02:27:48,102 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-11 02:27:48,102 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-11 02:27:48,102 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-11 02:27:48,103 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-11 02:27:48,103 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-11 02:27:48,104 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-11 02:27:48,104 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-11 02:27:48,104 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-11 02:27:48,105 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-11 02:27:48,105 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-11 02:27:48,105 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-11 02:27:48,105 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-11 02:27:48,105 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-11 02:27:48,106 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-11 02:27:48,106 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-clean/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-clean/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 -> 1c50dd7e64abcc7a7eef6ea31e37156afb1e4322422284686cac6e6613b192c7 [2024-10-11 02:27:48,313 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-11 02:27:48,336 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-11 02:27:48,338 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-11 02:27:48,339 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-11 02:27:48,339 INFO L274 PluginConnector]: CDTParser initialized [2024-10-11 02:27:48,340 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps5-ll_unwindbound10.c [2024-10-11 02:27:49,588 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-11 02:27:49,750 INFO L384 CDTParser]: Found 1 translation units. [2024-10-11 02:27:49,751 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps5-ll_unwindbound10.c [2024-10-11 02:27:49,757 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/1873a2462/5728eb3d7e3d4954957536d251bf15b1/FLAG80e44647a [2024-10-11 02:27:50,160 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/1873a2462/5728eb3d7e3d4954957536d251bf15b1 [2024-10-11 02:27:50,163 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-11 02:27:50,164 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-11 02:27:50,166 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-11 02:27:50,166 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-11 02:27:50,174 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-11 02:27:50,174 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,175 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@486335f5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50, skipping insertion in model container [2024-10-11 02:27:50,176 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,193 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-11 02:27:50,329 WARN L248 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/ps5-ll_unwindbound10.c[458,471] [2024-10-11 02:27:50,345 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-11 02:27:50,352 INFO L200 MainTranslator]: Completed pre-run [2024-10-11 02:27:50,368 WARN L248 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/ps5-ll_unwindbound10.c[458,471] [2024-10-11 02:27:50,375 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-11 02:27:50,389 INFO L204 MainTranslator]: Completed translation [2024-10-11 02:27:50,390 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50 WrapperNode [2024-10-11 02:27:50,390 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-11 02:27:50,391 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-11 02:27:50,391 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-11 02:27:50,391 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-11 02:27:50,397 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,402 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,414 INFO L138 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 43 [2024-10-11 02:27:50,414 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-11 02:27:50,415 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-11 02:27:50,415 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-11 02:27:50,415 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-11 02:27:50,422 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,422 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,423 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,430 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-10-11 02:27:50,430 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,430 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,432 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,438 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,439 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,439 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,444 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-11 02:27:50,446 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-11 02:27:50,446 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-11 02:27:50,446 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-11 02:27:50,446 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50" (1/1) ... [2024-10-11 02:27:50,450 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-11 02:27:50,458 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:50,469 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-10-11 02:27:50,471 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-10-11 02:27:50,502 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-11 02:27:50,502 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-11 02:27:50,502 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-11 02:27:50,502 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-11 02:27:50,502 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-11 02:27:50,502 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-11 02:27:50,548 INFO L238 CfgBuilder]: Building ICFG [2024-10-11 02:27:50,550 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-11 02:27:50,637 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-10-11 02:27:50,637 INFO L287 CfgBuilder]: Performing block encoding [2024-10-11 02:27:50,653 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-11 02:27:50,653 INFO L314 CfgBuilder]: Removed 1 assume(true) statements. [2024-10-11 02:27:50,653 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.10 02:27:50 BoogieIcfgContainer [2024-10-11 02:27:50,654 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-11 02:27:50,655 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-11 02:27:50,655 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-11 02:27:50,660 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-11 02:27:50,660 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.10 02:27:50" (1/3) ... [2024-10-11 02:27:50,661 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@8721bba and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.10 02:27:50, skipping insertion in model container [2024-10-11 02:27:50,663 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:50" (2/3) ... [2024-10-11 02:27:50,664 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@8721bba and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.10 02:27:50, skipping insertion in model container [2024-10-11 02:27:50,664 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.10 02:27:50" (3/3) ... [2024-10-11 02:27:50,665 INFO L112 eAbstractionObserver]: Analyzing ICFG ps5-ll_unwindbound10.c [2024-10-11 02:27:50,677 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-11 02:27:50,677 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-11 02:27:50,716 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-11 02:27:50,721 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;@729d03f3, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-11 02:27:50,721 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-11 02:27:50,724 INFO L276 IsEmpty]: Start isEmpty. Operand has 17 states, 11 states have (on average 1.5454545454545454) internal successors, (17), 12 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-11 02:27:50,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-10-11 02:27:50,729 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:50,729 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:50,730 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:50,733 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:50,734 INFO L85 PathProgramCache]: Analyzing trace with hash 793793432, now seen corresponding path program 1 times [2024-10-11 02:27:50,740 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:50,741 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1042625972] [2024-10-11 02:27:50,741 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:50,742 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:50,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:50,892 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:50,892 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:50,892 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1042625972] [2024-10-11 02:27:50,893 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1042625972] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:27:50,893 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:27:50,893 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-11 02:27:50,895 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1905697842] [2024-10-11 02:27:50,895 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:27:50,899 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-11 02:27:50,900 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:50,918 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-11 02:27:50,919 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-11 02:27:50,921 INFO L87 Difference]: Start difference. First operand has 17 states, 11 states have (on average 1.5454545454545454) internal successors, (17), 12 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:27:50,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:50,946 INFO L93 Difference]: Finished difference Result 32 states and 46 transitions. [2024-10-11 02:27:50,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-11 02:27:50,948 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-10-11 02:27:50,948 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:50,954 INFO L225 Difference]: With dead ends: 32 [2024-10-11 02:27:50,955 INFO L226 Difference]: Without dead ends: 15 [2024-10-11 02:27:50,958 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-11 02:27:50,961 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 18 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:50,965 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 18 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:27:50,981 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2024-10-11 02:27:50,993 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2024-10-11 02:27:50,995 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:27:50,996 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 18 transitions. [2024-10-11 02:27:50,998 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 18 transitions. Word has length 8 [2024-10-11 02:27:50,999 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:50,999 INFO L471 AbstractCegarLoop]: Abstraction has 15 states and 18 transitions. [2024-10-11 02:27:50,999 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:27:50,999 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 18 transitions. [2024-10-11 02:27:50,999 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-10-11 02:27:51,000 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:51,000 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:51,000 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-11 02:27:51,000 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:51,001 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:51,001 INFO L85 PathProgramCache]: Analyzing trace with hash 1922989550, now seen corresponding path program 1 times [2024-10-11 02:27:51,001 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:51,002 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1648543176] [2024-10-11 02:27:51,002 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:51,002 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:51,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:51,117 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:51,118 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:51,118 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1648543176] [2024-10-11 02:27:51,121 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1648543176] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:27:51,122 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:27:51,123 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-10-11 02:27:51,123 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1242193021] [2024-10-11 02:27:51,125 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:27:51,126 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-11 02:27:51,126 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:51,127 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-11 02:27:51,127 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-11 02:27:51,127 INFO L87 Difference]: Start difference. First operand 15 states and 18 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:27:51,162 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:51,163 INFO L93 Difference]: Finished difference Result 25 states and 29 transitions. [2024-10-11 02:27:51,163 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-11 02:27:51,163 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-10-11 02:27:51,163 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:51,164 INFO L225 Difference]: With dead ends: 25 [2024-10-11 02:27:51,164 INFO L226 Difference]: Without dead ends: 17 [2024-10-11 02:27:51,164 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-11 02:27:51,165 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 0 mSDsluCounter, 27 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:51,165 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 42 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:27:51,166 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2024-10-11 02:27:51,169 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2024-10-11 02:27:51,169 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:27:51,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 20 transitions. [2024-10-11 02:27:51,169 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 20 transitions. Word has length 9 [2024-10-11 02:27:51,169 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:51,170 INFO L471 AbstractCegarLoop]: Abstraction has 17 states and 20 transitions. [2024-10-11 02:27:51,170 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:27:51,170 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 20 transitions. [2024-10-11 02:27:51,170 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-10-11 02:27:51,170 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:51,170 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:51,171 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-11 02:27:51,171 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:51,172 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:51,172 INFO L85 PathProgramCache]: Analyzing trace with hash 1924777010, now seen corresponding path program 1 times [2024-10-11 02:27:51,172 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:51,172 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1498878878] [2024-10-11 02:27:51,172 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:51,172 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:51,197 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:27:51,202 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1123509409] [2024-10-11 02:27:51,203 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:51,203 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:51,204 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:51,205 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:51,206 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-10-11 02:27:51,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:51,261 INFO L255 TraceCheckSpWp]: Trace formula consists of 48 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-11 02:27:51,266 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:51,362 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:51,362 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-11 02:27:51,363 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:51,363 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1498878878] [2024-10-11 02:27:51,363 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:27:51,363 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1123509409] [2024-10-11 02:27:51,363 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1123509409] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:27:51,363 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:27:51,363 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-11 02:27:51,364 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1897136743] [2024-10-11 02:27:51,364 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:27:51,364 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:27:51,365 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:51,366 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:27:51,366 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-11 02:27:51,366 INFO L87 Difference]: Start difference. First operand 17 states and 20 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:27:51,414 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:51,415 INFO L93 Difference]: Finished difference Result 27 states and 32 transitions. [2024-10-11 02:27:51,415 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:27:51,415 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-10-11 02:27:51,415 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:51,416 INFO L225 Difference]: With dead ends: 27 [2024-10-11 02:27:51,416 INFO L226 Difference]: Without dead ends: 23 [2024-10-11 02:27:51,416 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 5 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-10-11 02:27:51,417 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 4 mSDsluCounter, 38 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 52 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:51,418 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 52 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:27:51,418 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2024-10-11 02:27:51,422 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2024-10-11 02:27:51,422 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 16 states have (on average 1.1875) internal successors, (19), 17 states have internal predecessors, (19), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-11 02:27:51,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 26 transitions. [2024-10-11 02:27:51,423 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 26 transitions. Word has length 9 [2024-10-11 02:27:51,423 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:51,423 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 26 transitions. [2024-10-11 02:27:51,423 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:27:51,424 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 26 transitions. [2024-10-11 02:27:51,424 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-10-11 02:27:51,424 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:51,424 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:51,437 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-11 02:27:51,628 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:51,629 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:51,629 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:51,630 INFO L85 PathProgramCache]: Analyzing trace with hash 76913492, now seen corresponding path program 1 times [2024-10-11 02:27:51,630 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:51,630 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1564983833] [2024-10-11 02:27:51,630 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:51,630 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:51,648 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:51,738 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-11 02:27:51,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:51,753 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:51,753 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:51,753 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1564983833] [2024-10-11 02:27:51,753 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1564983833] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:27:51,754 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [115543889] [2024-10-11 02:27:51,754 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:51,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:51,754 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:51,755 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:51,756 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-10-11 02:27:51,798 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:51,798 INFO L255 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-10-11 02:27:51,799 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:51,830 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:51,830 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:51,869 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:51,870 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [115543889] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:27:51,870 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:27:51,870 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-10-11 02:27:51,870 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1270216748] [2024-10-11 02:27:51,870 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:27:51,871 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-10-11 02:27:51,871 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:51,872 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-10-11 02:27:51,872 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-10-11 02:27:51,872 INFO L87 Difference]: Start difference. First operand 23 states and 26 transitions. Second operand has 10 states, 10 states have (on average 3.0) internal successors, (30), 10 states have internal predecessors, (30), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-11 02:27:51,944 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:51,944 INFO L93 Difference]: Finished difference Result 57 states and 67 transitions. [2024-10-11 02:27:51,945 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-11 02:27:51,945 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.0) internal successors, (30), 10 states have internal predecessors, (30), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 17 [2024-10-11 02:27:51,945 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:51,946 INFO L225 Difference]: With dead ends: 57 [2024-10-11 02:27:51,946 INFO L226 Difference]: Without dead ends: 49 [2024-10-11 02:27:51,947 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2024-10-11 02:27:51,948 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 29 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:51,948 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 75 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:27:51,949 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-10-11 02:27:51,959 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 45. [2024-10-11 02:27:51,960 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 33 states have internal predecessors, (37), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-11 02:27:51,961 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 54 transitions. [2024-10-11 02:27:51,962 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 54 transitions. Word has length 17 [2024-10-11 02:27:51,962 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:51,962 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 54 transitions. [2024-10-11 02:27:51,963 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.0) internal successors, (30), 10 states have internal predecessors, (30), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-11 02:27:51,963 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 54 transitions. [2024-10-11 02:27:51,963 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-10-11 02:27:51,964 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:51,964 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:51,978 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-10-11 02:27:52,164 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:52,165 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:52,165 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:52,165 INFO L85 PathProgramCache]: Analyzing trace with hash 78700952, now seen corresponding path program 1 times [2024-10-11 02:27:52,165 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:52,165 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [346949079] [2024-10-11 02:27:52,166 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:52,166 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:52,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:27:52,181 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [634196124] [2024-10-11 02:27:52,182 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:52,182 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:52,182 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:52,183 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:52,184 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-10-11 02:27:52,223 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,224 INFO L255 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-11 02:27:52,225 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:52,296 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:52,297 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:52,392 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-10-11 02:27:52,393 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:52,393 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [346949079] [2024-10-11 02:27:52,393 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:27:52,393 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [634196124] [2024-10-11 02:27:52,393 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [634196124] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-11 02:27:52,393 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-11 02:27:52,394 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-10-11 02:27:52,394 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1551323289] [2024-10-11 02:27:52,394 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:27:52,396 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:27:52,396 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:52,396 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:27:52,397 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-10-11 02:27:52,397 INFO L87 Difference]: Start difference. First operand 45 states and 54 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-11 02:27:52,439 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:52,439 INFO L93 Difference]: Finished difference Result 59 states and 67 transitions. [2024-10-11 02:27:52,439 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:27:52,440 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 17 [2024-10-11 02:27:52,440 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:52,441 INFO L225 Difference]: With dead ends: 59 [2024-10-11 02:27:52,441 INFO L226 Difference]: Without dead ends: 51 [2024-10-11 02:27:52,441 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 25 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-10-11 02:27:52,442 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 5 mSDsluCounter, 28 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:52,442 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 40 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:27:52,443 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2024-10-11 02:27:52,453 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 45. [2024-10-11 02:27:52,454 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 32 states have (on average 1.125) internal successors, (36), 34 states have internal predecessors, (36), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-11 02:27:52,455 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 51 transitions. [2024-10-11 02:27:52,455 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 51 transitions. Word has length 17 [2024-10-11 02:27:52,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:52,455 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 51 transitions. [2024-10-11 02:27:52,455 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-11 02:27:52,456 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 51 transitions. [2024-10-11 02:27:52,457 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-10-11 02:27:52,457 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:52,457 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:52,470 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-10-11 02:27:52,661 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:52,662 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:52,662 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:52,663 INFO L85 PathProgramCache]: Analyzing trace with hash 731759343, now seen corresponding path program 1 times [2024-10-11 02:27:52,663 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:52,663 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [866220275] [2024-10-11 02:27:52,663 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:52,663 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:52,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:27:52,683 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [883900976] [2024-10-11 02:27:52,683 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:52,683 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:52,683 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:52,685 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:52,686 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-10-11 02:27:52,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,723 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-11 02:27:52,724 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:52,805 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-10-11 02:27:52,806 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:52,904 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-10-11 02:27:52,904 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:52,904 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [866220275] [2024-10-11 02:27:52,905 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:27:52,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [883900976] [2024-10-11 02:27:52,905 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [883900976] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:27:52,905 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:27:52,905 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-10-11 02:27:52,905 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [113588925] [2024-10-11 02:27:52,905 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:27:52,906 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-10-11 02:27:52,906 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:52,906 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-10-11 02:27:52,906 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2024-10-11 02:27:52,906 INFO L87 Difference]: Start difference. First operand 45 states and 51 transitions. Second operand has 10 states, 8 states have (on average 2.75) internal successors, (22), 9 states have internal predecessors, (22), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-11 02:27:52,998 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:52,998 INFO L93 Difference]: Finished difference Result 54 states and 62 transitions. [2024-10-11 02:27:52,998 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-11 02:27:52,998 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.75) internal successors, (22), 9 states have internal predecessors, (22), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 28 [2024-10-11 02:27:52,999 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:52,999 INFO L225 Difference]: With dead ends: 54 [2024-10-11 02:27:52,999 INFO L226 Difference]: Without dead ends: 45 [2024-10-11 02:27:53,000 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 44 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2024-10-11 02:27:53,001 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 1 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 53 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:53,002 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 98 Invalid, 53 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:27:53,003 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-10-11 02:27:53,013 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2024-10-11 02:27:53,014 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 33 states have (on average 1.0606060606060606) internal successors, (35), 33 states have internal predecessors, (35), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-11 02:27:53,015 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 48 transitions. [2024-10-11 02:27:53,016 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 48 transitions. Word has length 28 [2024-10-11 02:27:53,017 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:53,017 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 48 transitions. [2024-10-11 02:27:53,017 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.75) internal successors, (22), 9 states have internal predecessors, (22), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-11 02:27:53,017 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 48 transitions. [2024-10-11 02:27:53,018 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-10-11 02:27:53,018 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:53,018 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:53,035 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-11 02:27:53,218 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-10-11 02:27:53,219 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:53,219 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:53,219 INFO L85 PathProgramCache]: Analyzing trace with hash -1074423298, now seen corresponding path program 1 times [2024-10-11 02:27:53,219 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:53,219 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [57642532] [2024-10-11 02:27:53,219 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:53,219 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:53,238 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:53,426 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-11 02:27:53,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:53,431 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-10-11 02:27:53,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:53,434 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-10-11 02:27:53,435 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:53,437 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-11 02:27:53,438 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:53,441 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-11 02:27:53,441 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:53,443 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-10-11 02:27:53,443 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:53,443 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [57642532] [2024-10-11 02:27:53,443 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [57642532] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:27:53,443 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1220811598] [2024-10-11 02:27:53,444 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:53,444 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:53,444 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:53,445 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:53,448 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-10-11 02:27:53,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:53,497 INFO L255 TraceCheckSpWp]: Trace formula consists of 141 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-11 02:27:53,498 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:53,560 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 24 proven. 56 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-10-11 02:27:53,560 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:53,676 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-10-11 02:27:53,678 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1220811598] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:27:53,678 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:27:53,678 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-10-11 02:27:53,678 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [230326758] [2024-10-11 02:27:53,678 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:27:53,679 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-11 02:27:53,680 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:53,680 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-11 02:27:53,680 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=144, Unknown=0, NotChecked=0, Total=240 [2024-10-11 02:27:53,681 INFO L87 Difference]: Start difference. First operand 45 states and 48 transitions. Second operand has 16 states, 16 states have (on average 3.6875) internal successors, (59), 16 states have internal predecessors, (59), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) [2024-10-11 02:27:53,878 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:53,878 INFO L93 Difference]: Finished difference Result 131 states and 143 transitions. [2024-10-11 02:27:53,878 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-10-11 02:27:53,878 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.6875) internal successors, (59), 16 states have internal predecessors, (59), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) Word has length 46 [2024-10-11 02:27:53,879 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:53,880 INFO L225 Difference]: With dead ends: 131 [2024-10-11 02:27:53,880 INFO L226 Difference]: Without dead ends: 121 [2024-10-11 02:27:53,881 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 94 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=196, Invalid=356, Unknown=0, NotChecked=0, Total=552 [2024-10-11 02:27:53,881 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 71 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 71 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 87 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:53,881 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [71 Valid, 111 Invalid, 87 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:27:53,882 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2024-10-11 02:27:53,908 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 96. [2024-10-11 02:27:53,908 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 68 states have (on average 1.1029411764705883) internal successors, (75), 73 states have internal predecessors, (75), 17 states have call successors, (17), 11 states have call predecessors, (17), 10 states have return successors, (16), 11 states have call predecessors, (16), 16 states have call successors, (16) [2024-10-11 02:27:53,911 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 108 transitions. [2024-10-11 02:27:53,911 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 108 transitions. Word has length 46 [2024-10-11 02:27:53,912 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:53,912 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 108 transitions. [2024-10-11 02:27:53,912 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.6875) internal successors, (59), 16 states have internal predecessors, (59), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) [2024-10-11 02:27:53,915 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 108 transitions. [2024-10-11 02:27:53,916 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-10-11 02:27:53,916 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:53,916 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:53,931 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-10-11 02:27:54,116 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:54,117 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:54,117 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:54,117 INFO L85 PathProgramCache]: Analyzing trace with hash -1441866883, now seen corresponding path program 2 times [2024-10-11 02:27:54,117 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:54,117 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2108898963] [2024-10-11 02:27:54,118 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:54,118 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:54,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:27:54,166 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [934399235] [2024-10-11 02:27:54,166 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-11 02:27:54,166 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:54,166 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:54,168 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:54,169 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-10-11 02:27:54,217 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-11 02:27:54,218 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 02:27:54,224 INFO L255 TraceCheckSpWp]: Trace formula consists of 151 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-10-11 02:27:54,225 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:54,425 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 12 proven. 40 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-10-11 02:27:54,426 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:54,683 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 12 proven. 40 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-10-11 02:27:54,683 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:54,684 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2108898963] [2024-10-11 02:27:54,684 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:27:54,684 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [934399235] [2024-10-11 02:27:54,684 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [934399235] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:27:54,684 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:27:54,684 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 20 [2024-10-11 02:27:54,684 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1094839229] [2024-10-11 02:27:54,685 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:27:54,685 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-10-11 02:27:54,685 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:54,685 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-10-11 02:27:54,687 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=313, Unknown=0, NotChecked=0, Total=380 [2024-10-11 02:27:54,687 INFO L87 Difference]: Start difference. First operand 96 states and 108 transitions. Second operand has 20 states, 18 states have (on average 2.4444444444444446) internal successors, (44), 18 states have internal predecessors, (44), 12 states have call successors, (14), 3 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-10-11 02:27:55,044 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:55,044 INFO L93 Difference]: Finished difference Result 102 states and 113 transitions. [2024-10-11 02:27:55,044 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-10-11 02:27:55,045 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 2.4444444444444446) internal successors, (44), 18 states have internal predecessors, (44), 12 states have call successors, (14), 3 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Word has length 52 [2024-10-11 02:27:55,045 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:55,046 INFO L225 Difference]: With dead ends: 102 [2024-10-11 02:27:55,048 INFO L226 Difference]: Without dead ends: 91 [2024-10-11 02:27:55,048 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 133 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=167, Invalid=703, Unknown=0, NotChecked=0, Total=870 [2024-10-11 02:27:55,049 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 23 mSDsluCounter, 318 mSDsCounter, 0 mSdLazyCounter, 200 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 348 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 200 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:55,049 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 348 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 200 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:27:55,049 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2024-10-11 02:27:55,068 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 91. [2024-10-11 02:27:55,069 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 68 states have (on average 1.0294117647058822) internal successors, (70), 68 states have internal predecessors, (70), 12 states have call successors, (12), 11 states have call predecessors, (12), 10 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-10-11 02:27:55,070 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 93 transitions. [2024-10-11 02:27:55,070 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 93 transitions. Word has length 52 [2024-10-11 02:27:55,071 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:55,071 INFO L471 AbstractCegarLoop]: Abstraction has 91 states and 93 transitions. [2024-10-11 02:27:55,071 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 2.4444444444444446) internal successors, (44), 18 states have internal predecessors, (44), 12 states have call successors, (14), 3 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-10-11 02:27:55,071 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 93 transitions. [2024-10-11 02:27:55,072 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2024-10-11 02:27:55,073 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:55,073 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:55,086 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-10-11 02:27:55,277 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-10-11 02:27:55,278 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:55,278 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:55,278 INFO L85 PathProgramCache]: Analyzing trace with hash -1566715457, now seen corresponding path program 3 times [2024-10-11 02:27:55,278 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:55,278 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [5534996] [2024-10-11 02:27:55,278 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:55,279 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:55,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:27:55,321 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [121678064] [2024-10-11 02:27:55,321 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-11 02:27:55,322 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:55,322 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:55,323 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:55,324 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process