./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound20.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/hard-ll_unwindbound20.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash a3d3bea00f90884a75828a52041ade76894eb11b308d280406ab40770bedb299 --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-08 14:33:19,157 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-08 14:33:19,223 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-08 14:33:19,229 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-08 14:33:19,230 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-08 14:33:19,260 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-08 14:33:19,261 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-08 14:33:19,262 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-08 14:33:19,262 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-08 14:33:19,264 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-08 14:33:19,264 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-08 14:33:19,265 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-08 14:33:19,265 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-08 14:33:19,265 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-08 14:33:19,266 INFO L153 SettingsManager]: * Use SBE=true [2024-11-08 14:33:19,267 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-08 14:33:19,267 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-08 14:33:19,267 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-08 14:33:19,270 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-08 14:33:19,270 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-08 14:33:19,270 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-08 14:33:19,271 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-08 14:33:19,271 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-08 14:33:19,271 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-08 14:33:19,272 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-08 14:33:19,272 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-08 14:33:19,273 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-08 14:33:19,273 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-08 14:33:19,273 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-08 14:33:19,273 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-08 14:33:19,274 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-08 14:33:19,274 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-08 14:33:19,275 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:33:19,275 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-08 14:33:19,275 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-08 14:33:19,276 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-08 14:33:19,276 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-08 14:33:19,276 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-08 14:33:19,276 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-08 14:33:19,276 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-08 14:33:19,276 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-08 14:33:19,277 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-08 14:33:19,277 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 -> a3d3bea00f90884a75828a52041ade76894eb11b308d280406ab40770bedb299 [2024-11-08 14:33:19,488 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-08 14:33:19,510 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-08 14:33:19,512 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-08 14:33:19,514 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-08 14:33:19,514 INFO L274 PluginConnector]: CDTParser initialized [2024-11-08 14:33:19,515 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound20.c [2024-11-08 14:33:20,963 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-08 14:33:21,139 INFO L384 CDTParser]: Found 1 translation units. [2024-11-08 14:33:21,139 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard-ll_unwindbound20.c [2024-11-08 14:33:21,152 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/45af8363c/3ec73484ffd740949d9506595b1b2b2e/FLAGbf0eba9e3 [2024-11-08 14:33:21,527 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/45af8363c/3ec73484ffd740949d9506595b1b2b2e [2024-11-08 14:33:21,529 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-08 14:33:21,530 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-08 14:33:21,531 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-08 14:33:21,531 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-08 14:33:21,537 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-08 14:33:21,538 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:33:21" (1/1) ... [2024-11-08 14:33:21,539 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4dc22d9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:33:21, skipping insertion in model container [2024-11-08 14:33:21,539 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:33:21" (1/1) ... [2024-11-08 14:33:21,559 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-08 14:33:21,735 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/hard-ll_unwindbound20.c[538,551] [2024-11-08 14:33:21,766 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:33:21,773 INFO L200 MainTranslator]: Completed pre-run [2024-11-08 14:33:21,782 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/hard-ll_unwindbound20.c[538,551] [2024-11-08 14:33:21,789 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:33:21,805 INFO L204 MainTranslator]: Completed translation [2024-11-08 14:33:21,805 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:33:21 WrapperNode [2024-11-08 14:33:21,808 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-08 14:33:21,809 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-08 14:33:21,809 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-08 14:33:21,810 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-08 14:33:21,816 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:33:21" (1/1) ... [2024-11-08 14:33:21,820 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:33:21" (1/1) ... [2024-11-08 14:33:21,842 INFO L138 Inliner]: procedures = 14, calls = 15, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 66 [2024-11-08 14:33:21,844 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-08 14:33:21,844 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-08 14:33:21,845 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-08 14:33:21,845 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-08 14:33:21,853 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:33:21" (1/1) ... [2024-11-08 14:33:21,854 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:33:21" (1/1) ... [2024-11-08 14:33:21,855 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:33:21" (1/1) ... [2024-11-08 14:33:21,866 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-08 14:33:21,867 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:33:21" (1/1) ... [2024-11-08 14:33:21,867 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:33:21" (1/1) ... [2024-11-08 14:33:21,870 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:33:21" (1/1) ... [2024-11-08 14:33:21,873 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:33:21" (1/1) ... [2024-11-08 14:33:21,873 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:33:21" (1/1) ... [2024-11-08 14:33:21,874 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:33:21" (1/1) ... [2024-11-08 14:33:21,876 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-08 14:33:21,877 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-08 14:33:21,877 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-08 14:33:21,877 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-08 14:33:21,878 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:33:21" (1/1) ... [2024-11-08 14:33:21,883 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:33:21,895 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:33:21,910 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:33:21,920 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:33:21,966 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-08 14:33:21,966 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-08 14:33:21,966 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-08 14:33:21,966 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-08 14:33:21,966 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-08 14:33:21,967 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-08 14:33:22,031 INFO L238 CfgBuilder]: Building ICFG [2024-11-08 14:33:22,035 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-08 14:33:22,219 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-08 14:33:22,219 INFO L287 CfgBuilder]: Performing block encoding [2024-11-08 14:33:22,232 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-08 14:33:22,232 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-08 14:33:22,233 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:33:22 BoogieIcfgContainer [2024-11-08 14:33:22,233 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-08 14:33:22,236 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-08 14:33:22,237 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-08 14:33:22,240 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-08 14:33:22,240 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.11 02:33:21" (1/3) ... [2024-11-08 14:33:22,241 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@41a9548 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:33:22, skipping insertion in model container [2024-11-08 14:33:22,242 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:33:21" (2/3) ... [2024-11-08 14:33:22,242 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@41a9548 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:33:22, skipping insertion in model container [2024-11-08 14:33:22,242 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:33:22" (3/3) ... [2024-11-08 14:33:22,244 INFO L112 eAbstractionObserver]: Analyzing ICFG hard-ll_unwindbound20.c [2024-11-08 14:33:22,259 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-08 14:33:22,260 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-08 14:33:22,320 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-08 14:33:22,326 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;@49dc8ec4, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-08 14:33:22,327 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-08 14:33:22,331 INFO L276 IsEmpty]: Start isEmpty. Operand has 28 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 19 states have internal predecessors, (28), 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:33:22,338 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-08 14:33:22,338 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:22,339 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:33:22,339 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:22,344 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:22,345 INFO L85 PathProgramCache]: Analyzing trace with hash -712527539, now seen corresponding path program 1 times [2024-11-08 14:33:22,353 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:22,353 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1805347966] [2024-11-08 14:33:22,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:22,355 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:22,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:22,508 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:33:22,508 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:22,508 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1805347966] [2024-11-08 14:33:22,509 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1805347966] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:33:22,509 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:33:22,510 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-08 14:33:22,511 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2067233786] [2024-11-08 14:33:22,513 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:33:22,519 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-08 14:33:22,520 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:22,544 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-08 14:33:22,546 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 14:33:22,548 INFO L87 Difference]: Start difference. First operand has 28 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 19 states have internal predecessors, (28), 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 4.5) internal successors, (9), 2 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:33:22,570 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:22,571 INFO L93 Difference]: Finished difference Result 53 states and 87 transitions. [2024-11-08 14:33:22,572 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-08 14:33:22,573 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 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:33:22,573 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:22,580 INFO L225 Difference]: With dead ends: 53 [2024-11-08 14:33:22,580 INFO L226 Difference]: Without dead ends: 24 [2024-11-08 14:33:22,583 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:33:22,588 INFO L432 NwaCegarLoop]: 38 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, 38 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:33:22,589 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:33:22,606 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2024-11-08 14:33:22,624 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-08 14:33:22,626 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 15 states have (on average 1.4) internal successors, (21), 16 states have internal predecessors, (21), 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:33:22,627 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 34 transitions. [2024-11-08 14:33:22,629 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 34 transitions. Word has length 10 [2024-11-08 14:33:22,629 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:22,630 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 34 transitions. [2024-11-08 14:33:22,630 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 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:33:22,630 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 34 transitions. [2024-11-08 14:33:22,631 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-08 14:33:22,631 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:22,631 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:33:22,632 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-08 14:33:22,632 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:22,633 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:22,633 INFO L85 PathProgramCache]: Analyzing trace with hash -1983932575, now seen corresponding path program 1 times [2024-11-08 14:33:22,633 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:22,633 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [260011318] [2024-11-08 14:33:22,634 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:22,634 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:22,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:22,849 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:33:22,850 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:22,850 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [260011318] [2024-11-08 14:33:22,850 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [260011318] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:33:22,851 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:33:22,851 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:33:22,851 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [130803970] [2024-11-08 14:33:22,851 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:33:22,853 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:33:22,853 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:22,854 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:33:22,854 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:33:22,855 INFO L87 Difference]: Start difference. First operand 24 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-08 14:33:22,921 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:22,922 INFO L93 Difference]: Finished difference Result 38 states and 53 transitions. [2024-11-08 14:33:22,922 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:33:22,922 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2024-11-08 14:33:22,923 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:22,924 INFO L225 Difference]: With dead ends: 38 [2024-11-08 14:33:22,924 INFO L226 Difference]: Without dead ends: 36 [2024-11-08 14:33:22,924 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:33:22,925 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 12 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:22,926 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 104 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:33:22,927 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2024-11-08 14:33:22,935 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 28. [2024-11-08 14:33:22,935 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:33:22,936 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2024-11-08 14:33:22,936 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 10 [2024-11-08 14:33:22,937 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:22,937 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2024-11-08 14:33:22,937 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-08 14:33:22,937 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2024-11-08 14:33:22,938 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-08 14:33:22,938 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:22,938 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:33:22,938 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-08 14:33:22,939 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:22,939 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:22,940 INFO L85 PathProgramCache]: Analyzing trace with hash 1787143384, now seen corresponding path program 1 times [2024-11-08 14:33:22,940 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:22,940 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [236142707] [2024-11-08 14:33:22,940 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:22,940 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:22,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:23,023 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:33:23,023 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:23,023 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [236142707] [2024-11-08 14:33:23,024 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [236142707] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:33:23,024 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:33:23,024 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-08 14:33:23,024 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [496095783] [2024-11-08 14:33:23,024 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:33:23,024 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-08 14:33:23,025 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:23,025 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-08 14:33:23,025 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-08 14:33:23,026 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 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:33:23,050 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:23,051 INFO L93 Difference]: Finished difference Result 44 states and 59 transitions. [2024-11-08 14:33:23,054 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-08 14:33:23,054 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 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 12 [2024-11-08 14:33:23,055 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:23,055 INFO L225 Difference]: With dead ends: 44 [2024-11-08 14:33:23,055 INFO L226 Difference]: Without dead ends: 30 [2024-11-08 14:33:23,056 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:33:23,057 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 0 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 89 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:33:23,058 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 89 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:33:23,058 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2024-11-08 14:33:23,063 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2024-11-08 14:33:23,064 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 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:33:23,065 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2024-11-08 14:33:23,065 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 12 [2024-11-08 14:33:23,065 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:23,065 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2024-11-08 14:33:23,066 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 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:33:23,066 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2024-11-08 14:33:23,066 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-08 14:33:23,066 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:23,067 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:33:23,067 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-08 14:33:23,067 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:23,067 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:23,068 INFO L85 PathProgramCache]: Analyzing trace with hash 472519838, now seen corresponding path program 1 times [2024-11-08 14:33:23,068 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:23,068 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [409432163] [2024-11-08 14:33:23,072 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:23,072 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:23,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:23,251 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:33:23,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:23,266 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:33:23,271 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:23,271 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [409432163] [2024-11-08 14:33:23,272 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [409432163] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:33:23,272 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:33:23,272 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:33:23,272 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1849390005] [2024-11-08 14:33:23,272 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:33:23,272 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:33:23,273 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:23,273 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:33:23,274 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:33:23,274 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-08 14:33:23,355 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:23,356 INFO L93 Difference]: Finished difference Result 44 states and 58 transitions. [2024-11-08 14:33:23,356 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:33:23,356 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2024-11-08 14:33:23,357 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:23,358 INFO L225 Difference]: With dead ends: 44 [2024-11-08 14:33:23,358 INFO L226 Difference]: Without dead ends: 42 [2024-11-08 14:33:23,359 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:33:23,363 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 12 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:23,363 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 101 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:33:23,364 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-08 14:33:23,372 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 34. [2024-11-08 14:33:23,373 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 24 states have internal predecessors, (29), 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:33:23,374 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 42 transitions. [2024-11-08 14:33:23,374 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 42 transitions. Word has length 15 [2024-11-08 14:33:23,374 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:23,374 INFO L471 AbstractCegarLoop]: Abstraction has 34 states and 42 transitions. [2024-11-08 14:33:23,374 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-08 14:33:23,375 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 42 transitions. [2024-11-08 14:33:23,375 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2024-11-08 14:33:23,375 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:23,375 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:33:23,376 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-08 14:33:23,376 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:23,376 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:23,377 INFO L85 PathProgramCache]: Analyzing trace with hash 838495553, now seen corresponding path program 1 times [2024-11-08 14:33:23,377 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:23,377 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1705107709] [2024-11-08 14:33:23,377 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:23,377 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:23,398 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:33:23,403 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [846155769] [2024-11-08 14:33:23,407 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:23,407 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:23,408 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:33:23,410 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:33:23,420 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:33:23,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:23,482 INFO L255 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-08 14:33:23,487 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:33:23,600 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:33:23,601 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:33:23,601 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:23,601 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1705107709] [2024-11-08 14:33:23,603 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:33:23,604 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [846155769] [2024-11-08 14:33:23,604 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [846155769] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:33:23,604 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:33:23,604 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:33:23,604 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [467123025] [2024-11-08 14:33:23,608 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:33:23,608 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:33:23,609 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:23,609 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:33:23,609 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:33:23,609 INFO L87 Difference]: Start difference. First operand 34 states and 42 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (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:33:23,680 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:23,680 INFO L93 Difference]: Finished difference Result 63 states and 85 transitions. [2024-11-08 14:33:23,680 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:33:23,681 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (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 20 [2024-11-08 14:33:23,681 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:23,682 INFO L225 Difference]: With dead ends: 63 [2024-11-08 14:33:23,682 INFO L226 Difference]: Without dead ends: 48 [2024-11-08 14:33:23,682 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 16 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:33:23,683 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 7 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:23,684 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 105 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:33:23,685 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2024-11-08 14:33:23,693 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2024-11-08 14:33:23,695 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 30 states have (on average 1.2666666666666666) internal successors, (38), 32 states have internal predecessors, (38), 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:33:23,699 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 62 transitions. [2024-11-08 14:33:23,699 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 62 transitions. Word has length 20 [2024-11-08 14:33:23,702 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:23,702 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 62 transitions. [2024-11-08 14:33:23,702 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (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:33:23,702 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 62 transitions. [2024-11-08 14:33:23,703 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-08 14:33:23,703 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:23,703 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:33:23,718 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:33:23,904 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:33:23,904 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:23,905 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:23,905 INFO L85 PathProgramCache]: Analyzing trace with hash 414140572, now seen corresponding path program 1 times [2024-11-08 14:33:23,905 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:23,905 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [323533257] [2024-11-08 14:33:23,905 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:23,905 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:23,924 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:24,002 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:33:24,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:24,010 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-08 14:33:24,012 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:24,019 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 14:33:24,025 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:24,032 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 14:33:24,032 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:24,032 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [323533257] [2024-11-08 14:33:24,033 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [323533257] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:33:24,033 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:33:24,033 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:33:24,033 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [723620067] [2024-11-08 14:33:24,033 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:33:24,034 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:33:24,034 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:24,036 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:33:24,036 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:33:24,037 INFO L87 Difference]: Start difference. First operand 48 states and 62 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 2 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:33:24,072 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:24,073 INFO L93 Difference]: Finished difference Result 67 states and 77 transitions. [2024-11-08 14:33:24,073 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:33:24,073 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 2 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 28 [2024-11-08 14:33:24,074 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:24,074 INFO L225 Difference]: With dead ends: 67 [2024-11-08 14:33:24,074 INFO L226 Difference]: Without dead ends: 60 [2024-11-08 14:33:24,075 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:33:24,076 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 7 mSDsluCounter, 77 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:24,076 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 108 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:33:24,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-11-08 14:33:24,084 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2024-11-08 14:33:24,086 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 39 states have (on average 1.1794871794871795) internal successors, (46), 40 states have internal predecessors, (46), 12 states have call successors, (12), 7 states have call predecessors, (12), 7 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-08 14:33:24,086 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 69 transitions. [2024-11-08 14:33:24,088 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 69 transitions. Word has length 28 [2024-11-08 14:33:24,088 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:24,088 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 69 transitions. [2024-11-08 14:33:24,089 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 2 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:33:24,089 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 69 transitions. [2024-11-08 14:33:24,090 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-08 14:33:24,090 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:24,090 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:33:24,090 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-08 14:33:24,091 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:24,091 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:24,091 INFO L85 PathProgramCache]: Analyzing trace with hash 415868450, now seen corresponding path program 1 times [2024-11-08 14:33:24,091 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:24,091 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [594812918] [2024-11-08 14:33:24,092 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:24,092 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:24,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:33:24,111 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1270887280] [2024-11-08 14:33:24,111 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:24,111 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:24,111 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:33:24,113 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:33:24,115 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:33:24,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:24,161 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-08 14:33:24,162 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:33:24,272 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 14:33:24,273 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:33:24,273 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:24,273 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [594812918] [2024-11-08 14:33:24,273 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:33:24,273 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1270887280] [2024-11-08 14:33:24,273 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1270887280] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:33:24,273 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:33:24,273 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:33:24,274 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1580587379] [2024-11-08 14:33:24,274 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:33:24,274 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:33:24,274 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:24,274 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:33:24,275 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:33:24,275 INFO L87 Difference]: Start difference. First operand 59 states and 69 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 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:33:24,342 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:24,343 INFO L93 Difference]: Finished difference Result 73 states and 88 transitions. [2024-11-08 14:33:24,343 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:33:24,343 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 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 28 [2024-11-08 14:33:24,344 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:24,345 INFO L225 Difference]: With dead ends: 73 [2024-11-08 14:33:24,345 INFO L226 Difference]: Without dead ends: 71 [2024-11-08 14:33:24,345 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 24 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:33:24,346 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 9 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:24,346 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 85 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:33:24,347 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2024-11-08 14:33:24,365 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 70. [2024-11-08 14:33:24,367 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 46 states have (on average 1.2173913043478262) internal successors, (56), 48 states have internal predecessors, (56), 15 states have call successors, (15), 8 states have call predecessors, (15), 8 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-08 14:33:24,369 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 85 transitions. [2024-11-08 14:33:24,370 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 85 transitions. Word has length 28 [2024-11-08 14:33:24,371 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:24,371 INFO L471 AbstractCegarLoop]: Abstraction has 70 states and 85 transitions. [2024-11-08 14:33:24,371 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 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:33:24,371 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 85 transitions. [2024-11-08 14:33:24,373 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-08 14:33:24,373 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:24,374 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, 1, 1] [2024-11-08 14:33:24,391 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-08 14:33:24,574 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,SelfDestructingSolverStorable6 [2024-11-08 14:33:24,575 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:24,575 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:24,575 INFO L85 PathProgramCache]: Analyzing trace with hash -1091220578, now seen corresponding path program 1 times [2024-11-08 14:33:24,575 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:24,575 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1603836323] [2024-11-08 14:33:24,575 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:24,576 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:24,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:24,662 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:33:24,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:24,666 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-08 14:33:24,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:24,670 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 14:33:24,672 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:24,675 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-08 14:33:24,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:24,678 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:33:24,679 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:24,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1603836323] [2024-11-08 14:33:24,679 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1603836323] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:33:24,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1296168559] [2024-11-08 14:33:24,679 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:24,680 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:24,680 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:33:24,681 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:33:24,683 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:33:24,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:24,729 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-08 14:33:24,731 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:33:24,790 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:33:24,794 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:33:24,870 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:33:24,871 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1296168559] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:33:24,871 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:33:24,871 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 8 [2024-11-08 14:33:24,871 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [553047100] [2024-11-08 14:33:24,871 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:33:24,872 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-08 14:33:24,872 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:24,873 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-08 14:33:24,873 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2024-11-08 14:33:24,873 INFO L87 Difference]: Start difference. First operand 70 states and 85 transitions. Second operand has 8 states, 8 states have (on average 3.875) internal successors, (31), 8 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:33:25,032 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:25,033 INFO L93 Difference]: Finished difference Result 157 states and 192 transitions. [2024-11-08 14:33:25,034 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-08 14:33:25,034 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.875) internal successors, (31), 8 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 35 [2024-11-08 14:33:25,035 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:25,037 INFO L225 Difference]: With dead ends: 157 [2024-11-08 14:33:25,039 INFO L226 Difference]: Without dead ends: 132 [2024-11-08 14:33:25,040 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 74 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2024-11-08 14:33:25,041 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 54 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 76 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:25,041 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 132 Invalid, 76 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:33:25,044 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2024-11-08 14:33:25,064 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 125. [2024-11-08 14:33:25,065 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 125 states, 81 states have (on average 1.1975308641975309) internal successors, (97), 85 states have internal predecessors, (97), 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:33:25,067 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 125 states to 125 states and 148 transitions. [2024-11-08 14:33:25,067 INFO L78 Accepts]: Start accepts. Automaton has 125 states and 148 transitions. Word has length 35 [2024-11-08 14:33:25,067 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:25,067 INFO L471 AbstractCegarLoop]: Abstraction has 125 states and 148 transitions. [2024-11-08 14:33:25,068 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.875) internal successors, (31), 8 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:33:25,068 INFO L276 IsEmpty]: Start isEmpty. Operand 125 states and 148 transitions. [2024-11-08 14:33:25,068 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-08 14:33:25,069 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:25,069 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:33:25,086 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-08 14:33:25,269 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:25,270 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:25,271 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:25,271 INFO L85 PathProgramCache]: Analyzing trace with hash 1884102282, now seen corresponding path program 1 times [2024-11-08 14:33:25,271 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:25,271 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [599798953] [2024-11-08 14:33:25,271 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:25,272 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:25,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:33:25,288 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [852671897] [2024-11-08 14:33:25,289 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:25,289 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:25,289 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:33:25,291 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:33:25,292 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:33:25,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:25,343 INFO L255 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-08 14:33:25,345 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:33:25,457 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:33:25,458 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:33:25,535 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:33:25,536 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:25,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [599798953] [2024-11-08 14:33:25,536 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:33:25,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [852671897] [2024-11-08 14:33:25,536 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [852671897] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-08 14:33:25,536 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:33:25,537 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-08 14:33:25,537 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1175864719] [2024-11-08 14:33:25,537 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:33:25,537 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:33:25,537 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:25,538 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:33:25,538 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-08 14:33:25,538 INFO L87 Difference]: Start difference. First operand 125 states and 148 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (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:33:25,635 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:25,636 INFO L93 Difference]: Finished difference Result 148 states and 176 transitions. [2024-11-08 14:33:25,637 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:33:25,637 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (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 38 [2024-11-08 14:33:25,638 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:25,640 INFO L225 Difference]: With dead ends: 148 [2024-11-08 14:33:25,640 INFO L226 Difference]: Without dead ends: 142 [2024-11-08 14:33:25,641 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 67 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-08 14:33:25,642 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 8 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:25,643 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 99 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:33:25,644 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2024-11-08 14:33:25,670 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 134. [2024-11-08 14:33:25,670 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 88 states have (on average 1.1704545454545454) internal successors, (103), 92 states have internal predecessors, (103), 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:33:25,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 157 transitions. [2024-11-08 14:33:25,671 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 157 transitions. Word has length 38 [2024-11-08 14:33:25,672 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:25,672 INFO L471 AbstractCegarLoop]: Abstraction has 134 states and 157 transitions. [2024-11-08 14:33:25,672 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (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:33:25,672 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 157 transitions. [2024-11-08 14:33:25,673 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-08 14:33:25,673 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:25,673 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, 1, 1] [2024-11-08 14:33:25,690 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-08 14:33:25,877 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:25,878 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:25,878 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:25,878 INFO L85 PathProgramCache]: Analyzing trace with hash -1909657797, now seen corresponding path program 1 times [2024-11-08 14:33:25,878 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:25,878 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2106637113] [2024-11-08 14:33:25,878 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:25,879 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:25,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:25,984 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:33:25,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,001 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-08 14:33:26,006 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,013 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 14:33:26,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,019 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-08 14:33:26,023 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,025 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-08 14:33:26,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,032 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-11-08 14:33:26,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,038 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:33:26,038 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:26,038 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2106637113] [2024-11-08 14:33:26,038 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2106637113] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:33:26,038 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:33:26,039 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:33:26,039 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1802955693] [2024-11-08 14:33:26,039 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:33:26,039 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:33:26,039 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:26,040 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:33:26,040 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:33:26,041 INFO L87 Difference]: Start difference. First operand 134 states and 157 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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:33:26,094 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:26,096 INFO L93 Difference]: Finished difference Result 139 states and 161 transitions. [2024-11-08 14:33:26,096 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:33:26,096 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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 44 [2024-11-08 14:33:26,097 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:26,098 INFO L225 Difference]: With dead ends: 139 [2024-11-08 14:33:26,098 INFO L226 Difference]: Without dead ends: 120 [2024-11-08 14:33:26,098 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:33:26,099 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 1 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:26,099 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 118 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:33:26,103 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2024-11-08 14:33:26,125 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 120. [2024-11-08 14:33:26,125 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 79 states have (on average 1.1772151898734178) internal successors, (93), 82 states have internal predecessors, (93), 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:33:26,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 141 transitions. [2024-11-08 14:33:26,127 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 141 transitions. Word has length 44 [2024-11-08 14:33:26,127 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:26,127 INFO L471 AbstractCegarLoop]: Abstraction has 120 states and 141 transitions. [2024-11-08 14:33:26,128 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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:33:26,128 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 141 transitions. [2024-11-08 14:33:26,129 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-08 14:33:26,131 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:26,131 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, 1, 1] [2024-11-08 14:33:26,131 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2024-11-08 14:33:26,131 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:26,132 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:26,132 INFO L85 PathProgramCache]: Analyzing trace with hash -785132454, now seen corresponding path program 1 times [2024-11-08 14:33:26,132 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:26,132 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2011195328] [2024-11-08 14:33:26,132 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:26,132 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:26,146 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,221 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:33:26,222 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,226 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-08 14:33:26,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,231 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 14:33:26,233 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,235 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-08 14:33:26,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,238 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-08 14:33:26,239 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,241 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-08 14:33:26,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,245 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-08 14:33:26,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,248 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:33:26,248 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:26,248 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2011195328] [2024-11-08 14:33:26,248 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2011195328] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:33:26,248 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1541273029] [2024-11-08 14:33:26,249 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:26,249 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:26,249 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:33:26,251 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:33:26,252 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:33:26,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,302 INFO L255 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-08 14:33:26,304 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:33:26,370 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:33:26,370 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:33:26,441 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:33:26,441 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1541273029] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:33:26,441 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:33:26,441 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2024-11-08 14:33:26,441 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1680148277] [2024-11-08 14:33:26,441 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:33:26,442 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-08 14:33:26,442 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:26,442 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-08 14:33:26,443 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-11-08 14:33:26,443 INFO L87 Difference]: Start difference. First operand 120 states and 141 transitions. Second operand has 10 states, 10 states have (on average 3.8) internal successors, (38), 10 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:33:26,609 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:26,609 INFO L93 Difference]: Finished difference Result 243 states and 296 transitions. [2024-11-08 14:33:26,610 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-08 14:33:26,610 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.8) internal successors, (38), 10 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 51 [2024-11-08 14:33:26,610 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:26,612 INFO L225 Difference]: With dead ends: 243 [2024-11-08 14:33:26,612 INFO L226 Difference]: Without dead ends: 222 [2024-11-08 14:33:26,612 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 111 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=52, Invalid=104, Unknown=0, NotChecked=0, Total=156 [2024-11-08 14:33:26,613 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 79 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 87 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 185 SdHoareTripleChecker+Invalid, 102 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 87 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:26,613 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 185 Invalid, 102 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 87 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 14:33:26,614 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 222 states. [2024-11-08 14:33:26,644 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 222 to 215. [2024-11-08 14:33:26,644 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 215 states, 140 states have (on average 1.1928571428571428) internal successors, (167), 149 states have internal predecessors, (167), 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:33:26,645 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 215 states to 215 states and 261 transitions. [2024-11-08 14:33:26,646 INFO L78 Accepts]: Start accepts. Automaton has 215 states and 261 transitions. Word has length 51 [2024-11-08 14:33:26,646 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:26,646 INFO L471 AbstractCegarLoop]: Abstraction has 215 states and 261 transitions. [2024-11-08 14:33:26,646 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.8) internal successors, (38), 10 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:33:26,646 INFO L276 IsEmpty]: Start isEmpty. Operand 215 states and 261 transitions. [2024-11-08 14:33:26,647 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-11-08 14:33:26,647 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:26,647 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, 1, 1] [2024-11-08 14:33:26,664 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:33:26,848 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,SelfDestructingSolverStorable10 [2024-11-08 14:33:26,848 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:26,849 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:26,849 INFO L85 PathProgramCache]: Analyzing trace with hash 98519191, now seen corresponding path program 1 times [2024-11-08 14:33:26,849 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:26,849 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1119719825] [2024-11-08 14:33:26,849 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:26,849 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:26,880 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:33:26,881 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1744331850] [2024-11-08 14:33:26,881 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:26,882 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:26,882 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:33:26,883 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:33:26,884 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:33:26,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:26,952 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-08 14:33:26,955 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:33:27,597 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2024-11-08 14:33:27,598 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:33:29,608 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2024-11-08 14:33:29,609 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:29,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1119719825] [2024-11-08 14:33:29,609 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:33:29,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1744331850] [2024-11-08 14:33:29,609 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1744331850] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:33:29,609 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:33:29,609 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 18 [2024-11-08 14:33:29,610 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2022934201] [2024-11-08 14:33:29,610 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:33:29,610 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-08 14:33:29,610 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:29,611 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-08 14:33:29,611 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=244, Unknown=0, NotChecked=0, Total=306 [2024-11-08 14:33:29,611 INFO L87 Difference]: Start difference. First operand 215 states and 261 transitions. Second operand has 18 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 8 states have call successors, (18), 3 states have call predecessors, (18), 1 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-08 14:33:31,725 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:31,725 INFO L93 Difference]: Finished difference Result 379 states and 486 transitions. [2024-11-08 14:33:31,726 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-08 14:33:31,726 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 8 states have call successors, (18), 3 states have call predecessors, (18), 1 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 60 [2024-11-08 14:33:31,727 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:31,729 INFO L225 Difference]: With dead ends: 379 [2024-11-08 14:33:31,729 INFO L226 Difference]: Without dead ends: 303 [2024-11-08 14:33:31,730 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 102 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 139 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=152, Invalid=550, Unknown=0, NotChecked=0, Total=702 [2024-11-08 14:33:31,733 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 115 mSDsluCounter, 322 mSDsCounter, 0 mSdLazyCounter, 287 mSolverCounterSat, 112 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 118 SdHoareTripleChecker+Valid, 361 SdHoareTripleChecker+Invalid, 399 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 112 IncrementalHoareTripleChecker+Valid, 287 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:31,733 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [118 Valid, 361 Invalid, 399 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [112 Valid, 287 Invalid, 0 Unknown, 0 Unchecked, 1.6s Time] [2024-11-08 14:33:31,734 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 303 states. [2024-11-08 14:33:31,784 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 303 to 265. [2024-11-08 14:33:31,786 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 265 states, 178 states have (on average 1.202247191011236) internal successors, (214), 187 states have internal predecessors, (214), 55 states have call successors, (55), 31 states have call predecessors, (55), 31 states have return successors, (52), 46 states have call predecessors, (52), 52 states have call successors, (52) [2024-11-08 14:33:31,788 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 265 states to 265 states and 321 transitions. [2024-11-08 14:33:31,788 INFO L78 Accepts]: Start accepts. Automaton has 265 states and 321 transitions. Word has length 60 [2024-11-08 14:33:31,788 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:31,789 INFO L471 AbstractCegarLoop]: Abstraction has 265 states and 321 transitions. [2024-11-08 14:33:31,789 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 8 states have call successors, (18), 3 states have call predecessors, (18), 1 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-08 14:33:31,789 INFO L276 IsEmpty]: Start isEmpty. Operand 265 states and 321 transitions. [2024-11-08 14:33:31,791 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2024-11-08 14:33:31,791 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:31,791 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, 1, 1] [2024-11-08 14:33:31,809 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-08 14:33:31,991 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:31,992 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:31,992 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:31,992 INFO L85 PathProgramCache]: Analyzing trace with hash -902942769, now seen corresponding path program 1 times [2024-11-08 14:33:31,993 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:31,993 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1602434127] [2024-11-08 14:33:31,993 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:31,993 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:32,024 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:33:32,026 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [613467070] [2024-11-08 14:33:32,026 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:32,026 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:32,026 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:33:32,028 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:33:32,031 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:33:32,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:32,089 INFO L255 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-11-08 14:33:32,092 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:33:32,589 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 20 proven. 11 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-11-08 14:33:32,590 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:33:33,307 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 20 proven. 11 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-11-08 14:33:33,307 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:33,307 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1602434127] [2024-11-08 14:33:33,307 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:33:33,307 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [613467070] [2024-11-08 14:33:33,307 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [613467070] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:33:33,308 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:33:33,308 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 19 [2024-11-08 14:33:33,308 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [657279135] [2024-11-08 14:33:33,308 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:33:33,308 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-08 14:33:33,308 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:33,309 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-08 14:33:33,309 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=275, Unknown=0, NotChecked=0, Total=342 [2024-11-08 14:33:33,310 INFO L87 Difference]: Start difference. First operand 265 states and 321 transitions. Second operand has 19 states, 18 states have (on average 2.2777777777777777) internal successors, (41), 17 states have internal predecessors, (41), 10 states have call successors, (22), 3 states have call predecessors, (22), 1 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-08 14:33:34,045 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:34,046 INFO L93 Difference]: Finished difference Result 389 states and 483 transitions. [2024-11-08 14:33:34,046 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-08 14:33:34,046 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 2.2777777777777777) internal successors, (41), 17 states have internal predecessors, (41), 10 states have call successors, (22), 3 states have call predecessors, (22), 1 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) Word has length 71 [2024-11-08 14:33:34,047 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:34,049 INFO L225 Difference]: With dead ends: 389 [2024-11-08 14:33:34,049 INFO L226 Difference]: Without dead ends: 320 [2024-11-08 14:33:34,051 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 123 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 124 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=174, Invalid=696, Unknown=0, NotChecked=0, Total=870 [2024-11-08 14:33:34,052 INFO L432 NwaCegarLoop]: 51 mSDtfsCounter, 69 mSDsluCounter, 468 mSDsCounter, 0 mSdLazyCounter, 328 mSolverCounterSat, 62 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 72 SdHoareTripleChecker+Valid, 519 SdHoareTripleChecker+Invalid, 390 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 328 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:34,052 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [72 Valid, 519 Invalid, 390 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 328 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-08 14:33:34,053 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 320 states. [2024-11-08 14:33:34,101 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 320 to 271. [2024-11-08 14:33:34,102 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 271 states, 183 states have (on average 1.2021857923497268) internal successors, (220), 188 states have internal predecessors, (220), 56 states have call successors, (56), 32 states have call predecessors, (56), 31 states have return successors, (53), 50 states have call predecessors, (53), 53 states have call successors, (53) [2024-11-08 14:33:34,104 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 271 states to 271 states and 329 transitions. [2024-11-08 14:33:34,104 INFO L78 Accepts]: Start accepts. Automaton has 271 states and 329 transitions. Word has length 71 [2024-11-08 14:33:34,104 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:34,105 INFO L471 AbstractCegarLoop]: Abstraction has 271 states and 329 transitions. [2024-11-08 14:33:34,105 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 2.2777777777777777) internal successors, (41), 17 states have internal predecessors, (41), 10 states have call successors, (22), 3 states have call predecessors, (22), 1 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-08 14:33:34,105 INFO L276 IsEmpty]: Start isEmpty. Operand 271 states and 329 transitions. [2024-11-08 14:33:34,106 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-08 14:33:34,106 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:34,106 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:33:34,122 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-08 14:33:34,306 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:34,307 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:34,307 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:34,307 INFO L85 PathProgramCache]: Analyzing trace with hash -1932765757, now seen corresponding path program 2 times [2024-11-08 14:33:34,308 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:34,308 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1002852812] [2024-11-08 14:33:34,308 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:34,308 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:34,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:34,464 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:33:34,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:34,468 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-08 14:33:34,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:34,471 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 14:33:34,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:34,475 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-08 14:33:34,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:34,478 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-08 14:33:34,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:34,481 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-08 14:33:34,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:34,484 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-08 14:33:34,486 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:34,488 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-08 14:33:34,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:34,491 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 56 [2024-11-08 14:33:34,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:34,496 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 61 [2024-11-08 14:33:34,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:34,500 INFO L134 CoverageAnalysis]: Checked inductivity of 218 backedges. 27 proven. 11 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-11-08 14:33:34,500 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:34,500 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1002852812] [2024-11-08 14:33:34,500 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1002852812] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:33:34,501 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [868794018] [2024-11-08 14:33:34,501 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:33:34,501 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:34,501 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:33:34,503 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:33:34,504 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:33:34,562 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:33:34,562 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:33:34,563 INFO L255 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-08 14:33:34,565 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:33:34,622 INFO L134 CoverageAnalysis]: Checked inductivity of 218 backedges. 27 proven. 11 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-11-08 14:33:34,623 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:33:34,729 INFO L134 CoverageAnalysis]: Checked inductivity of 218 backedges. 27 proven. 11 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-11-08 14:33:34,729 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [868794018] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:33:34,730 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:33:34,730 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 5 [2024-11-08 14:33:34,730 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [362263335] [2024-11-08 14:33:34,730 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:33:34,730 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:33:34,731 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:34,731 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:33:34,731 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:33:34,731 INFO L87 Difference]: Start difference. First operand 271 states and 329 transitions. Second operand has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 4 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-11-08 14:33:34,844 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:34,844 INFO L93 Difference]: Finished difference Result 309 states and 376 transitions. [2024-11-08 14:33:34,845 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-08 14:33:34,845 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 4 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) Word has length 74 [2024-11-08 14:33:34,845 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:34,847 INFO L225 Difference]: With dead ends: 309 [2024-11-08 14:33:34,847 INFO L226 Difference]: Without dead ends: 256 [2024-11-08 14:33:34,847 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 168 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:33:34,850 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 0 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:34,850 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 131 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:33:34,851 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 256 states. [2024-11-08 14:33:34,899 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 256 to 248. [2024-11-08 14:33:34,899 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 248 states, 169 states have (on average 1.183431952662722) internal successors, (200), 172 states have internal predecessors, (200), 49 states have call successors, (49), 30 states have call predecessors, (49), 29 states have return successors, (47), 45 states have call predecessors, (47), 47 states have call successors, (47) [2024-11-08 14:33:34,900 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 248 states to 248 states and 296 transitions. [2024-11-08 14:33:34,902 INFO L78 Accepts]: Start accepts. Automaton has 248 states and 296 transitions. Word has length 74 [2024-11-08 14:33:34,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:34,902 INFO L471 AbstractCegarLoop]: Abstraction has 248 states and 296 transitions. [2024-11-08 14:33:34,902 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 4 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-11-08 14:33:34,902 INFO L276 IsEmpty]: Start isEmpty. Operand 248 states and 296 transitions. [2024-11-08 14:33:34,903 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-08 14:33:34,903 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:34,903 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, 1, 1] [2024-11-08 14:33:34,920 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:33:35,103 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,SelfDestructingSolverStorable13 [2024-11-08 14:33:35,104 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:35,105 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:35,105 INFO L85 PathProgramCache]: Analyzing trace with hash 224462768, now seen corresponding path program 1 times [2024-11-08 14:33:35,105 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:35,105 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1129780962] [2024-11-08 14:33:35,105 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:35,105 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:35,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:35,353 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:33:35,354 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:35,356 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-08 14:33:35,357 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:35,360 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 14:33:35,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:35,363 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-08 14:33:35,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:35,368 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-08 14:33:35,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:35,372 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-08 14:33:35,374 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:35,377 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-08 14:33:35,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:35,381 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-08 14:33:35,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:35,386 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 56 [2024-11-08 14:33:35,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:35,391 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 61 [2024-11-08 14:33:35,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:35,396 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 67 [2024-11-08 14:33:35,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:35,400 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:33:35,401 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:35,401 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1129780962] [2024-11-08 14:33:35,401 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1129780962] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:33:35,401 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1939098220] [2024-11-08 14:33:35,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:35,401 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:35,402 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:33:35,403 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:33:35,405 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:33:35,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:35,466 INFO L255 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-08 14:33:35,470 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:33:35,820 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:33:35,820 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:33:36,188 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:33:36,188 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1939098220] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:33:36,188 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:33:36,188 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 10, 8] total 17 [2024-11-08 14:33:36,188 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1376692153] [2024-11-08 14:33:36,188 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:33:36,189 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-08 14:33:36,189 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:36,189 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-08 14:33:36,190 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=220, Unknown=0, NotChecked=0, Total=272 [2024-11-08 14:33:36,190 INFO L87 Difference]: Start difference. First operand 248 states and 296 transitions. Second operand has 17 states, 17 states have (on average 2.8823529411764706) internal successors, (49), 15 states have internal predecessors, (49), 9 states have call successors, (30), 3 states have call predecessors, (30), 1 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) [2024-11-08 14:33:36,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:36,468 INFO L93 Difference]: Finished difference Result 264 states and 319 transitions. [2024-11-08 14:33:36,468 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-08 14:33:36,468 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.8823529411764706) internal successors, (49), 15 states have internal predecessors, (49), 9 states have call successors, (30), 3 states have call predecessors, (30), 1 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) Word has length 76 [2024-11-08 14:33:36,469 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:36,470 INFO L225 Difference]: With dead ends: 264 [2024-11-08 14:33:36,470 INFO L226 Difference]: Without dead ends: 239 [2024-11-08 14:33:36,471 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 164 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=83, Invalid=337, Unknown=0, NotChecked=0, Total=420 [2024-11-08 14:33:36,471 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 30 mSDsluCounter, 348 mSDsCounter, 0 mSdLazyCounter, 171 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 395 SdHoareTripleChecker+Invalid, 187 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 171 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:36,471 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 395 Invalid, 187 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 171 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-08 14:33:36,472 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 239 states. [2024-11-08 14:33:36,529 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 239 to 229. [2024-11-08 14:33:36,530 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 229 states, 156 states have (on average 1.1923076923076923) internal successors, (186), 159 states have internal predecessors, (186), 45 states have call successors, (45), 28 states have call predecessors, (45), 27 states have return successors, (43), 41 states have call predecessors, (43), 43 states have call successors, (43) [2024-11-08 14:33:36,531 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 229 states to 229 states and 274 transitions. [2024-11-08 14:33:36,531 INFO L78 Accepts]: Start accepts. Automaton has 229 states and 274 transitions. Word has length 76 [2024-11-08 14:33:36,531 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:36,532 INFO L471 AbstractCegarLoop]: Abstraction has 229 states and 274 transitions. [2024-11-08 14:33:36,532 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.8823529411764706) internal successors, (49), 15 states have internal predecessors, (49), 9 states have call successors, (30), 3 states have call predecessors, (30), 1 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) [2024-11-08 14:33:36,532 INFO L276 IsEmpty]: Start isEmpty. Operand 229 states and 274 transitions. [2024-11-08 14:33:36,534 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2024-11-08 14:33:36,534 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:36,534 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:33:36,553 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:33:36,735 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,SelfDestructingSolverStorable14 [2024-11-08 14:33:36,736 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:36,736 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:36,736 INFO L85 PathProgramCache]: Analyzing trace with hash 1653644173, now seen corresponding path program 1 times [2024-11-08 14:33:36,736 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:36,736 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [552696919] [2024-11-08 14:33:36,736 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:36,736 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:36,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,802 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:33:36,803 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,806 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-08 14:33:36,807 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,812 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 14:33:36,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,815 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-08 14:33:36,815 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,817 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-08 14:33:36,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,820 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-08 14:33:36,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,822 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-08 14:33:36,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,824 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-08 14:33:36,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,828 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-08 14:33:36,829 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,832 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-08 14:33:36,833 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,835 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-08 14:33:36,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,840 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 71 [2024-11-08 14:33:36,841 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,842 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 30 proven. 12 refuted. 0 times theorem prover too weak. 264 trivial. 0 not checked. [2024-11-08 14:33:36,842 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:36,842 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [552696919] [2024-11-08 14:33:36,842 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [552696919] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:33:36,842 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1586687496] [2024-11-08 14:33:36,842 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:36,843 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:36,843 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:33:36,845 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:33:36,847 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:33:36,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:33:36,901 INFO L255 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-08 14:33:36,903 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:33:36,936 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 84 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2024-11-08 14:33:36,937 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:33:36,937 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1586687496] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:33:36,937 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:33:36,937 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 6 [2024-11-08 14:33:36,937 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1824506583] [2024-11-08 14:33:36,937 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:33:36,938 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:33:36,938 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:36,938 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:33:36,938 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:33:36,938 INFO L87 Difference]: Start difference. First operand 229 states and 274 transitions. Second operand has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-08 14:33:37,025 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:33:37,025 INFO L93 Difference]: Finished difference Result 250 states and 300 transitions. [2024-11-08 14:33:37,026 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:33:37,026 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 80 [2024-11-08 14:33:37,026 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:33:37,028 INFO L225 Difference]: With dead ends: 250 [2024-11-08 14:33:37,028 INFO L226 Difference]: Without dead ends: 230 [2024-11-08 14:33:37,028 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 104 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:33:37,029 INFO L432 NwaCegarLoop]: 50 mSDtfsCounter, 17 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 109 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:33:37,029 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 109 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:33:37,029 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 230 states. [2024-11-08 14:33:37,072 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 230 to 222. [2024-11-08 14:33:37,072 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 222 states, 152 states have (on average 1.1578947368421053) internal successors, (176), 154 states have internal predecessors, (176), 43 states have call successors, (43), 26 states have call predecessors, (43), 26 states have return successors, (42), 41 states have call predecessors, (42), 42 states have call successors, (42) [2024-11-08 14:33:37,073 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 222 states to 222 states and 261 transitions. [2024-11-08 14:33:37,074 INFO L78 Accepts]: Start accepts. Automaton has 222 states and 261 transitions. Word has length 80 [2024-11-08 14:33:37,074 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:33:37,075 INFO L471 AbstractCegarLoop]: Abstraction has 222 states and 261 transitions. [2024-11-08 14:33:37,075 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 4 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-08 14:33:37,075 INFO L276 IsEmpty]: Start isEmpty. Operand 222 states and 261 transitions. [2024-11-08 14:33:37,075 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2024-11-08 14:33:37,076 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:33:37,076 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, 1, 1] [2024-11-08 14:33:37,092 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:33:37,276 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,SelfDestructingSolverStorable15 [2024-11-08 14:33:37,276 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:33:37,277 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:33:37,277 INFO L85 PathProgramCache]: Analyzing trace with hash -1315137972, now seen corresponding path program 3 times [2024-11-08 14:33:37,277 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:33:37,277 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [946932367] [2024-11-08 14:33:37,277 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:33:37,277 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:33:37,304 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:33:37,305 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2062307839] [2024-11-08 14:33:37,305 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 14:33:37,305 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:33:37,305 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:33:37,307 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:33:37,308 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:33:37,371 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-08 14:33:37,371 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:33:37,372 INFO L255 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-11-08 14:33:37,375 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:33:37,843 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 37 proven. 55 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-08 14:33:37,843 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:33:53,640 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 37 proven. 55 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-08 14:33:53,641 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:33:53,641 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [946932367] [2024-11-08 14:33:53,641 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:33:53,642 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2062307839] [2024-11-08 14:33:53,642 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2062307839] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:33:53,642 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:33:53,642 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 21 [2024-11-08 14:33:53,642 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [973451141] [2024-11-08 14:33:53,642 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:33:53,643 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-08 14:33:53,643 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:33:53,644 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-08 14:33:53,644 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=348, Unknown=0, NotChecked=0, Total=420 [2024-11-08 14:33:53,644 INFO L87 Difference]: Start difference. First operand 222 states and 261 transitions. Second operand has 21 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 20 states have internal predecessors, (56), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) [2024-11-08 14:33:59,609 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.06s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:34:01,670 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:34:01,670 INFO L93 Difference]: Finished difference Result 296 states and 378 transitions. [2024-11-08 14:34:01,671 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-08 14:34:01,671 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 20 states have internal predecessors, (56), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) Word has length 92 [2024-11-08 14:34:01,671 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:34:01,673 INFO L225 Difference]: With dead ends: 296 [2024-11-08 14:34:01,673 INFO L226 Difference]: Without dead ends: 272 [2024-11-08 14:34:01,673 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 190 GetRequests, 163 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 69 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=142, Invalid=614, Unknown=0, NotChecked=0, Total=756 [2024-11-08 14:34:01,674 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 97 mSDsluCounter, 491 mSDsCounter, 0 mSdLazyCounter, 547 mSolverCounterSat, 136 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 538 SdHoareTripleChecker+Invalid, 684 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 136 IncrementalHoareTripleChecker+Valid, 547 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.6s IncrementalHoareTripleChecker+Time [2024-11-08 14:34:01,674 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [101 Valid, 538 Invalid, 684 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [136 Valid, 547 Invalid, 1 Unknown, 0 Unchecked, 3.6s Time] [2024-11-08 14:34:01,675 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 272 states. [2024-11-08 14:34:01,722 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 272 to 250. [2024-11-08 14:34:01,722 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 250 states, 168 states have (on average 1.1845238095238095) internal successors, (199), 175 states have internal predecessors, (199), 54 states have call successors, (54), 27 states have call predecessors, (54), 27 states have return successors, (53), 47 states have call predecessors, (53), 53 states have call successors, (53) [2024-11-08 14:34:01,724 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 250 states to 250 states and 306 transitions. [2024-11-08 14:34:01,724 INFO L78 Accepts]: Start accepts. Automaton has 250 states and 306 transitions. Word has length 92 [2024-11-08 14:34:01,725 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:34:01,725 INFO L471 AbstractCegarLoop]: Abstraction has 250 states and 306 transitions. [2024-11-08 14:34:01,725 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 20 states have internal predecessors, (56), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) [2024-11-08 14:34:01,725 INFO L276 IsEmpty]: Start isEmpty. Operand 250 states and 306 transitions. [2024-11-08 14:34:01,726 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2024-11-08 14:34:01,726 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:34:01,726 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, 1, 1] [2024-11-08 14:34:01,741 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:34:01,930 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,SelfDestructingSolverStorable16 [2024-11-08 14:34:01,930 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:34:01,931 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:34:01,931 INFO L85 PathProgramCache]: Analyzing trace with hash 57999976, now seen corresponding path program 1 times [2024-11-08 14:34:01,931 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:34:01,931 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [4229971] [2024-11-08 14:34:01,931 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:34:01,931 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:34:01,942 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,089 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:34:02,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,092 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-08 14:34:02,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,094 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 14:34:02,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,097 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-08 14:34:02,098 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,099 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-08 14:34:02,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,104 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-08 14:34:02,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,107 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-08 14:34:02,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,111 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-08 14:34:02,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,113 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-08 14:34:02,115 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,117 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-08 14:34:02,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,119 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-08 14:34:02,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,123 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-11-08 14:34:02,125 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,127 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 80 [2024-11-08 14:34:02,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,129 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 85 [2024-11-08 14:34:02,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,131 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:34:02,131 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:34:02,131 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [4229971] [2024-11-08 14:34:02,131 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [4229971] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:34:02,132 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1984893483] [2024-11-08 14:34:02,132 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:34:02,132 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:34:02,132 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:34:02,134 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:34:02,135 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:34:02,196 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:02,197 INFO L255 TraceCheckSpWp]: Trace formula consists of 236 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-08 14:34:02,199 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:34:02,288 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:34:02,289 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:34:02,415 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:34:02,415 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1984893483] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:34:02,416 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:34:02,416 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 8] total 14 [2024-11-08 14:34:02,416 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [724333777] [2024-11-08 14:34:02,416 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:34:02,416 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-08 14:34:02,416 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:34:02,417 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-08 14:34:02,417 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2024-11-08 14:34:02,418 INFO L87 Difference]: Start difference. First operand 250 states and 306 transitions. Second operand has 14 states, 14 states have (on average 4.357142857142857) internal successors, (61), 14 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:34:02,816 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:34:02,816 INFO L93 Difference]: Finished difference Result 632 states and 806 transitions. [2024-11-08 14:34:02,816 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-08 14:34:02,816 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.357142857142857) internal successors, (61), 14 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 98 [2024-11-08 14:34:02,817 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:34:02,819 INFO L225 Difference]: With dead ends: 632 [2024-11-08 14:34:02,819 INFO L226 Difference]: Without dead ends: 537 [2024-11-08 14:34:02,821 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 238 GetRequests, 217 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2024-11-08 14:34:02,822 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 174 mSDsluCounter, 198 mSDsCounter, 0 mSdLazyCounter, 150 mSolverCounterSat, 63 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 174 SdHoareTripleChecker+Valid, 234 SdHoareTripleChecker+Invalid, 213 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 63 IncrementalHoareTripleChecker+Valid, 150 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-08 14:34:02,823 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [174 Valid, 234 Invalid, 213 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [63 Valid, 150 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-08 14:34:02,823 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 537 states. [2024-11-08 14:34:02,952 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 537 to 516. [2024-11-08 14:34:02,953 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 516 states, 337 states have (on average 1.2166172106824926) internal successors, (410), 361 states have internal predecessors, (410), 120 states have call successors, (120), 58 states have call predecessors, (120), 58 states have return successors, (115), 96 states have call predecessors, (115), 115 states have call successors, (115) [2024-11-08 14:34:02,956 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 516 states to 516 states and 645 transitions. [2024-11-08 14:34:02,957 INFO L78 Accepts]: Start accepts. Automaton has 516 states and 645 transitions. Word has length 98 [2024-11-08 14:34:02,957 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:34:02,957 INFO L471 AbstractCegarLoop]: Abstraction has 516 states and 645 transitions. [2024-11-08 14:34:02,957 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.357142857142857) internal successors, (61), 14 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:34:02,957 INFO L276 IsEmpty]: Start isEmpty. Operand 516 states and 645 transitions. [2024-11-08 14:34:02,958 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2024-11-08 14:34:02,959 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:34:02,959 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, 1, 1] [2024-11-08 14:34:02,976 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-11-08 14:34:03,159 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,SelfDestructingSolverStorable17 [2024-11-08 14:34:03,160 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:34:03,160 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:34:03,160 INFO L85 PathProgramCache]: Analyzing trace with hash 900247290, now seen corresponding path program 2 times [2024-11-08 14:34:03,160 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:34:03,160 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1243084128] [2024-11-08 14:34:03,160 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:34:03,160 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:34:03,197 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:34:03,200 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2103174131] [2024-11-08 14:34:03,200 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:34:03,201 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:34:03,201 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:34:03,202 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:34:03,204 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:34:03,284 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:34:03,284 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:34:03,290 INFO L255 TraceCheckSpWp]: Trace formula consists of 243 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-11-08 14:34:03,293 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:34:04,029 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 67 proven. 75 refuted. 0 times theorem prover too weak. 342 trivial. 0 not checked. [2024-11-08 14:34:04,029 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:34:04,760 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:34:04,760 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1243084128] [2024-11-08 14:34:04,760 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:34:04,760 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2103174131] [2024-11-08 14:34:04,760 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2103174131] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:34:04,760 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:34:04,760 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-11-08 14:34:04,760 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1366922842] [2024-11-08 14:34:04,760 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 14:34:04,761 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-08 14:34:04,761 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:34:04,761 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-08 14:34:04,762 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=416, Unknown=0, NotChecked=0, Total=506 [2024-11-08 14:34:04,762 INFO L87 Difference]: Start difference. First operand 516 states and 645 transitions. Second operand has 16 states, 15 states have (on average 2.2) internal successors, (33), 14 states have internal predecessors, (33), 8 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 7 states have call successors, (15) [2024-11-08 14:34:05,284 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:34:05,284 INFO L93 Difference]: Finished difference Result 604 states and 752 transitions. [2024-11-08 14:34:05,287 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-08 14:34:05,287 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.2) internal successors, (33), 14 states have internal predecessors, (33), 8 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 7 states have call successors, (15) Word has length 103 [2024-11-08 14:34:05,287 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:34:05,290 INFO L225 Difference]: With dead ends: 604 [2024-11-08 14:34:05,290 INFO L226 Difference]: Without dead ends: 526 [2024-11-08 14:34:05,290 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 74 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=108, Invalid=492, Unknown=0, NotChecked=0, Total=600 [2024-11-08 14:34:05,291 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 7 mSDsluCounter, 403 mSDsCounter, 0 mSdLazyCounter, 419 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 446 SdHoareTripleChecker+Invalid, 441 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 419 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-08 14:34:05,291 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 446 Invalid, 441 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 419 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-08 14:34:05,292 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 526 states. [2024-11-08 14:34:05,401 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 526 to 514. [2024-11-08 14:34:05,402 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 514 states, 338 states have (on average 1.2011834319526626) internal successors, (406), 359 states have internal predecessors, (406), 115 states have call successors, (115), 60 states have call predecessors, (115), 60 states have return successors, (111), 94 states have call predecessors, (111), 111 states have call successors, (111) [2024-11-08 14:34:05,405 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 514 states to 514 states and 632 transitions. [2024-11-08 14:34:05,406 INFO L78 Accepts]: Start accepts. Automaton has 514 states and 632 transitions. Word has length 103 [2024-11-08 14:34:05,406 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:34:05,406 INFO L471 AbstractCegarLoop]: Abstraction has 514 states and 632 transitions. [2024-11-08 14:34:05,406 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.2) internal successors, (33), 14 states have internal predecessors, (33), 8 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 7 states have call successors, (15) [2024-11-08 14:34:05,406 INFO L276 IsEmpty]: Start isEmpty. Operand 514 states and 632 transitions. [2024-11-08 14:34:05,409 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2024-11-08 14:34:05,409 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:34:05,409 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:34:05,425 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:34:05,613 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:34:05,613 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:34:05,614 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:34:05,614 INFO L85 PathProgramCache]: Analyzing trace with hash -1093897416, now seen corresponding path program 1 times [2024-11-08 14:34:05,614 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:34:05,614 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [861782627] [2024-11-08 14:34:05,614 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:34:05,614 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:34:05,637 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:34:05,638 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [530482870] [2024-11-08 14:34:05,639 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:34:05,639 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:34:05,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:34:05,641 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:34:05,644 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:34:05,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:05,714 INFO L255 TraceCheckSpWp]: Trace formula consists of 239 conjuncts, 48 conjuncts are in the unsatisfiable core [2024-11-08 14:34:05,715 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:34:06,885 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 58 proven. 84 refuted. 0 times theorem prover too weak. 342 trivial. 0 not checked. [2024-11-08 14:34:06,885 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:34:08,478 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:34:08,478 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [861782627] [2024-11-08 14:34:08,478 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:34:08,478 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [530482870] [2024-11-08 14:34:08,478 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [530482870] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:34:08,478 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-08 14:34:08,478 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-11-08 14:34:08,478 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [621155303] [2024-11-08 14:34:08,479 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-08 14:34:08,479 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-08 14:34:08,479 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:34:08,479 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-08 14:34:08,480 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=478, Unknown=0, NotChecked=0, Total=600 [2024-11-08 14:34:08,480 INFO L87 Difference]: Start difference. First operand 514 states and 632 transitions. Second operand has 16 states, 15 states have (on average 2.2) internal successors, (33), 14 states have internal predecessors, (33), 8 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 7 states have call successors, (15) [2024-11-08 14:34:09,169 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:34:09,170 INFO L93 Difference]: Finished difference Result 522 states and 640 transitions. [2024-11-08 14:34:09,170 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-08 14:34:09,170 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.2) internal successors, (33), 14 states have internal predecessors, (33), 8 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 7 states have call successors, (15) Word has length 103 [2024-11-08 14:34:09,171 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:34:09,173 INFO L225 Difference]: With dead ends: 522 [2024-11-08 14:34:09,173 INFO L226 Difference]: Without dead ends: 520 [2024-11-08 14:34:09,174 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 113 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 119 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=140, Invalid=562, Unknown=0, NotChecked=0, Total=702 [2024-11-08 14:34:09,175 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 5 mSDsluCounter, 383 mSDsCounter, 0 mSdLazyCounter, 424 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 423 SdHoareTripleChecker+Invalid, 440 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 424 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-08 14:34:09,175 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 423 Invalid, 440 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 424 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-08 14:34:09,180 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 520 states. [2024-11-08 14:34:09,296 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 520 to 512. [2024-11-08 14:34:09,297 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 512 states, 337 states have (on average 1.2017804154302671) internal successors, (405), 359 states have internal predecessors, (405), 114 states have call successors, (114), 60 states have call predecessors, (114), 60 states have return successors, (110), 92 states have call predecessors, (110), 110 states have call successors, (110) [2024-11-08 14:34:09,299 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 512 states to 512 states and 629 transitions. [2024-11-08 14:34:09,300 INFO L78 Accepts]: Start accepts. Automaton has 512 states and 629 transitions. Word has length 103 [2024-11-08 14:34:09,300 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:34:09,301 INFO L471 AbstractCegarLoop]: Abstraction has 512 states and 629 transitions. [2024-11-08 14:34:09,301 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.2) internal successors, (33), 14 states have internal predecessors, (33), 8 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 7 states have call successors, (15) [2024-11-08 14:34:09,301 INFO L276 IsEmpty]: Start isEmpty. Operand 512 states and 629 transitions. [2024-11-08 14:34:09,302 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2024-11-08 14:34:09,302 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:34:09,302 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, 1, 1] [2024-11-08 14:34:09,320 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2024-11-08 14:34:09,503 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:34:09,503 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:34:09,503 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:34:09,504 INFO L85 PathProgramCache]: Analyzing trace with hash -1090630811, now seen corresponding path program 2 times [2024-11-08 14:34:09,504 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:34:09,504 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [288955988] [2024-11-08 14:34:09,504 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:34:09,504 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:34:09,517 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,870 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:34:09,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,873 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-08 14:34:09,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,878 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 14:34:09,878 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,880 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-08 14:34:09,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,884 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-08 14:34:09,885 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,887 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-08 14:34:09,888 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,890 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-08 14:34:09,891 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,894 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-08 14:34:09,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,898 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-08 14:34:09,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,901 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-08 14:34:09,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,905 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-08 14:34:09,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,908 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 74 [2024-11-08 14:34:09,910 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,913 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 79 [2024-11-08 14:34:09,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,917 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 88 [2024-11-08 14:34:09,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,919 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 93 [2024-11-08 14:34:09,920 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,922 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 99 [2024-11-08 14:34:09,923 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:09,925 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:34:09,925 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:34:09,925 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [288955988] [2024-11-08 14:34:09,925 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [288955988] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:34:09,926 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [676673384] [2024-11-08 14:34:09,926 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 14:34:09,926 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:34:09,926 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:34:09,928 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:34:09,929 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-08 14:34:09,995 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 14:34:09,995 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:34:09,996 INFO L255 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-08 14:34:09,998 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:34:10,384 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:34:10,384 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:34:11,188 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:34:11,188 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [676673384] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:34:11,188 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:34:11,188 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 13, 12] total 26 [2024-11-08 14:34:11,188 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [637538529] [2024-11-08 14:34:11,188 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:34:11,189 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-11-08 14:34:11,189 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:34:11,190 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-11-08 14:34:11,190 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=559, Unknown=0, NotChecked=0, Total=650 [2024-11-08 14:34:11,190 INFO L87 Difference]: Start difference. First operand 512 states and 629 transitions. Second operand has 26 states, 26 states have (on average 2.8846153846153846) internal successors, (75), 23 states have internal predecessors, (75), 18 states have call successors, (47), 3 states have call predecessors, (47), 2 states have return successors, (45), 18 states have call predecessors, (45), 18 states have call successors, (45) [2024-11-08 14:34:11,709 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:34:11,709 INFO L93 Difference]: Finished difference Result 539 states and 669 transitions. [2024-11-08 14:34:11,710 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-08 14:34:11,710 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 2.8846153846153846) internal successors, (75), 23 states have internal predecessors, (75), 18 states have call successors, (47), 3 states have call predecessors, (47), 2 states have return successors, (45), 18 states have call predecessors, (45), 18 states have call successors, (45) Word has length 108 [2024-11-08 14:34:11,710 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:34:11,713 INFO L225 Difference]: With dead ends: 539 [2024-11-08 14:34:11,714 INFO L226 Difference]: Without dead ends: 483 [2024-11-08 14:34:11,714 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 263 GetRequests, 232 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 233 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=154, Invalid=902, Unknown=0, NotChecked=0, Total=1056 [2024-11-08 14:34:11,715 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 39 mSDsluCounter, 402 mSDsCounter, 0 mSdLazyCounter, 349 mSolverCounterSat, 47 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 447 SdHoareTripleChecker+Invalid, 396 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 349 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-08 14:34:11,715 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 447 Invalid, 396 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 349 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-08 14:34:11,716 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 483 states. [2024-11-08 14:34:11,842 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 483 to 468. [2024-11-08 14:34:11,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 468 states, 306 states have (on average 1.2156862745098038) internal successors, (372), 327 states have internal predecessors, (372), 107 states have call successors, (107), 54 states have call predecessors, (107), 54 states have return successors, (103), 86 states have call predecessors, (103), 103 states have call successors, (103) [2024-11-08 14:34:11,845 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 468 states to 468 states and 582 transitions. [2024-11-08 14:34:11,845 INFO L78 Accepts]: Start accepts. Automaton has 468 states and 582 transitions. Word has length 108 [2024-11-08 14:34:11,846 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:34:11,846 INFO L471 AbstractCegarLoop]: Abstraction has 468 states and 582 transitions. [2024-11-08 14:34:11,846 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 2.8846153846153846) internal successors, (75), 23 states have internal predecessors, (75), 18 states have call successors, (47), 3 states have call predecessors, (47), 2 states have return successors, (45), 18 states have call predecessors, (45), 18 states have call successors, (45) [2024-11-08 14:34:11,846 INFO L276 IsEmpty]: Start isEmpty. Operand 468 states and 582 transitions. [2024-11-08 14:34:11,847 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2024-11-08 14:34:11,847 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:34:11,847 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:34:11,864 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-08 14:34:12,051 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:34:12,052 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:34:12,052 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:34:12,052 INFO L85 PathProgramCache]: Analyzing trace with hash -353318641, now seen corresponding path program 1 times [2024-11-08 14:34:12,052 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:34:12,052 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [20918973] [2024-11-08 14:34:12,052 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:34:12,052 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:34:12,066 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,243 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:34:12,244 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,246 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-08 14:34:12,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,248 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 14:34:12,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,250 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-08 14:34:12,251 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,252 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-08 14:34:12,253 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,254 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-08 14:34:12,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,256 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-08 14:34:12,257 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,259 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-08 14:34:12,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,262 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-08 14:34:12,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,265 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-08 14:34:12,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,267 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-08 14:34:12,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,272 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-11-08 14:34:12,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,275 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-11-08 14:34:12,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,278 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-11-08 14:34:12,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,280 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 92 [2024-11-08 14:34:12,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,282 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 97 [2024-11-08 14:34:12,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,285 INFO L134 CoverageAnalysis]: Checked inductivity of 558 backedges. 32 proven. 46 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2024-11-08 14:34:12,285 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:34:12,285 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [20918973] [2024-11-08 14:34:12,285 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [20918973] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:34:12,285 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [791292698] [2024-11-08 14:34:12,285 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:34:12,286 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:34:12,286 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:34:12,287 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:34:12,294 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-08 14:34:12,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:12,363 INFO L255 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-08 14:34:12,365 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:34:12,485 INFO L134 CoverageAnalysis]: Checked inductivity of 558 backedges. 32 proven. 470 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2024-11-08 14:34:12,486 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:34:12,634 INFO L134 CoverageAnalysis]: Checked inductivity of 558 backedges. 32 proven. 46 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2024-11-08 14:34:12,634 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [791292698] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:34:12,634 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:34:12,634 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 10] total 18 [2024-11-08 14:34:12,634 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1294840656] [2024-11-08 14:34:12,634 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:34:12,635 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-08 14:34:12,635 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:34:12,636 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-08 14:34:12,636 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=125, Invalid=181, Unknown=0, NotChecked=0, Total=306 [2024-11-08 14:34:12,636 INFO L87 Difference]: Start difference. First operand 468 states and 582 transitions. Second operand has 18 states, 18 states have (on average 4.222222222222222) internal successors, (76), 18 states have internal predecessors, (76), 13 states have call successors, (49), 8 states have call predecessors, (49), 7 states have return successors, (48), 12 states have call predecessors, (48), 12 states have call successors, (48) [2024-11-08 14:34:13,128 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:34:13,129 INFO L93 Difference]: Finished difference Result 842 states and 1077 transitions. [2024-11-08 14:34:13,129 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-08 14:34:13,129 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 4.222222222222222) internal successors, (76), 18 states have internal predecessors, (76), 13 states have call successors, (49), 8 states have call predecessors, (49), 7 states have return successors, (48), 12 states have call predecessors, (48), 12 states have call successors, (48) Word has length 110 [2024-11-08 14:34:13,130 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:34:13,134 INFO L225 Difference]: With dead ends: 842 [2024-11-08 14:34:13,134 INFO L226 Difference]: Without dead ends: 796 [2024-11-08 14:34:13,134 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 268 GetRequests, 243 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=236, Invalid=466, Unknown=0, NotChecked=0, Total=702 [2024-11-08 14:34:13,135 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 241 mSDsluCounter, 200 mSDsCounter, 0 mSdLazyCounter, 196 mSolverCounterSat, 92 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 241 SdHoareTripleChecker+Valid, 231 SdHoareTripleChecker+Invalid, 288 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 92 IncrementalHoareTripleChecker+Valid, 196 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-08 14:34:13,135 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [241 Valid, 231 Invalid, 288 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [92 Valid, 196 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-08 14:34:13,136 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 796 states. [2024-11-08 14:34:13,301 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 796 to 781. [2024-11-08 14:34:13,303 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 781 states, 519 states have (on average 1.163776493256262) internal successors, (604), 551 states have internal predecessors, (604), 182 states have call successors, (182), 79 states have call predecessors, (182), 79 states have return successors, (174), 150 states have call predecessors, (174), 174 states have call successors, (174) [2024-11-08 14:34:13,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 781 states to 781 states and 960 transitions. [2024-11-08 14:34:13,307 INFO L78 Accepts]: Start accepts. Automaton has 781 states and 960 transitions. Word has length 110 [2024-11-08 14:34:13,307 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:34:13,307 INFO L471 AbstractCegarLoop]: Abstraction has 781 states and 960 transitions. [2024-11-08 14:34:13,308 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 4.222222222222222) internal successors, (76), 18 states have internal predecessors, (76), 13 states have call successors, (49), 8 states have call predecessors, (49), 7 states have return successors, (48), 12 states have call predecessors, (48), 12 states have call successors, (48) [2024-11-08 14:34:13,308 INFO L276 IsEmpty]: Start isEmpty. Operand 781 states and 960 transitions. [2024-11-08 14:34:13,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 122 [2024-11-08 14:34:13,309 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:34:13,309 INFO L215 NwaCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:34:13,326 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-11-08 14:34:13,513 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable21 [2024-11-08 14:34:13,514 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:34:13,514 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:34:13,514 INFO L85 PathProgramCache]: Analyzing trace with hash -1977071855, now seen corresponding path program 3 times [2024-11-08 14:34:13,514 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:34:13,514 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [159475637] [2024-11-08 14:34:13,514 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:34:13,514 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:34:13,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,670 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-08 14:34:13,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,673 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-08 14:34:13,674 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,676 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 14:34:13,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,678 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-08 14:34:13,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,680 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-08 14:34:13,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,682 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-08 14:34:13,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,685 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-08 14:34:13,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,687 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-08 14:34:13,688 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,689 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-08 14:34:13,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,691 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-08 14:34:13,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,693 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-08 14:34:13,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,695 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-11-08 14:34:13,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,697 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-11-08 14:34:13,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,700 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-11-08 14:34:13,701 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,703 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 92 [2024-11-08 14:34:13,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,707 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 97 [2024-11-08 14:34:13,708 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,710 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 106 [2024-11-08 14:34:13,711 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,713 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 111 [2024-11-08 14:34:13,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:34:13,716 INFO L134 CoverageAnalysis]: Checked inductivity of 700 backedges. 54 proven. 34 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2024-11-08 14:34:13,716 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:34:13,716 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [159475637] [2024-11-08 14:34:13,716 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [159475637] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:34:13,716 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1162136312] [2024-11-08 14:34:13,716 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 14:34:13,717 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:34:13,717 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:34:13,718 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:34:13,720 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-08 14:34:13,786 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-08 14:34:13,786 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:34:13,793 INFO L255 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-08 14:34:13,795 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:34:14,266 INFO L134 CoverageAnalysis]: Checked inductivity of 700 backedges. 164 proven. 47 refuted. 0 times theorem prover too weak. 489 trivial. 0 not checked. [2024-11-08 14:34:14,266 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:34:14,436 INFO L134 CoverageAnalysis]: Checked inductivity of 700 backedges. 134 proven. 2 refuted. 0 times theorem prover too weak. 564 trivial. 0 not checked. [2024-11-08 14:34:14,437 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1162136312] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:34:14,437 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:34:14,437 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 15, 8] total 24 [2024-11-08 14:34:14,437 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1679182298] [2024-11-08 14:34:14,437 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:34:14,437 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-08 14:34:14,437 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:34:14,438 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-08 14:34:14,438 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=482, Unknown=0, NotChecked=0, Total=552 [2024-11-08 14:34:14,438 INFO L87 Difference]: Start difference. First operand 781 states and 960 transitions. Second operand has 24 states, 20 states have (on average 3.6) internal successors, (72), 19 states have internal predecessors, (72), 14 states have call successors, (42), 4 states have call predecessors, (42), 2 states have return successors, (41), 13 states have call predecessors, (41), 11 states have call successors, (41) [2024-11-08 14:34:15,712 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:34:15,712 INFO L93 Difference]: Finished difference Result 947 states and 1138 transitions. [2024-11-08 14:34:15,712 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2024-11-08 14:34:15,712 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 20 states have (on average 3.6) internal successors, (72), 19 states have internal predecessors, (72), 14 states have call successors, (42), 4 states have call predecessors, (42), 2 states have return successors, (41), 13 states have call predecessors, (41), 11 states have call successors, (41) Word has length 121 [2024-11-08 14:34:15,713 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:34:15,717 INFO L225 Difference]: With dead ends: 947 [2024-11-08 14:34:15,717 INFO L226 Difference]: Without dead ends: 892 [2024-11-08 14:34:15,718 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 314 GetRequests, 268 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 464 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=423, Invalid=1833, Unknown=0, NotChecked=0, Total=2256 [2024-11-08 14:34:15,718 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 106 mSDsluCounter, 598 mSDsCounter, 0 mSdLazyCounter, 458 mSolverCounterSat, 100 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 109 SdHoareTripleChecker+Valid, 647 SdHoareTripleChecker+Invalid, 558 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 100 IncrementalHoareTripleChecker+Valid, 458 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-08 14:34:15,719 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [109 Valid, 647 Invalid, 558 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [100 Valid, 458 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-08 14:34:15,719 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 892 states. [2024-11-08 14:34:15,941 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 892 to 866. [2024-11-08 14:34:15,942 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 866 states, 588 states have (on average 1.1343537414965987) internal successors, (667), 605 states have internal predecessors, (667), 178 states have call successors, (178), 99 states have call predecessors, (178), 99 states have return successors, (171), 161 states have call predecessors, (171), 171 states have call successors, (171) [2024-11-08 14:34:15,945 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 866 states to 866 states and 1016 transitions. [2024-11-08 14:34:15,946 INFO L78 Accepts]: Start accepts. Automaton has 866 states and 1016 transitions. Word has length 121 [2024-11-08 14:34:15,946 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:34:15,946 INFO L471 AbstractCegarLoop]: Abstraction has 866 states and 1016 transitions. [2024-11-08 14:34:15,947 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 20 states have (on average 3.6) internal successors, (72), 19 states have internal predecessors, (72), 14 states have call successors, (42), 4 states have call predecessors, (42), 2 states have return successors, (41), 13 states have call predecessors, (41), 11 states have call successors, (41) [2024-11-08 14:34:15,947 INFO L276 IsEmpty]: Start isEmpty. Operand 866 states and 1016 transitions. [2024-11-08 14:34:15,948 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2024-11-08 14:34:15,948 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:34:15,948 INFO L215 NwaCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:34:15,964 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2024-11-08 14:34:16,152 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable22,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:34:16,153 INFO L396 AbstractCegarLoop]: === Iteration 24 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:34:16,153 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:34:16,153 INFO L85 PathProgramCache]: Analyzing trace with hash 488955713, now seen corresponding path program 4 times [2024-11-08 14:34:16,153 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:34:16,153 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1848624044] [2024-11-08 14:34:16,153 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:34:16,153 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:34:16,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:34:16,188 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1523911289] [2024-11-08 14:34:16,188 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-08 14:34:16,188 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:34:16,189 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:34:16,193 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 14:34:16,196 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-08 14:34:16,289 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-08 14:34:16,290 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 14:34:16,292 INFO L255 TraceCheckSpWp]: Trace formula consists of 293 conjuncts, 59 conjuncts are in the unsatisfiable core [2024-11-08 14:34:16,294 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:34:17,002 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 65 proven. 85 refuted. 0 times theorem prover too weak. 561 trivial. 0 not checked. [2024-11-08 14:34:17,002 INFO L311 TraceCheckSpWp]: Computing backward predicates...