./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound10.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 9f971bd1a6fba471cdece6d295ca31488341eb806ea8364f7549d05755c7a031 --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-08 14:36:09,197 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-08 14:36:09,232 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-08 14:36:09,235 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-08 14:36:09,236 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-08 14:36:09,261 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-08 14:36:09,261 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-08 14:36:09,263 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-08 14:36:09,263 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-08 14:36:09,263 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-08 14:36:09,263 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-08 14:36:09,264 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-08 14:36:09,264 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-08 14:36:09,264 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-08 14:36:09,264 INFO L153 SettingsManager]: * Use SBE=true [2024-11-08 14:36:09,265 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-08 14:36:09,265 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-08 14:36:09,265 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-08 14:36:09,265 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-08 14:36:09,266 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-08 14:36:09,266 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-08 14:36:09,268 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-08 14:36:09,269 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-08 14:36:09,269 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-08 14:36:09,270 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-08 14:36:09,272 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-08 14:36:09,272 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-08 14:36:09,272 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-08 14:36:09,273 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-08 14:36:09,273 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-08 14:36:09,273 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-08 14:36:09,273 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-08 14:36:09,273 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:36:09,273 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-08 14:36:09,273 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-08 14:36:09,274 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-08 14:36:09,274 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-08 14:36:09,274 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-08 14:36:09,274 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-08 14:36:09,275 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-08 14:36:09,275 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-08 14:36:09,275 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-08 14:36:09,276 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 9f971bd1a6fba471cdece6d295ca31488341eb806ea8364f7549d05755c7a031 [2024-11-08 14:36:09,503 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-08 14:36:09,520 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-08 14:36:09,523 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-08 14:36:09,524 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-08 14:36:09,524 INFO L274 PluginConnector]: CDTParser initialized [2024-11-08 14:36:09,525 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound10.c [2024-11-08 14:36:10,738 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-08 14:36:10,964 INFO L384 CDTParser]: Found 1 translation units. [2024-11-08 14:36:10,965 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound10.c [2024-11-08 14:36:10,972 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1acf3caaf/8078d79c7d8c4b70a6b6204e86c19e1e/FLAG750505ecf [2024-11-08 14:36:11,330 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1acf3caaf/8078d79c7d8c4b70a6b6204e86c19e1e [2024-11-08 14:36:11,332 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-08 14:36:11,333 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-08 14:36:11,334 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-08 14:36:11,334 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-08 14:36:11,337 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-08 14:36:11,338 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,339 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@30635e7b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11, skipping insertion in model container [2024-11-08 14:36:11,339 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,360 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-08 14:36:11,484 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound10.c[526,539] [2024-11-08 14:36:11,495 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:36:11,502 INFO L200 MainTranslator]: Completed pre-run [2024-11-08 14:36:11,511 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_unwindbound10.c[526,539] [2024-11-08 14:36:11,522 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:36:11,534 INFO L204 MainTranslator]: Completed translation [2024-11-08 14:36:11,535 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11 WrapperNode [2024-11-08 14:36:11,535 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-08 14:36:11,536 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-08 14:36:11,536 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-08 14:36:11,536 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-08 14:36:11,541 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,546 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,564 INFO L138 Inliner]: procedures = 14, calls = 22, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 69 [2024-11-08 14:36:11,565 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-08 14:36:11,566 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-08 14:36:11,566 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-08 14:36:11,566 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-08 14:36:11,577 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,577 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,582 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,594 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2024-11-08 14:36:11,598 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,598 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,601 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,604 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,606 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,607 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,612 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-08 14:36:11,612 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-08 14:36:11,612 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-08 14:36:11,612 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-08 14:36:11,613 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11" (1/1) ... [2024-11-08 14:36:11,618 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:36:11,629 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:36:11,647 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-08 14:36:11,655 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-08 14:36:11,685 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-08 14:36:11,685 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-08 14:36:11,685 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-08 14:36:11,685 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-08 14:36:11,685 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-08 14:36:11,685 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-08 14:36:11,686 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-08 14:36:11,731 INFO L238 CfgBuilder]: Building ICFG [2024-11-08 14:36:11,733 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-08 14:36:11,823 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-08 14:36:11,823 INFO L287 CfgBuilder]: Performing block encoding [2024-11-08 14:36:11,839 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-08 14:36:11,839 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-08 14:36:11,839 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:36:11 BoogieIcfgContainer [2024-11-08 14:36:11,839 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-08 14:36:11,841 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-08 14:36:11,841 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-08 14:36:11,846 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-08 14:36:11,846 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.11 02:36:11" (1/3) ... [2024-11-08 14:36:11,847 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2fe5bb84 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:36:11, skipping insertion in model container [2024-11-08 14:36:11,848 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:36:11" (2/3) ... [2024-11-08 14:36:11,848 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2fe5bb84 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:36:11, skipping insertion in model container [2024-11-08 14:36:11,848 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:36:11" (3/3) ... [2024-11-08 14:36:11,850 INFO L112 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound10.c [2024-11-08 14:36:11,862 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-08 14:36:11,863 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-08 14:36:11,915 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-08 14:36:11,920 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;@7b18b3bd, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-08 14:36:11,924 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-08 14:36:11,929 INFO L276 IsEmpty]: Start isEmpty. Operand has 26 states, 16 states have (on average 1.5625) internal successors, (25), 17 states have internal predecessors, (25), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 14:36:11,935 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-11-08 14:36:11,935 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:11,935 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:11,937 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:11,940 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:11,940 INFO L85 PathProgramCache]: Analyzing trace with hash 643118537, now seen corresponding path program 1 times [2024-11-08 14:36:11,949 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:11,949 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [188318520] [2024-11-08 14:36:11,949 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:11,950 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:12,018 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:12,058 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-08 14:36:12,059 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:12,059 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [188318520] [2024-11-08 14:36:12,060 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [188318520] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:36:12,060 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:36:12,060 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-08 14:36:12,061 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [46541711] [2024-11-08 14:36:12,062 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:36:12,064 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-08 14:36:12,065 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:12,080 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-08 14:36:12,081 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 14:36:12,082 INFO L87 Difference]: Start difference. First operand has 26 states, 16 states have (on average 1.5625) internal successors, (25), 17 states have internal predecessors, (25), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) 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-11-08 14:36:12,098 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:12,098 INFO L93 Difference]: Finished difference Result 50 states and 83 transitions. [2024-11-08 14:36:12,099 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-08 14:36:12,100 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-11-08 14:36:12,100 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:12,105 INFO L225 Difference]: With dead ends: 50 [2024-11-08 14:36:12,105 INFO L226 Difference]: Without dead ends: 22 [2024-11-08 14:36:12,107 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 14:36:12,109 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 36 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:12,110 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:36:12,122 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2024-11-08 14:36:12,133 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2024-11-08 14:36:12,134 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 14 states have internal predecessors, (19), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 14:36:12,135 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 32 transitions. [2024-11-08 14:36:12,136 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 32 transitions. Word has length 8 [2024-11-08 14:36:12,137 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:12,137 INFO L471 AbstractCegarLoop]: Abstraction has 22 states and 32 transitions. [2024-11-08 14:36:12,137 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-11-08 14:36:12,137 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 32 transitions. [2024-11-08 14:36:12,137 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-11-08 14:36:12,138 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:12,138 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:12,138 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-08 14:36:12,138 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:12,139 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:12,139 INFO L85 PathProgramCache]: Analyzing trace with hash 181060127, now seen corresponding path program 1 times [2024-11-08 14:36:12,139 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:12,139 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [202324557] [2024-11-08 14:36:12,139 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:12,139 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:12,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:12,250 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-08 14:36:12,251 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:12,251 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [202324557] [2024-11-08 14:36:12,251 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [202324557] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:36:12,251 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:36:12,251 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:36:12,251 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [614626201] [2024-11-08 14:36:12,252 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:36:12,252 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:36:12,253 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:12,253 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:36:12,253 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:36:12,257 INFO L87 Difference]: Start difference. First operand 22 states and 32 transitions. Second operand has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 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-11-08 14:36:12,315 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:12,315 INFO L93 Difference]: Finished difference Result 36 states and 51 transitions. [2024-11-08 14:36:12,316 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:36:12,316 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 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-11-08 14:36:12,316 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:12,317 INFO L225 Difference]: With dead ends: 36 [2024-11-08 14:36:12,318 INFO L226 Difference]: Without dead ends: 34 [2024-11-08 14:36:12,318 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:36:12,320 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 12 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:12,320 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 97 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:36:12,321 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2024-11-08 14:36:12,329 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 26. [2024-11-08 14:36:12,330 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 14:36:12,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 35 transitions. [2024-11-08 14:36:12,332 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 35 transitions. Word has length 8 [2024-11-08 14:36:12,332 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:12,332 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 35 transitions. [2024-11-08 14:36:12,333 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.4) internal successors, (7), 4 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-11-08 14:36:12,333 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 35 transitions. [2024-11-08 14:36:12,333 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-08 14:36:12,334 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:12,334 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:12,334 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-08 14:36:12,335 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:12,335 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:12,335 INFO L85 PathProgramCache]: Analyzing trace with hash -712280900, now seen corresponding path program 1 times [2024-11-08 14:36:12,337 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:12,337 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1785249775] [2024-11-08 14:36:12,337 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:12,337 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:12,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:12,415 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-08 14:36:12,416 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:12,416 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1785249775] [2024-11-08 14:36:12,416 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1785249775] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:36:12,416 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:36:12,416 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-08 14:36:12,416 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [395045638] [2024-11-08 14:36:12,417 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:36:12,417 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-08 14:36:12,417 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:12,417 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-08 14:36:12,418 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-08 14:36:12,418 INFO L87 Difference]: Start difference. First operand 26 states and 35 transitions. Second operand has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-08 14:36:12,430 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:12,431 INFO L93 Difference]: Finished difference Result 42 states and 57 transitions. [2024-11-08 14:36:12,431 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-08 14:36:12,431 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2024-11-08 14:36:12,431 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:12,432 INFO L225 Difference]: With dead ends: 42 [2024-11-08 14:36:12,432 INFO L226 Difference]: Without dead ends: 28 [2024-11-08 14:36:12,433 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-08 14:36:12,433 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 0 mSDsluCounter, 55 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:12,434 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 85 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:36:12,434 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2024-11-08 14:36:12,438 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2024-11-08 14:36:12,438 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 14:36:12,438 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2024-11-08 14:36:12,439 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 10 [2024-11-08 14:36:12,439 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:12,439 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2024-11-08 14:36:12,439 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-08 14:36:12,439 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2024-11-08 14:36:12,440 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-08 14:36:12,440 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:12,440 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:12,440 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-08 14:36:12,440 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:12,441 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:12,441 INFO L85 PathProgramCache]: Analyzing trace with hash 2036073049, now seen corresponding path program 1 times [2024-11-08 14:36:12,441 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:12,441 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1594095634] [2024-11-08 14:36:12,441 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:12,441 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:12,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:12,521 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-08 14:36:12,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:12,530 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-08 14:36:12,530 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:12,531 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1594095634] [2024-11-08 14:36:12,531 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1594095634] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:36:12,531 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:36:12,531 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:36:12,531 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1228870185] [2024-11-08 14:36:12,531 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:36:12,532 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:36:12,532 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:12,533 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:36:12,533 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:36:12,534 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-08 14:36:12,594 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:12,594 INFO L93 Difference]: Finished difference Result 42 states and 56 transitions. [2024-11-08 14:36:12,594 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:36:12,595 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 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 13 [2024-11-08 14:36:12,595 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:12,596 INFO L225 Difference]: With dead ends: 42 [2024-11-08 14:36:12,597 INFO L226 Difference]: Without dead ends: 40 [2024-11-08 14:36:12,597 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:36:12,601 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 12 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:12,602 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 94 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:36:12,602 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2024-11-08 14:36:12,606 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 32. [2024-11-08 14:36:12,609 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 14:36:12,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 40 transitions. [2024-11-08 14:36:12,613 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 40 transitions. Word has length 13 [2024-11-08 14:36:12,613 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:12,613 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 40 transitions. [2024-11-08 14:36:12,613 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-08 14:36:12,614 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 40 transitions. [2024-11-08 14:36:12,614 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-08 14:36:12,614 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:12,614 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:12,615 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-08 14:36:12,615 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:12,615 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:12,616 INFO L85 PathProgramCache]: Analyzing trace with hash 380169759, now seen corresponding path program 1 times [2024-11-08 14:36:12,616 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:12,616 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1639822668] [2024-11-08 14:36:12,616 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:12,616 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:12,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:36:12,638 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1825563034] [2024-11-08 14:36:12,640 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:12,641 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:12,641 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:36:12,647 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:36:12,648 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-08 14:36:12,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:12,704 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-08 14:36:12,709 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:36:12,843 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:36:12,843 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:36:12,843 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:12,843 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1639822668] [2024-11-08 14:36:12,844 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:36:12,844 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1825563034] [2024-11-08 14:36:12,844 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1825563034] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:36:12,844 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:36:12,844 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:36:12,844 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2091158607] [2024-11-08 14:36:12,844 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:36:12,844 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:36:12,844 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:12,845 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:36:12,845 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:36:12,845 INFO L87 Difference]: Start difference. First operand 32 states and 40 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:36:12,900 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:12,900 INFO L93 Difference]: Finished difference Result 61 states and 83 transitions. [2024-11-08 14:36:12,901 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:36:12,901 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2024-11-08 14:36:12,901 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:12,901 INFO L225 Difference]: With dead ends: 61 [2024-11-08 14:36:12,901 INFO L226 Difference]: Without dead ends: 46 [2024-11-08 14:36:12,902 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:36:12,902 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 7 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:12,902 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 98 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:36:12,903 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-08 14:36:12,914 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2024-11-08 14:36:12,914 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 28 states have (on average 1.2857142857142858) internal successors, (36), 30 states have internal predecessors, (36), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-08 14:36:12,915 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 60 transitions. [2024-11-08 14:36:12,915 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 60 transitions. Word has length 18 [2024-11-08 14:36:12,916 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:12,916 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 60 transitions. [2024-11-08 14:36:12,916 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:36:12,917 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 60 transitions. [2024-11-08 14:36:12,917 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-11-08 14:36:12,917 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:12,917 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:12,930 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-08 14:36:13,121 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:13,122 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:13,122 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:13,123 INFO L85 PathProgramCache]: Analyzing trace with hash -461064832, now seen corresponding path program 1 times [2024-11-08 14:36:13,123 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:13,123 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1265764747] [2024-11-08 14:36:13,123 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:13,123 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:13,138 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:36:13,142 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2028209570] [2024-11-08 14:36:13,142 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:13,142 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:13,143 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:36:13,144 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:36:13,147 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-08 14:36:13,198 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:13,199 INFO L255 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-08 14:36:13,201 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:36:13,287 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-08 14:36:13,287 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:36:13,414 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-08 14:36:13,414 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:13,414 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1265764747] [2024-11-08 14:36:13,415 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:36:13,415 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2028209570] [2024-11-08 14:36:13,415 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2028209570] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:36:13,415 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:36:13,415 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-11-08 14:36:13,415 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [830979674] [2024-11-08 14:36:13,415 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:36:13,415 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-08 14:36:13,416 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:13,416 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-08 14:36:13,416 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-11-08 14:36:13,416 INFO L87 Difference]: Start difference. First operand 46 states and 60 transitions. Second operand has 10 states, 10 states have (on average 2.3) internal successors, (23), 9 states have internal predecessors, (23), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-08 14:36:13,491 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:13,491 INFO L93 Difference]: Finished difference Result 60 states and 79 transitions. [2024-11-08 14:36:13,491 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-08 14:36:13,491 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.3) internal successors, (23), 9 states have internal predecessors, (23), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 26 [2024-11-08 14:36:13,491 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:13,492 INFO L225 Difference]: With dead ends: 60 [2024-11-08 14:36:13,492 INFO L226 Difference]: Without dead ends: 57 [2024-11-08 14:36:13,493 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 41 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2024-11-08 14:36:13,493 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 9 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 111 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 114 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 111 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:13,493 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 122 Invalid, 114 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 111 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:36:13,494 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2024-11-08 14:36:13,499 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 56. [2024-11-08 14:36:13,499 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 35 states have (on average 1.2857142857142858) internal successors, (45), 37 states have internal predecessors, (45), 15 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-08 14:36:13,500 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 74 transitions. [2024-11-08 14:36:13,500 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 74 transitions. Word has length 26 [2024-11-08 14:36:13,500 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:13,500 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 74 transitions. [2024-11-08 14:36:13,500 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.3) internal successors, (23), 9 states have internal predecessors, (23), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-08 14:36:13,501 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 74 transitions. [2024-11-08 14:36:13,501 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-11-08 14:36:13,501 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:13,501 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:13,514 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-08 14:36:13,705 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-11-08 14:36:13,706 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:13,707 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:13,707 INFO L85 PathProgramCache]: Analyzing trace with hash -909290541, now seen corresponding path program 1 times [2024-11-08 14:36:13,707 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:13,707 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1524508466] [2024-11-08 14:36:13,707 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:13,707 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:13,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:13,775 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-08 14:36:13,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:13,781 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-08 14:36:13,786 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:13,788 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-08 14:36:13,793 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:13,796 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-08 14:36:13,800 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:13,801 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 14:36:13,802 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:13,802 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1524508466] [2024-11-08 14:36:13,802 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1524508466] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:36:13,802 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2008876811] [2024-11-08 14:36:13,802 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:13,803 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:13,803 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:36:13,805 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:36:13,808 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-08 14:36:13,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:13,848 INFO L255 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-08 14:36:13,850 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:36:13,883 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-08 14:36:13,884 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:36:13,928 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 14:36:13,928 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2008876811] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:36:13,928 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:36:13,929 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-11-08 14:36:13,929 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [825253837] [2024-11-08 14:36:13,929 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:36:13,929 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-08 14:36:13,929 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:13,930 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-08 14:36:13,930 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-11-08 14:36:13,930 INFO L87 Difference]: Start difference. First operand 56 states and 74 transitions. Second operand has 10 states, 10 states have (on average 3.1) internal successors, (31), 10 states have internal predecessors, (31), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-08 14:36:14,053 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:14,053 INFO L93 Difference]: Finished difference Result 155 states and 190 transitions. [2024-11-08 14:36:14,053 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-08 14:36:14,053 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.1) internal successors, (31), 10 states have internal predecessors, (31), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 33 [2024-11-08 14:36:14,054 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:14,055 INFO L225 Difference]: With dead ends: 155 [2024-11-08 14:36:14,056 INFO L226 Difference]: Without dead ends: 130 [2024-11-08 14:36:14,056 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2024-11-08 14:36:14,060 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 56 mSDsluCounter, 139 mSDsCounter, 0 mSdLazyCounter, 100 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 170 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 100 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:14,061 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 170 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 100 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:36:14,061 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2024-11-08 14:36:14,081 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 123. [2024-11-08 14:36:14,081 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 79 states have (on average 1.2025316455696202) internal successors, (95), 83 states have internal predecessors, (95), 27 states have call successors, (27), 16 states have call predecessors, (27), 16 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-08 14:36:14,082 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 146 transitions. [2024-11-08 14:36:14,083 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 146 transitions. Word has length 33 [2024-11-08 14:36:14,083 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:14,083 INFO L471 AbstractCegarLoop]: Abstraction has 123 states and 146 transitions. [2024-11-08 14:36:14,083 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.1) internal successors, (31), 10 states have internal predecessors, (31), 3 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-08 14:36:14,083 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 146 transitions. [2024-11-08 14:36:14,102 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-08 14:36:14,103 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:14,103 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:14,115 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-08 14:36:14,303 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:14,304 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:14,305 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:14,305 INFO L85 PathProgramCache]: Analyzing trace with hash 252591112, now seen corresponding path program 1 times [2024-11-08 14:36:14,306 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:14,306 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1665075017] [2024-11-08 14:36:14,306 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:14,306 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:14,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:36:14,315 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1867329434] [2024-11-08 14:36:14,315 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:14,316 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:14,316 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:36:14,317 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:36:14,318 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-08 14:36:14,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:14,360 INFO L255 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-08 14:36:14,361 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:36:14,435 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-08 14:36:14,435 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:36:14,486 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-08 14:36:14,487 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:14,487 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1665075017] [2024-11-08 14:36:14,487 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:36:14,487 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1867329434] [2024-11-08 14:36:14,487 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1867329434] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-08 14:36:14,487 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:36:14,487 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-08 14:36:14,488 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [914177971] [2024-11-08 14:36:14,488 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:36:14,488 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:36:14,488 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:14,489 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:36:14,489 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-08 14:36:14,489 INFO L87 Difference]: Start difference. First operand 123 states and 146 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-08 14:36:15,982 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.45s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:36:15,994 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:15,994 INFO L93 Difference]: Finished difference Result 146 states and 174 transitions. [2024-11-08 14:36:15,997 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:36:15,997 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 36 [2024-11-08 14:36:15,998 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:15,998 INFO L225 Difference]: With dead ends: 146 [2024-11-08 14:36:15,998 INFO L226 Difference]: Without dead ends: 140 [2024-11-08 14:36:15,999 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 63 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-08 14:36:15,999 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 8 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:15,999 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 92 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2024-11-08 14:36:16,000 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2024-11-08 14:36:16,025 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 132. [2024-11-08 14:36:16,027 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 132 states, 86 states have (on average 1.1744186046511629) internal successors, (101), 90 states have internal predecessors, (101), 28 states have call successors, (28), 18 states have call predecessors, (28), 17 states have return successors, (26), 23 states have call predecessors, (26), 26 states have call successors, (26) [2024-11-08 14:36:16,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 155 transitions. [2024-11-08 14:36:16,030 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 155 transitions. Word has length 36 [2024-11-08 14:36:16,030 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:16,030 INFO L471 AbstractCegarLoop]: Abstraction has 132 states and 155 transitions. [2024-11-08 14:36:16,030 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-08 14:36:16,030 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 155 transitions. [2024-11-08 14:36:16,031 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-11-08 14:36:16,031 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:16,031 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:16,046 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-08 14:36:16,232 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:16,232 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:16,233 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:16,233 INFO L85 PathProgramCache]: Analyzing trace with hash 1776130969, now seen corresponding path program 1 times [2024-11-08 14:36:16,233 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:16,233 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1631269946] [2024-11-08 14:36:16,233 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:16,233 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:16,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,302 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-08 14:36:16,303 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,304 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-08 14:36:16,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,307 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-08 14:36:16,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,309 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-11-08 14:36:16,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,311 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-11-08 14:36:16,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,313 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-11-08 14:36:16,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,315 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-08 14:36:16,315 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:16,315 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1631269946] [2024-11-08 14:36:16,316 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1631269946] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:36:16,316 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:36:16,316 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:36:16,316 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [486761099] [2024-11-08 14:36:16,316 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:36:16,316 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:36:16,316 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:16,316 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:36:16,316 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:36:16,316 INFO L87 Difference]: Start difference. First operand 132 states and 155 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-08 14:36:16,346 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:16,346 INFO L93 Difference]: Finished difference Result 137 states and 159 transitions. [2024-11-08 14:36:16,346 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:36:16,346 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 42 [2024-11-08 14:36:16,347 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:16,347 INFO L225 Difference]: With dead ends: 137 [2024-11-08 14:36:16,347 INFO L226 Difference]: Without dead ends: 118 [2024-11-08 14:36:16,348 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:36:16,348 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 1 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:16,348 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 111 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:36:16,349 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2024-11-08 14:36:16,361 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 118. [2024-11-08 14:36:16,364 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 77 states have (on average 1.1818181818181819) internal successors, (91), 80 states have internal predecessors, (91), 25 states have call successors, (25), 16 states have call predecessors, (25), 15 states have return successors, (23), 21 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-08 14:36:16,365 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 139 transitions. [2024-11-08 14:36:16,365 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 139 transitions. Word has length 42 [2024-11-08 14:36:16,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:16,365 INFO L471 AbstractCegarLoop]: Abstraction has 118 states and 139 transitions. [2024-11-08 14:36:16,365 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-08 14:36:16,365 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 139 transitions. [2024-11-08 14:36:16,367 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-08 14:36:16,368 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:16,368 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:16,369 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2024-11-08 14:36:16,369 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:16,369 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:16,369 INFO L85 PathProgramCache]: Analyzing trace with hash 1605675221, now seen corresponding path program 1 times [2024-11-08 14:36:16,369 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:16,370 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [833583181] [2024-11-08 14:36:16,370 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:16,370 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:16,379 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,455 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-08 14:36:16,457 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,458 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-08 14:36:16,461 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,462 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-08 14:36:16,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,467 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-11-08 14:36:16,468 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,471 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-11-08 14:36:16,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,474 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-11-08 14:36:16,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,478 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 40 [2024-11-08 14:36:16,480 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,482 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-08 14:36:16,483 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:16,484 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [833583181] [2024-11-08 14:36:16,484 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [833583181] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:36:16,484 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [80229804] [2024-11-08 14:36:16,484 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:16,488 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:16,488 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:36:16,489 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:36:16,492 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-08 14:36:16,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:16,538 INFO L255 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-08 14:36:16,539 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:36:16,613 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 36 proven. 42 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-08 14:36:16,613 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:36:16,702 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-08 14:36:16,703 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [80229804] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:36:16,703 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:36:16,703 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 12 [2024-11-08 14:36:16,703 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [196982887] [2024-11-08 14:36:16,703 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:36:16,704 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-08 14:36:16,705 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:16,706 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-08 14:36:16,706 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2024-11-08 14:36:16,706 INFO L87 Difference]: Start difference. First operand 118 states and 139 transitions. Second operand has 12 states, 12 states have (on average 3.1666666666666665) internal successors, (38), 12 states have internal predecessors, (38), 5 states have call successors, (21), 4 states have call predecessors, (21), 4 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) [2024-11-08 14:36:16,880 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:16,880 INFO L93 Difference]: Finished difference Result 241 states and 294 transitions. [2024-11-08 14:36:16,881 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-08 14:36:16,881 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.1666666666666665) internal successors, (38), 12 states have internal predecessors, (38), 5 states have call successors, (21), 4 states have call predecessors, (21), 4 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) Word has length 49 [2024-11-08 14:36:16,881 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:16,882 INFO L225 Difference]: With dead ends: 241 [2024-11-08 14:36:16,883 INFO L226 Difference]: Without dead ends: 220 [2024-11-08 14:36:16,883 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 106 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=67, Invalid=143, Unknown=0, NotChecked=0, Total=210 [2024-11-08 14:36:16,883 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 85 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 111 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 85 SdHoareTripleChecker+Valid, 190 SdHoareTripleChecker+Invalid, 135 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 111 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:16,884 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [85 Valid, 190 Invalid, 135 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 111 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:36:16,884 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states. [2024-11-08 14:36:16,907 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 213. [2024-11-08 14:36:16,908 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 213 states, 138 states have (on average 1.1956521739130435) internal successors, (165), 147 states have internal predecessors, (165), 49 states have call successors, (49), 26 states have call predecessors, (49), 25 states have return successors, (45), 39 states have call predecessors, (45), 45 states have call successors, (45) [2024-11-08 14:36:16,909 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 259 transitions. [2024-11-08 14:36:16,910 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 259 transitions. Word has length 49 [2024-11-08 14:36:16,910 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:16,910 INFO L471 AbstractCegarLoop]: Abstraction has 213 states and 259 transitions. [2024-11-08 14:36:16,910 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.1666666666666665) internal successors, (38), 12 states have internal predecessors, (38), 5 states have call successors, (21), 4 states have call predecessors, (21), 4 states have return successors, (20), 5 states have call predecessors, (20), 5 states have call successors, (20) [2024-11-08 14:36:16,910 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 259 transitions. [2024-11-08 14:36:16,911 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2024-11-08 14:36:16,911 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:16,911 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:16,925 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-08 14:36:17,112 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-08 14:36:17,113 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:17,113 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:17,113 INFO L85 PathProgramCache]: Analyzing trace with hash -1800695307, now seen corresponding path program 1 times [2024-11-08 14:36:17,113 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:17,113 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [899077502] [2024-11-08 14:36:17,114 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:17,114 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:17,136 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:36:17,137 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [677549393] [2024-11-08 14:36:17,137 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:17,137 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:17,138 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:36:17,139 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:36:17,140 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-08 14:36:17,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:17,181 INFO L255 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-08 14:36:17,183 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:36:17,392 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 18 proven. 28 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-08 14:36:17,392 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:36:18,611 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 18 proven. 28 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-08 14:36:18,611 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:18,611 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [899077502] [2024-11-08 14:36:18,612 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:36:18,612 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [677549393] [2024-11-08 14:36:18,613 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [677549393] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:36:18,613 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:36:18,613 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2024-11-08 14:36:18,613 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [746442511] [2024-11-08 14:36:18,613 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:36:18,613 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-08 14:36:18,613 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:18,614 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-08 14:36:18,616 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2024-11-08 14:36:18,616 INFO L87 Difference]: Start difference. First operand 213 states and 259 transitions. Second operand has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 14 states have internal predecessors, (40), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-08 14:36:19,226 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:19,227 INFO L93 Difference]: Finished difference Result 359 states and 460 transitions. [2024-11-08 14:36:19,227 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-08 14:36:19,227 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 14 states have internal predecessors, (40), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 58 [2024-11-08 14:36:19,227 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:19,229 INFO L225 Difference]: With dead ends: 359 [2024-11-08 14:36:19,229 INFO L226 Difference]: Without dead ends: 298 [2024-11-08 14:36:19,230 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=76, Invalid=266, Unknown=0, NotChecked=0, Total=342 [2024-11-08 14:36:19,230 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 53 mSDsluCounter, 234 mSDsCounter, 0 mSdLazyCounter, 299 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 274 SdHoareTripleChecker+Invalid, 367 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 299 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:19,230 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 274 Invalid, 367 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 299 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-08 14:36:19,231 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 298 states. [2024-11-08 14:36:19,265 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 298 to 272. [2024-11-08 14:36:19,265 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 272 states, 185 states have (on average 1.227027027027027) internal successors, (227), 192 states have internal predecessors, (227), 57 states have call successors, (57), 29 states have call predecessors, (57), 29 states have return successors, (55), 50 states have call predecessors, (55), 55 states have call successors, (55) [2024-11-08 14:36:19,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 272 states to 272 states and 339 transitions. [2024-11-08 14:36:19,267 INFO L78 Accepts]: Start accepts. Automaton has 272 states and 339 transitions. Word has length 58 [2024-11-08 14:36:19,267 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:19,267 INFO L471 AbstractCegarLoop]: Abstraction has 272 states and 339 transitions. [2024-11-08 14:36:19,267 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 14 states have internal predecessors, (40), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-08 14:36:19,267 INFO L276 IsEmpty]: Start isEmpty. Operand 272 states and 339 transitions. [2024-11-08 14:36:19,268 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2024-11-08 14:36:19,268 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:19,268 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:19,281 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-08 14:36:19,472 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:19,473 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:19,473 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:19,473 INFO L85 PathProgramCache]: Analyzing trace with hash -1688778742, now seen corresponding path program 1 times [2024-11-08 14:36:19,474 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:19,474 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [832083157] [2024-11-08 14:36:19,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:19,474 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:19,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:36:19,491 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [198805735] [2024-11-08 14:36:19,491 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:19,491 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:19,491 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:36:19,492 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:36:19,493 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-08 14:36:19,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:19,545 INFO L255 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-08 14:36:19,548 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:36:19,736 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 22 proven. 36 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-08 14:36:19,736 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:36:20,172 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 22 proven. 36 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-08 14:36:20,173 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:20,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [832083157] [2024-11-08 14:36:20,173 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:36:20,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [198805735] [2024-11-08 14:36:20,173 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [198805735] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:36:20,173 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:36:20,173 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2024-11-08 14:36:20,173 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1489081082] [2024-11-08 14:36:20,173 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:36:20,174 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-08 14:36:20,174 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:20,175 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-08 14:36:20,175 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=187, Unknown=0, NotChecked=0, Total=240 [2024-11-08 14:36:20,175 INFO L87 Difference]: Start difference. First operand 272 states and 339 transitions. Second operand has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2024-11-08 14:36:20,606 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:20,606 INFO L93 Difference]: Finished difference Result 337 states and 420 transitions. [2024-11-08 14:36:20,606 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-08 14:36:20,606 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) Word has length 69 [2024-11-08 14:36:20,607 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:20,608 INFO L225 Difference]: With dead ends: 337 [2024-11-08 14:36:20,608 INFO L226 Difference]: Without dead ends: 269 [2024-11-08 14:36:20,608 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 122 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=79, Invalid=263, Unknown=0, NotChecked=0, Total=342 [2024-11-08 14:36:20,609 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 23 mSDsluCounter, 218 mSDsCounter, 0 mSdLazyCounter, 288 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 253 SdHoareTripleChecker+Invalid, 311 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 288 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:20,609 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 253 Invalid, 311 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 288 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-08 14:36:20,609 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 269 states. [2024-11-08 14:36:20,637 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 269 to 243. [2024-11-08 14:36:20,637 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 243 states, 166 states have (on average 1.180722891566265) internal successors, (196), 171 states have internal predecessors, (196), 47 states have call successors, (47), 30 states have call predecessors, (47), 29 states have return successors, (45), 41 states have call predecessors, (45), 45 states have call successors, (45) [2024-11-08 14:36:20,638 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 288 transitions. [2024-11-08 14:36:20,638 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 288 transitions. Word has length 69 [2024-11-08 14:36:20,638 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:20,639 INFO L471 AbstractCegarLoop]: Abstraction has 243 states and 288 transitions. [2024-11-08 14:36:20,639 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 3.0) internal successors, (42), 15 states have internal predecessors, (42), 8 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2024-11-08 14:36:20,639 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 288 transitions. [2024-11-08 14:36:20,639 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-08 14:36:20,639 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:20,639 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:20,655 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-08 14:36:20,840 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:20,840 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:20,840 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:20,840 INFO L85 PathProgramCache]: Analyzing trace with hash -428937714, now seen corresponding path program 1 times [2024-11-08 14:36:20,840 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:20,840 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1801761290] [2024-11-08 14:36:20,841 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:20,841 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:20,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:21,064 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-08 14:36:21,066 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:21,069 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-08 14:36:21,069 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:21,071 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-08 14:36:21,072 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:21,074 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-11-08 14:36:21,075 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:21,080 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-11-08 14:36:21,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:21,086 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-11-08 14:36:21,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:21,096 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 40 [2024-11-08 14:36:21,097 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:21,101 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 45 [2024-11-08 14:36:21,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:21,106 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-11-08 14:36:21,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:21,110 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-11-08 14:36:21,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:21,113 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-08 14:36:21,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:21,116 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-08 14:36:21,116 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:21,116 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1801761290] [2024-11-08 14:36:21,116 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1801761290] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:36:21,116 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [625719389] [2024-11-08 14:36:21,116 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:21,116 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:21,117 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:36:21,119 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:36:21,120 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-08 14:36:21,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:21,165 INFO L255 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-08 14:36:21,167 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:36:21,304 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-08 14:36:21,305 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:36:21,585 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-08 14:36:21,586 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [625719389] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:36:21,586 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:36:21,586 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 7] total 14 [2024-11-08 14:36:21,586 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1924003265] [2024-11-08 14:36:21,586 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:36:21,586 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-08 14:36:21,586 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:21,587 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-08 14:36:21,587 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2024-11-08 14:36:21,587 INFO L87 Difference]: Start difference. First operand 243 states and 288 transitions. Second operand has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 12 states have internal predecessors, (51), 8 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 8 states have call predecessors, (32), 8 states have call successors, (32) [2024-11-08 14:36:21,770 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:21,770 INFO L93 Difference]: Finished difference Result 281 states and 329 transitions. [2024-11-08 14:36:21,771 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-08 14:36:21,771 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 12 states have internal predecessors, (51), 8 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 8 states have call predecessors, (32), 8 states have call successors, (32) Word has length 74 [2024-11-08 14:36:21,771 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:21,772 INFO L225 Difference]: With dead ends: 281 [2024-11-08 14:36:21,772 INFO L226 Difference]: Without dead ends: 215 [2024-11-08 14:36:21,773 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 180 GetRequests, 162 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 51 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=67, Invalid=239, Unknown=0, NotChecked=0, Total=306 [2024-11-08 14:36:21,773 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 12 mSDsluCounter, 208 mSDsCounter, 0 mSdLazyCounter, 146 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 157 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 146 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:21,773 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 249 Invalid, 157 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 146 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:36:21,774 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2024-11-08 14:36:21,814 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 210. [2024-11-08 14:36:21,815 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 210 states, 144 states have (on average 1.1527777777777777) internal successors, (166), 147 states have internal predecessors, (166), 40 states have call successors, (40), 25 states have call predecessors, (40), 25 states have return successors, (39), 37 states have call predecessors, (39), 39 states have call successors, (39) [2024-11-08 14:36:21,816 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 210 states to 210 states and 245 transitions. [2024-11-08 14:36:21,816 INFO L78 Accepts]: Start accepts. Automaton has 210 states and 245 transitions. Word has length 74 [2024-11-08 14:36:21,816 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:21,816 INFO L471 AbstractCegarLoop]: Abstraction has 210 states and 245 transitions. [2024-11-08 14:36:21,816 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 12 states have internal predecessors, (51), 8 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 8 states have call predecessors, (32), 8 states have call successors, (32) [2024-11-08 14:36:21,816 INFO L276 IsEmpty]: Start isEmpty. Operand 210 states and 245 transitions. [2024-11-08 14:36:21,817 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-11-08 14:36:21,817 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:21,817 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-11-08 14:36:21,829 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-08 14:36:22,021 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-08 14:36:22,022 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:22,023 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:22,023 INFO L85 PathProgramCache]: Analyzing trace with hash 1611798954, now seen corresponding path program 2 times [2024-11-08 14:36:22,023 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:22,024 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1941246985] [2024-11-08 14:36:22,024 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:22,024 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:22,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:36:22,045 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1663189737] [2024-11-08 14:36:22,046 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:36:22,046 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:22,046 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:36:22,047 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:36:22,048 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-08 14:36:22,095 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:36:22,096 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:36:22,097 INFO L255 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 48 conjuncts are in the unsatisfiable core [2024-11-08 14:36:22,099 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:36:22,467 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 28 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-08 14:36:22,468 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:36:38,845 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 28 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-08 14:36:38,846 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:38,846 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1941246985] [2024-11-08 14:36:38,846 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:36:38,846 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1663189737] [2024-11-08 14:36:38,846 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1663189737] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:36:38,846 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:36:38,846 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 25 [2024-11-08 14:36:38,846 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [410677101] [2024-11-08 14:36:38,847 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:36:38,847 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-08 14:36:38,847 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:38,848 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-08 14:36:38,848 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=493, Unknown=0, NotChecked=0, Total=600 [2024-11-08 14:36:38,848 INFO L87 Difference]: Start difference. First operand 210 states and 245 transitions. Second operand has 25 states, 25 states have (on average 2.16) internal successors, (54), 23 states have internal predecessors, (54), 13 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 11 states have call predecessors, (26), 11 states have call successors, (26) [2024-11-08 14:36:52,235 WARN L286 SmtUtils]: Spent 9.93s on a formula simplification. DAG size of input: 223 DAG size of output: 125 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-08 14:36:53,116 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:53,117 INFO L93 Difference]: Finished difference Result 319 states and 404 transitions. [2024-11-08 14:36:53,117 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-08 14:36:53,117 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 2.16) internal successors, (54), 23 states have internal predecessors, (54), 13 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 11 states have call predecessors, (26), 11 states have call successors, (26) Word has length 90 [2024-11-08 14:36:53,117 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:53,119 INFO L225 Difference]: With dead ends: 319 [2024-11-08 14:36:53,119 INFO L226 Difference]: Without dead ends: 283 [2024-11-08 14:36:53,119 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 195 GetRequests, 155 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 245 ImplicationChecksByTransitivity, 14.9s TimeCoverageRelationStatistics Valid=359, Invalid=1363, Unknown=0, NotChecked=0, Total=1722 [2024-11-08 14:36:53,120 INFO L432 NwaCegarLoop]: 55 mSDtfsCounter, 74 mSDsluCounter, 532 mSDsCounter, 0 mSdLazyCounter, 676 mSolverCounterSat, 146 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 76 SdHoareTripleChecker+Valid, 587 SdHoareTripleChecker+Invalid, 822 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 146 IncrementalHoareTripleChecker+Valid, 676 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:53,120 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [76 Valid, 587 Invalid, 822 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [146 Valid, 676 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2024-11-08 14:36:53,120 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 283 states. [2024-11-08 14:36:53,161 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 283 to 245. [2024-11-08 14:36:53,162 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 245 states, 167 states have (on average 1.1736526946107784) internal successors, (196), 171 states have internal predecessors, (196), 49 states have call successors, (49), 28 states have call predecessors, (49), 28 states have return successors, (48), 45 states have call predecessors, (48), 48 states have call successors, (48) [2024-11-08 14:36:53,163 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 245 states to 245 states and 293 transitions. [2024-11-08 14:36:53,163 INFO L78 Accepts]: Start accepts. Automaton has 245 states and 293 transitions. Word has length 90 [2024-11-08 14:36:53,163 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:53,163 INFO L471 AbstractCegarLoop]: Abstraction has 245 states and 293 transitions. [2024-11-08 14:36:53,164 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 2.16) internal successors, (54), 23 states have internal predecessors, (54), 13 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 11 states have call predecessors, (26), 11 states have call successors, (26) [2024-11-08 14:36:53,164 INFO L276 IsEmpty]: Start isEmpty. Operand 245 states and 293 transitions. [2024-11-08 14:36:53,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2024-11-08 14:36:53,164 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:53,164 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-11-08 14:36:53,177 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-08 14:36:53,368 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-08 14:36:53,369 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:53,369 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:53,369 INFO L85 PathProgramCache]: Analyzing trace with hash -1147408146, now seen corresponding path program 3 times [2024-11-08 14:36:53,369 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:53,369 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1256571467] [2024-11-08 14:36:53,369 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:53,370 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:53,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:36:53,401 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1511373894] [2024-11-08 14:36:53,401 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 14:36:53,401 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:53,401 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:36:53,403 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:36:53,404 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-08 14:36:53,447 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-08 14:36:53,447 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:36:53,448 INFO L255 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-08 14:36:53,450 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:36:53,554 INFO L134 CoverageAnalysis]: Checked inductivity of 424 backedges. 81 proven. 41 refuted. 0 times theorem prover too weak. 302 trivial. 0 not checked. [2024-11-08 14:36:53,555 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:36:54,305 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:54,305 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1256571467] [2024-11-08 14:36:54,305 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:36:54,305 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1511373894] [2024-11-08 14:36:54,306 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1511373894] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:36:54,306 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:36:54,306 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2024-11-08 14:36:54,306 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [66150799] [2024-11-08 14:36:54,306 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 14:36:54,306 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-08 14:36:54,306 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:54,307 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-08 14:36:54,307 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2024-11-08 14:36:54,307 INFO L87 Difference]: Start difference. First operand 245 states and 293 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-08 14:36:54,452 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:54,452 INFO L93 Difference]: Finished difference Result 268 states and 314 transitions. [2024-11-08 14:36:54,453 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-08 14:36:54,453 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 95 [2024-11-08 14:36:54,453 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:54,455 INFO L225 Difference]: With dead ends: 268 [2024-11-08 14:36:54,455 INFO L226 Difference]: Without dead ends: 266 [2024-11-08 14:36:54,455 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2024-11-08 14:36:54,455 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 20 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 108 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 108 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:54,455 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 111 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 108 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:36:54,456 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 266 states. [2024-11-08 14:36:54,503 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 266 to 261. [2024-11-08 14:36:54,504 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 261 states, 179 states have (on average 1.1620111731843576) internal successors, (208), 183 states have internal predecessors, (208), 49 states have call successors, (49), 32 states have call predecessors, (49), 32 states have return successors, (48), 45 states have call predecessors, (48), 48 states have call successors, (48) [2024-11-08 14:36:54,505 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 261 states to 261 states and 305 transitions. [2024-11-08 14:36:54,505 INFO L78 Accepts]: Start accepts. Automaton has 261 states and 305 transitions. Word has length 95 [2024-11-08 14:36:54,505 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:54,506 INFO L471 AbstractCegarLoop]: Abstraction has 261 states and 305 transitions. [2024-11-08 14:36:54,506 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-08 14:36:54,506 INFO L276 IsEmpty]: Start isEmpty. Operand 261 states and 305 transitions. [2024-11-08 14:36:54,506 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2024-11-08 14:36:54,507 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:54,507 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 5, 4, 4, 4, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:54,523 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-08 14:36:54,708 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-08 14:36:54,709 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:54,709 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:54,709 INFO L85 PathProgramCache]: Analyzing trace with hash 1991126182, now seen corresponding path program 1 times [2024-11-08 14:36:54,710 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:54,710 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [181569242] [2024-11-08 14:36:54,710 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:54,710 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:54,720 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,830 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-08 14:36:54,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,834 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-08 14:36:54,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,836 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-08 14:36:54,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,840 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-11-08 14:36:54,841 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,842 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-11-08 14:36:54,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,843 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-11-08 14:36:54,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,847 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 40 [2024-11-08 14:36:54,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,850 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 45 [2024-11-08 14:36:54,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,852 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 50 [2024-11-08 14:36:54,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,856 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 58 [2024-11-08 14:36:54,857 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,858 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2024-11-08 14:36:54,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,859 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 68 [2024-11-08 14:36:54,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,861 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-11-08 14:36:54,862 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,862 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-11-08 14:36:54,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,864 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 28 proven. 44 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2024-11-08 14:36:54,864 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:54,864 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [181569242] [2024-11-08 14:36:54,865 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [181569242] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:36:54,865 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1109540682] [2024-11-08 14:36:54,865 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:54,865 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:54,865 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:36:54,866 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:36:54,868 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-08 14:36:54,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:36:54,916 INFO L255 TraceCheckSpWp]: Trace formula consists of 251 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-08 14:36:54,918 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:36:54,992 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 120 proven. 260 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2024-11-08 14:36:54,993 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:36:55,105 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 28 proven. 44 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2024-11-08 14:36:55,105 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1109540682] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:36:55,105 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:36:55,106 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-11-08 14:36:55,106 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1486447485] [2024-11-08 14:36:55,106 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:36:55,106 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-08 14:36:55,106 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:55,107 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-08 14:36:55,108 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=144, Unknown=0, NotChecked=0, Total=240 [2024-11-08 14:36:55,108 INFO L87 Difference]: Start difference. First operand 261 states and 305 transitions. Second operand has 16 states, 16 states have (on average 3.8125) internal successors, (61), 16 states have internal predecessors, (61), 9 states have call successors, (41), 6 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) [2024-11-08 14:36:55,473 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:36:55,473 INFO L93 Difference]: Finished difference Result 720 states and 884 transitions. [2024-11-08 14:36:55,473 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-08 14:36:55,473 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.8125) internal successors, (61), 16 states have internal predecessors, (61), 9 states have call successors, (41), 6 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) Word has length 96 [2024-11-08 14:36:55,474 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:36:55,477 INFO L225 Difference]: With dead ends: 720 [2024-11-08 14:36:55,477 INFO L226 Difference]: Without dead ends: 650 [2024-11-08 14:36:55,477 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 234 GetRequests, 212 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-11-08 14:36:55,478 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 166 mSDsluCounter, 184 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 166 SdHoareTripleChecker+Valid, 213 SdHoareTripleChecker+Invalid, 202 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-08 14:36:55,478 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [166 Valid, 213 Invalid, 202 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-08 14:36:55,478 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 650 states. [2024-11-08 14:36:55,613 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 650 to 562. [2024-11-08 14:36:55,614 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 562 states, 376 states have (on average 1.2074468085106382) internal successors, (454), 394 states have internal predecessors, (454), 116 states have call successors, (116), 69 states have call predecessors, (116), 69 states have return successors, (112), 98 states have call predecessors, (112), 112 states have call successors, (112) [2024-11-08 14:36:55,616 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 562 states to 562 states and 682 transitions. [2024-11-08 14:36:55,616 INFO L78 Accepts]: Start accepts. Automaton has 562 states and 682 transitions. Word has length 96 [2024-11-08 14:36:55,616 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:36:55,616 INFO L471 AbstractCegarLoop]: Abstraction has 562 states and 682 transitions. [2024-11-08 14:36:55,617 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.8125) internal successors, (61), 16 states have internal predecessors, (61), 9 states have call successors, (41), 6 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) [2024-11-08 14:36:55,617 INFO L276 IsEmpty]: Start isEmpty. Operand 562 states and 682 transitions. [2024-11-08 14:36:55,617 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-08 14:36:55,618 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:36:55,618 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:36:55,631 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-08 14:36:55,821 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-08 14:36:55,822 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:36:55,822 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:36:55,822 INFO L85 PathProgramCache]: Analyzing trace with hash -218084043, now seen corresponding path program 2 times [2024-11-08 14:36:55,822 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:36:55,822 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1918767143] [2024-11-08 14:36:55,822 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:36:55,822 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:36:55,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:36:55,848 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1519436647] [2024-11-08 14:36:55,848 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:36:55,848 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:36:55,848 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:36:55,851 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:36:55,859 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-08 14:36:55,911 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:36:55,912 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:36:55,913 INFO L255 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 54 conjuncts are in the unsatisfiable core [2024-11-08 14:36:55,914 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:36:56,303 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 32 proven. 74 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2024-11-08 14:36:56,303 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:36:58,535 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 32 proven. 74 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2024-11-08 14:36:58,535 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:36:58,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1918767143] [2024-11-08 14:36:58,536 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:36:58,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1519436647] [2024-11-08 14:36:58,536 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1519436647] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:36:58,536 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:36:58,536 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 27 [2024-11-08 14:36:58,536 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [788371275] [2024-11-08 14:36:58,536 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:36:58,537 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-08 14:36:58,537 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:36:58,537 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-08 14:36:58,537 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=157, Invalid=545, Unknown=0, NotChecked=0, Total=702 [2024-11-08 14:36:58,538 INFO L87 Difference]: Start difference. First operand 562 states and 682 transitions. Second operand has 27 states, 25 states have (on average 2.24) internal successors, (56), 25 states have internal predecessors, (56), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) [2024-11-08 14:37:01,865 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:37:01,866 INFO L93 Difference]: Finished difference Result 732 states and 907 transitions. [2024-11-08 14:37:01,866 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-08 14:37:01,866 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 25 states have (on average 2.24) internal successors, (56), 25 states have internal predecessors, (56), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) Word has length 101 [2024-11-08 14:37:01,867 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:37:01,869 INFO L225 Difference]: With dead ends: 732 [2024-11-08 14:37:01,870 INFO L226 Difference]: Without dead ends: 555 [2024-11-08 14:37:01,871 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 209 GetRequests, 175 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 190 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=313, Invalid=947, Unknown=0, NotChecked=0, Total=1260 [2024-11-08 14:37:01,871 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 85 mSDsluCounter, 365 mSDsCounter, 0 mSdLazyCounter, 469 mSolverCounterSat, 97 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 89 SdHoareTripleChecker+Valid, 411 SdHoareTripleChecker+Invalid, 566 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 97 IncrementalHoareTripleChecker+Valid, 469 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2024-11-08 14:37:01,871 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [89 Valid, 411 Invalid, 566 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [97 Valid, 469 Invalid, 0 Unknown, 0 Unchecked, 1.6s Time] [2024-11-08 14:37:01,872 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 555 states. [2024-11-08 14:37:02,006 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 555 to 490. [2024-11-08 14:37:02,007 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 490 states, 328 states have (on average 1.1829268292682926) internal successors, (388), 341 states have internal predecessors, (388), 98 states have call successors, (98), 64 states have call predecessors, (98), 63 states have return successors, (94), 84 states have call predecessors, (94), 94 states have call successors, (94) [2024-11-08 14:37:02,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 490 states to 490 states and 580 transitions. [2024-11-08 14:37:02,009 INFO L78 Accepts]: Start accepts. Automaton has 490 states and 580 transitions. Word has length 101 [2024-11-08 14:37:02,009 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:37:02,010 INFO L471 AbstractCegarLoop]: Abstraction has 490 states and 580 transitions. [2024-11-08 14:37:02,010 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 25 states have (on average 2.24) internal successors, (56), 25 states have internal predecessors, (56), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) [2024-11-08 14:37:02,010 INFO L276 IsEmpty]: Start isEmpty. Operand 490 states and 580 transitions. [2024-11-08 14:37:02,011 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-11-08 14:37:02,013 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:37:02,013 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:37:02,026 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-08 14:37:02,213 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-08 14:37:02,213 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:37:02,214 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:37:02,214 INFO L85 PathProgramCache]: Analyzing trace with hash -1040094269, now seen corresponding path program 2 times [2024-11-08 14:37:02,214 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:37:02,214 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1944170240] [2024-11-08 14:37:02,214 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:37:02,215 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:37:02,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,518 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-08 14:37:02,519 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,521 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-08 14:37:02,522 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,524 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-08 14:37:02,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,527 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-11-08 14:37:02,528 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,529 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-11-08 14:37:02,530 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,531 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-11-08 14:37:02,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,533 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 40 [2024-11-08 14:37:02,535 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,537 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 45 [2024-11-08 14:37:02,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,539 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 50 [2024-11-08 14:37:02,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,541 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 58 [2024-11-08 14:37:02,544 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,545 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2024-11-08 14:37:02,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,548 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 72 [2024-11-08 14:37:02,550 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,554 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 77 [2024-11-08 14:37:02,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,557 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 86 [2024-11-08 14:37:02,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,558 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 91 [2024-11-08 14:37:02,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,560 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 97 [2024-11-08 14:37:02,561 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:37:02,562 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2024-11-08 14:37:02,562 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:37:02,562 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1944170240] [2024-11-08 14:37:02,563 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1944170240] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:37:02,563 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [29872477] [2024-11-08 14:37:02,563 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:37:02,563 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:37:02,563 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:37:02,564 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:37:02,567 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-08 14:37:02,617 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:37:02,617 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:37:02,618 INFO L255 TraceCheckSpWp]: Trace formula consists of 267 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-08 14:37:02,620 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:37:02,915 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 34 proven. 77 refuted. 0 times theorem prover too weak. 435 trivial. 0 not checked. [2024-11-08 14:37:02,916 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:37:03,824 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 34 proven. 77 refuted. 0 times theorem prover too weak. 435 trivial. 0 not checked. [2024-11-08 14:37:03,824 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [29872477] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:37:03,824 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:37:03,824 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 13, 10] total 23 [2024-11-08 14:37:03,825 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1486811955] [2024-11-08 14:37:03,825 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:37:03,825 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-08 14:37:03,825 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:37:03,826 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-08 14:37:03,826 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=411, Unknown=0, NotChecked=0, Total=506 [2024-11-08 14:37:03,826 INFO L87 Difference]: Start difference. First operand 490 states and 580 transitions. Second operand has 23 states, 23 states have (on average 3.347826086956522) internal successors, (77), 22 states have internal predecessors, (77), 15 states have call successors, (49), 3 states have call predecessors, (49), 2 states have return successors, (47), 15 states have call predecessors, (47), 15 states have call successors, (47) [2024-11-08 14:37:04,401 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:37:04,401 INFO L93 Difference]: Finished difference Result 562 states and 691 transitions. [2024-11-08 14:37:04,401 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-08 14:37:04,402 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 3.347826086956522) internal successors, (77), 22 states have internal predecessors, (77), 15 states have call successors, (49), 3 states have call predecessors, (49), 2 states have return successors, (47), 15 states have call predecessors, (47), 15 states have call successors, (47) Word has length 106 [2024-11-08 14:37:04,402 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:37:04,404 INFO L225 Difference]: With dead ends: 562 [2024-11-08 14:37:04,404 INFO L226 Difference]: Without dead ends: 493 [2024-11-08 14:37:04,405 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 254 GetRequests, 230 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 155 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=127, Invalid=523, Unknown=0, NotChecked=0, Total=650 [2024-11-08 14:37:04,406 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 22 mSDsluCounter, 324 mSDsCounter, 0 mSdLazyCounter, 424 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 364 SdHoareTripleChecker+Invalid, 442 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 424 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-08 14:37:04,406 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 364 Invalid, 442 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 424 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-08 14:37:04,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 493 states. [2024-11-08 14:37:04,558 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 493 to 440. [2024-11-08 14:37:04,559 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 440 states, 290 states have (on average 1.1793103448275861) internal successors, (342), 310 states have internal predecessors, (342), 93 states have call successors, (93), 56 states have call predecessors, (93), 56 states have return successors, (87), 73 states have call predecessors, (87), 87 states have call successors, (87) [2024-11-08 14:37:04,560 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 440 states to 440 states and 522 transitions. [2024-11-08 14:37:04,561 INFO L78 Accepts]: Start accepts. Automaton has 440 states and 522 transitions. Word has length 106 [2024-11-08 14:37:04,561 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:37:04,561 INFO L471 AbstractCegarLoop]: Abstraction has 440 states and 522 transitions. [2024-11-08 14:37:04,561 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 3.347826086956522) internal successors, (77), 22 states have internal predecessors, (77), 15 states have call successors, (49), 3 states have call predecessors, (49), 2 states have return successors, (47), 15 states have call predecessors, (47), 15 states have call successors, (47) [2024-11-08 14:37:04,562 INFO L276 IsEmpty]: Start isEmpty. Operand 440 states and 522 transitions. [2024-11-08 14:37:04,562 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2024-11-08 14:37:04,562 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:37:04,562 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2024-11-08 14:37:04,575 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-08 14:37:04,763 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-08 14:37:04,763 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:37:04,763 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:37:04,764 INFO L85 PathProgramCache]: Analyzing trace with hash 969385619, now seen corresponding path program 4 times [2024-11-08 14:37:04,764 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:37:04,764 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2050782084] [2024-11-08 14:37:04,764 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:37:04,764 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:37:04,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:37:04,786 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [574624030] [2024-11-08 14:37:04,787 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-08 14:37:04,787 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:37:04,787 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:37:04,788 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:37:04,791 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-08 14:37:04,862 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-08 14:37:04,863 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:37:04,864 INFO L255 TraceCheckSpWp]: Trace formula consists of 226 conjuncts, 73 conjuncts are in the unsatisfiable core [2024-11-08 14:37:04,866 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:37:37,962 INFO L134 CoverageAnalysis]: Checked inductivity of 560 backedges. 185 proven. 75 refuted. 0 times theorem prover too weak. 300 trivial. 0 not checked. [2024-11-08 14:37:37,962 INFO L311 TraceCheckSpWp]: Computing backward predicates...