./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 4a390ef5 Calling Ultimate with: /root/.sdkman/candidates/java/current/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 /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound50.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 436f0a1b9da8affd8e76edc25dee0cffff5a08ff489ec96067821d6a4548518b --- Real Ultimate output --- This is Ultimate 0.2.5-dev-4a390ef-m [2024-10-24 00:11:44,204 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-24 00:11:44,272 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-24 00:11:44,276 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-24 00:11:44,277 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-24 00:11:44,304 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-24 00:11:44,307 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-24 00:11:44,307 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-24 00:11:44,308 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-24 00:11:44,310 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-24 00:11:44,310 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-24 00:11:44,310 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-24 00:11:44,311 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-24 00:11:44,311 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-24 00:11:44,313 INFO L153 SettingsManager]: * Use SBE=true [2024-10-24 00:11:44,314 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-24 00:11:44,314 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-24 00:11:44,314 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-24 00:11:44,315 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-24 00:11:44,315 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-24 00:11:44,315 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-24 00:11:44,317 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-24 00:11:44,317 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-24 00:11:44,317 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-24 00:11:44,318 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-24 00:11:44,318 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-24 00:11:44,321 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-24 00:11:44,321 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-24 00:11:44,321 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-24 00:11:44,322 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-24 00:11:44,322 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-24 00:11:44,323 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-24 00:11:44,323 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-24 00:11:44,323 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-24 00:11:44,324 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-24 00:11:44,324 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-24 00:11:44,325 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-24 00:11:44,325 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-24 00:11:44,325 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-24 00:11:44,325 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-24 00:11:44,326 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-24 00:11:44,326 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-24 00:11:44,326 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 -> 436f0a1b9da8affd8e76edc25dee0cffff5a08ff489ec96067821d6a4548518b [2024-10-24 00:11:44,601 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-24 00:11:44,626 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-24 00:11:44,630 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-24 00:11:44,631 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-24 00:11:44,632 INFO L274 PluginConnector]: CDTParser initialized [2024-10-24 00:11:44,633 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound50.c [2024-10-24 00:11:46,179 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-24 00:11:46,391 INFO L384 CDTParser]: Found 1 translation units. [2024-10-24 00:11:46,392 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound50.c [2024-10-24 00:11:46,400 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/387fdef63/34eeb2120bf740c893b7873871ead219/FLAGb8a46660b [2024-10-24 00:11:46,762 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/387fdef63/34eeb2120bf740c893b7873871ead219 [2024-10-24 00:11:46,764 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-24 00:11:46,766 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-24 00:11:46,767 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-24 00:11:46,767 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-24 00:11:46,775 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-24 00:11:46,776 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.10 12:11:46" (1/1) ... [2024-10-24 00:11:46,778 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7528b55f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:46, skipping insertion in model container [2024-10-24 00:11:46,778 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.10 12:11:46" (1/1) ... [2024-10-24 00:11:46,800 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-24 00:11:47,015 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound50.c[490,503] [2024-10-24 00:11:47,047 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-24 00:11:47,063 INFO L200 MainTranslator]: Completed pre-run [2024-10-24 00:11:47,074 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound50.c[490,503] [2024-10-24 00:11:47,092 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-24 00:11:47,115 INFO L204 MainTranslator]: Completed translation [2024-10-24 00:11:47,115 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47 WrapperNode [2024-10-24 00:11:47,115 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-24 00:11:47,117 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-24 00:11:47,117 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-24 00:11:47,117 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-24 00:11:47,124 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47" (1/1) ... [2024-10-24 00:11:47,132 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47" (1/1) ... [2024-10-24 00:11:47,151 INFO L138 Inliner]: procedures = 14, calls = 14, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 94 [2024-10-24 00:11:47,154 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-24 00:11:47,155 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-24 00:11:47,155 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-24 00:11:47,155 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-24 00:11:47,167 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47" (1/1) ... [2024-10-24 00:11:47,167 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47" (1/1) ... [2024-10-24 00:11:47,173 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47" (1/1) ... [2024-10-24 00:11:47,188 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-10-24 00:11:47,192 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47" (1/1) ... [2024-10-24 00:11:47,193 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47" (1/1) ... [2024-10-24 00:11:47,197 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47" (1/1) ... [2024-10-24 00:11:47,209 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47" (1/1) ... [2024-10-24 00:11:47,210 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47" (1/1) ... [2024-10-24 00:11:47,214 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47" (1/1) ... [2024-10-24 00:11:47,216 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-24 00:11:47,220 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-24 00:11:47,220 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-24 00:11:47,220 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-24 00:11:47,221 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47" (1/1) ... [2024-10-24 00:11:47,228 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-24 00:11:47,239 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:47,257 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-10-24 00:11:47,260 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-10-24 00:11:47,313 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-24 00:11:47,313 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-10-24 00:11:47,314 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-10-24 00:11:47,314 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-24 00:11:47,314 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-24 00:11:47,314 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-24 00:11:47,314 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-24 00:11:47,316 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-24 00:11:47,375 INFO L238 CfgBuilder]: Building ICFG [2024-10-24 00:11:47,378 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-24 00:11:47,608 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-10-24 00:11:47,608 INFO L287 CfgBuilder]: Performing block encoding [2024-10-24 00:11:47,641 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-24 00:11:47,641 INFO L314 CfgBuilder]: Removed 3 assume(true) statements. [2024-10-24 00:11:47,642 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 12:11:47 BoogieIcfgContainer [2024-10-24 00:11:47,642 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-24 00:11:47,644 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-24 00:11:47,644 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-24 00:11:47,649 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-24 00:11:47,649 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.10 12:11:46" (1/3) ... [2024-10-24 00:11:47,650 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@67808b78 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.10 12:11:47, skipping insertion in model container [2024-10-24 00:11:47,650 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.10 12:11:47" (2/3) ... [2024-10-24 00:11:47,651 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@67808b78 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.10 12:11:47, skipping insertion in model container [2024-10-24 00:11:47,652 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.10 12:11:47" (3/3) ... [2024-10-24 00:11:47,653 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd3-ll_unwindbound50.c [2024-10-24 00:11:47,671 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-24 00:11:47,672 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-24 00:11:47,743 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-24 00:11:47,749 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;@94e7ff0, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-24 00:11:47,750 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-24 00:11:47,755 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 21 states have (on average 1.5714285714285714) internal successors, (33), 22 states have internal predecessors, (33), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-24 00:11:47,762 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-10-24 00:11:47,763 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:47,763 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:47,764 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:47,771 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:47,772 INFO L85 PathProgramCache]: Analyzing trace with hash -832436526, now seen corresponding path program 1 times [2024-10-24 00:11:47,781 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:47,781 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1009051308] [2024-10-24 00:11:47,782 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:47,782 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:47,944 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:48,005 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:11:48,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:48,022 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-24 00:11:48,024 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:48,030 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:48,032 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:48,033 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1009051308] [2024-10-24 00:11:48,037 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1009051308] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:11:48,037 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:11:48,037 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-24 00:11:48,039 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1394413347] [2024-10-24 00:11:48,039 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:11:48,048 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-24 00:11:48,052 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:48,088 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-24 00:11:48,088 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-24 00:11:48,091 INFO L87 Difference]: Start difference. First operand has 32 states, 21 states have (on average 1.5714285714285714) internal successors, (33), 22 states have internal predecessors, (33), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 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), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-24 00:11:48,123 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:48,126 INFO L93 Difference]: Finished difference Result 62 states and 98 transitions. [2024-10-24 00:11:48,127 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-24 00:11:48,129 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), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2024-10-24 00:11:48,129 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:48,135 INFO L225 Difference]: With dead ends: 62 [2024-10-24 00:11:48,138 INFO L226 Difference]: Without dead ends: 30 [2024-10-24 00:11:48,142 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-24 00:11:48,145 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:48,149 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 40 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:11:48,165 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2024-10-24 00:11:48,183 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2024-10-24 00:11:48,184 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 20 states have (on average 1.35) internal successors, (27), 21 states have internal predecessors, (27), 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-10-24 00:11:48,185 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 40 transitions. [2024-10-24 00:11:48,187 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 40 transitions. Word has length 17 [2024-10-24 00:11:48,187 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:48,187 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 40 transitions. [2024-10-24 00:11:48,187 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), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-24 00:11:48,187 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 40 transitions. [2024-10-24 00:11:48,188 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-10-24 00:11:48,188 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:48,188 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:48,189 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-24 00:11:48,189 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:48,190 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:48,190 INFO L85 PathProgramCache]: Analyzing trace with hash 958862887, now seen corresponding path program 1 times [2024-10-24 00:11:48,190 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:48,190 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [257387475] [2024-10-24 00:11:48,190 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:48,190 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:48,230 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:48,354 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:11:48,357 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:48,366 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-24 00:11:48,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:48,375 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:48,376 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:48,376 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [257387475] [2024-10-24 00:11:48,376 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [257387475] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:11:48,376 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:11:48,377 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-10-24 00:11:48,377 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1079483085] [2024-10-24 00:11:48,377 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:11:48,378 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-24 00:11:48,378 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:48,379 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-24 00:11:48,379 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-24 00:11:48,380 INFO L87 Difference]: Start difference. First operand 30 states and 40 transitions. Second operand has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:48,407 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:48,408 INFO L93 Difference]: Finished difference Result 39 states and 49 transitions. [2024-10-24 00:11:48,408 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-24 00:11:48,408 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2024-10-24 00:11:48,409 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:48,410 INFO L225 Difference]: With dead ends: 39 [2024-10-24 00:11:48,410 INFO L226 Difference]: Without dead ends: 32 [2024-10-24 00:11:48,410 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-24 00:11:48,411 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 5 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:48,412 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 100 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:11:48,413 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2024-10-24 00:11:48,423 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2024-10-24 00:11:48,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 23 states have internal predecessors, (29), 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-10-24 00:11:48,424 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 42 transitions. [2024-10-24 00:11:48,424 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 42 transitions. Word has length 18 [2024-10-24 00:11:48,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:48,428 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 42 transitions. [2024-10-24 00:11:48,429 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:48,429 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2024-10-24 00:11:48,429 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-10-24 00:11:48,429 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:48,430 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:48,430 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-24 00:11:48,430 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:48,431 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:48,431 INFO L85 PathProgramCache]: Analyzing trace with hash -359656705, now seen corresponding path program 1 times [2024-10-24 00:11:48,431 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:48,431 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2147373922] [2024-10-24 00:11:48,432 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:48,432 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:48,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:48,546 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:11:48,548 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:48,550 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-24 00:11:48,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:48,585 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-24 00:11:48,586 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:48,586 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2147373922] [2024-10-24 00:11:48,586 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2147373922] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:11:48,586 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:11:48,586 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-24 00:11:48,587 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [440337040] [2024-10-24 00:11:48,587 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:11:48,587 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-24 00:11:48,587 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:48,588 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-24 00:11:48,590 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:11:48,590 INFO L87 Difference]: Start difference. First operand 32 states and 42 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:48,734 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:48,734 INFO L93 Difference]: Finished difference Result 52 states and 70 transitions. [2024-10-24 00:11:48,737 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-24 00:11:48,737 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2024-10-24 00:11:48,738 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:48,738 INFO L225 Difference]: With dead ends: 52 [2024-10-24 00:11:48,739 INFO L226 Difference]: Without dead ends: 45 [2024-10-24 00:11:48,739 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-10-24 00:11:48,741 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 45 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:48,742 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 130 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:11:48,744 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-10-24 00:11:48,755 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 33. [2024-10-24 00:11:48,755 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 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-10-24 00:11:48,756 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2024-10-24 00:11:48,758 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 19 [2024-10-24 00:11:48,758 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:48,758 INFO L471 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2024-10-24 00:11:48,758 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:48,759 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2024-10-24 00:11:48,760 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-10-24 00:11:48,761 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:48,761 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:48,761 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-10-24 00:11:48,762 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:48,762 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:48,762 INFO L85 PathProgramCache]: Analyzing trace with hash -1735129581, now seen corresponding path program 1 times [2024-10-24 00:11:48,763 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:48,763 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [468228374] [2024-10-24 00:11:48,764 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:48,764 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:48,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:48,879 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:11:48,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:48,890 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-24 00:11:48,896 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:48,904 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:48,905 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:48,905 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [468228374] [2024-10-24 00:11:48,905 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [468228374] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:11:48,905 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:11:48,905 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-24 00:11:48,906 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1733272762] [2024-10-24 00:11:48,906 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:11:48,906 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-24 00:11:48,906 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:48,907 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-24 00:11:48,907 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:11:48,907 INFO L87 Difference]: Start difference. First operand 33 states and 43 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:48,960 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:48,962 INFO L93 Difference]: Finished difference Result 57 states and 77 transitions. [2024-10-24 00:11:48,962 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-24 00:11:48,963 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2024-10-24 00:11:48,963 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:48,963 INFO L225 Difference]: With dead ends: 57 [2024-10-24 00:11:48,963 INFO L226 Difference]: Without dead ends: 35 [2024-10-24 00:11:48,964 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:11:48,965 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 8 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:48,965 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 126 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:11:48,966 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2024-10-24 00:11:48,976 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2024-10-24 00:11:48,977 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 25 states have (on average 1.28) internal successors, (32), 26 states have internal predecessors, (32), 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-10-24 00:11:48,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 45 transitions. [2024-10-24 00:11:48,979 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 45 transitions. Word has length 24 [2024-10-24 00:11:48,979 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:48,979 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 45 transitions. [2024-10-24 00:11:48,980 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:48,980 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 45 transitions. [2024-10-24 00:11:48,981 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-10-24 00:11:48,982 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:48,982 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:48,982 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-10-24 00:11:48,983 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:48,983 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:48,984 INFO L85 PathProgramCache]: Analyzing trace with hash 150917056, now seen corresponding path program 1 times [2024-10-24 00:11:48,984 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:48,985 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [858111083] [2024-10-24 00:11:48,985 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:48,985 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:49,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:11:49,007 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1479190727] [2024-10-24 00:11:49,007 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:49,007 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:49,008 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:49,010 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-10-24 00:11:49,011 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-10-24 00:11:49,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:49,064 INFO L255 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-24 00:11:49,070 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:49,246 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:49,246 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 00:11:49,246 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:49,246 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [858111083] [2024-10-24 00:11:49,247 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:11:49,247 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1479190727] [2024-10-24 00:11:49,247 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1479190727] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:11:49,248 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:11:49,248 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 00:11:49,251 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1221437662] [2024-10-24 00:11:49,251 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:11:49,251 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:11:49,251 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:49,281 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:11:49,281 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:11:49,282 INFO L87 Difference]: Start difference. First operand 35 states and 45 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:49,336 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:49,337 INFO L93 Difference]: Finished difference Result 53 states and 70 transitions. [2024-10-24 00:11:49,338 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:11:49,338 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), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2024-10-24 00:11:49,338 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:49,339 INFO L225 Difference]: With dead ends: 53 [2024-10-24 00:11:49,339 INFO L226 Difference]: Without dead ends: 51 [2024-10-24 00:11:49,339 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:11:49,340 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 9 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:49,341 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 131 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:11:49,346 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2024-10-24 00:11:49,356 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 50. [2024-10-24 00:11:49,356 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 35 states have (on average 1.3142857142857143) internal successors, (46), 36 states have internal predecessors, (46), 11 states have call successors, (11), 3 states have call predecessors, (11), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-10-24 00:11:49,357 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 67 transitions. [2024-10-24 00:11:49,357 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 67 transitions. Word has length 24 [2024-10-24 00:11:49,358 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:49,358 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 67 transitions. [2024-10-24 00:11:49,358 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), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:49,359 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 67 transitions. [2024-10-24 00:11:49,360 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-10-24 00:11:49,360 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:49,360 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:49,374 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-24 00:11:49,562 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-10-24 00:11:49,562 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:49,563 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:49,563 INFO L85 PathProgramCache]: Analyzing trace with hash -1833090586, now seen corresponding path program 1 times [2024-10-24 00:11:49,563 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:49,563 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1916360152] [2024-10-24 00:11:49,563 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:49,564 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:49,586 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:49,701 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:11:49,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:49,711 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-24 00:11:49,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:49,721 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:49,722 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:49,722 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1916360152] [2024-10-24 00:11:49,722 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1916360152] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:11:49,723 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1948102075] [2024-10-24 00:11:49,724 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:49,724 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:49,724 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:49,727 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-10-24 00:11:49,729 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-10-24 00:11:49,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:49,780 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 00:11:49,782 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:49,851 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:49,851 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:49,953 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:49,953 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1948102075] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:11:49,954 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 00:11:49,954 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 12 [2024-10-24 00:11:49,954 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [108248404] [2024-10-24 00:11:49,954 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:49,958 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-10-24 00:11:49,959 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:49,959 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-24 00:11:49,960 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2024-10-24 00:11:49,960 INFO L87 Difference]: Start difference. First operand 50 states and 67 transitions. Second operand has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 12 states have internal predecessors, (35), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-24 00:11:50,178 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:50,179 INFO L93 Difference]: Finished difference Result 146 states and 192 transitions. [2024-10-24 00:11:50,179 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-10-24 00:11:50,179 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 12 states have internal predecessors, (35), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 25 [2024-10-24 00:11:50,180 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:50,182 INFO L225 Difference]: With dead ends: 146 [2024-10-24 00:11:50,182 INFO L226 Difference]: Without dead ends: 139 [2024-10-24 00:11:50,185 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 48 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2024-10-24 00:11:50,186 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 88 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 93 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 88 SdHoareTripleChecker+Valid, 220 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 93 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:50,186 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [88 Valid, 220 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 93 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:11:50,188 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2024-10-24 00:11:50,207 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 96. [2024-10-24 00:11:50,208 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 68 states have (on average 1.338235294117647) internal successors, (91), 70 states have internal predecessors, (91), 20 states have call successors, (20), 7 states have call predecessors, (20), 7 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2024-10-24 00:11:50,209 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 129 transitions. [2024-10-24 00:11:50,210 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 129 transitions. Word has length 25 [2024-10-24 00:11:50,211 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:50,211 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 129 transitions. [2024-10-24 00:11:50,211 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 12 states have internal predecessors, (35), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-24 00:11:50,211 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 129 transitions. [2024-10-24 00:11:50,212 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-10-24 00:11:50,212 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:50,213 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:50,227 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-10-24 00:11:50,416 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-10-24 00:11:50,417 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:50,417 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:50,417 INFO L85 PathProgramCache]: Analyzing trace with hash -1010868448, now seen corresponding path program 1 times [2024-10-24 00:11:50,418 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:50,418 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2028398780] [2024-10-24 00:11:50,418 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:50,418 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:50,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:50,506 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:11:50,509 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:50,538 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-24 00:11:50,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:50,543 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-24 00:11:50,545 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:50,545 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2028398780] [2024-10-24 00:11:50,545 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2028398780] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:11:50,545 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1360235632] [2024-10-24 00:11:50,545 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:50,546 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:50,546 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:50,548 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-10-24 00:11:50,549 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-10-24 00:11:50,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:50,598 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-24 00:11:50,599 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:50,640 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-24 00:11:50,641 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:50,723 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-24 00:11:50,723 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1360235632] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:11:50,723 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 00:11:50,723 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2024-10-24 00:11:50,723 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [972159575] [2024-10-24 00:11:50,724 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:50,724 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-10-24 00:11:50,724 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:50,724 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-10-24 00:11:50,725 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-10-24 00:11:50,725 INFO L87 Difference]: Start difference. First operand 96 states and 129 transitions. Second operand has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-24 00:11:50,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:50,946 INFO L93 Difference]: Finished difference Result 182 states and 260 transitions. [2024-10-24 00:11:50,946 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-10-24 00:11:50,946 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 26 [2024-10-24 00:11:50,947 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:50,948 INFO L225 Difference]: With dead ends: 182 [2024-10-24 00:11:50,948 INFO L226 Difference]: Without dead ends: 170 [2024-10-24 00:11:50,949 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 50 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=55, Invalid=155, Unknown=0, NotChecked=0, Total=210 [2024-10-24 00:11:50,949 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 112 mSDsluCounter, 228 mSDsCounter, 0 mSdLazyCounter, 103 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 116 SdHoareTripleChecker+Valid, 275 SdHoareTripleChecker+Invalid, 144 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 103 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:50,950 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [116 Valid, 275 Invalid, 144 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 103 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:11:50,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 170 states. [2024-10-24 00:11:50,976 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 170 to 127. [2024-10-24 00:11:50,977 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 96 states have (on average 1.3541666666666667) internal successors, (130), 97 states have internal predecessors, (130), 23 states have call successors, (23), 7 states have call predecessors, (23), 7 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-10-24 00:11:50,978 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 175 transitions. [2024-10-24 00:11:50,979 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 175 transitions. Word has length 26 [2024-10-24 00:11:50,979 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:50,979 INFO L471 AbstractCegarLoop]: Abstraction has 127 states and 175 transitions. [2024-10-24 00:11:50,979 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-24 00:11:50,979 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 175 transitions. [2024-10-24 00:11:50,980 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-10-24 00:11:50,980 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:50,981 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:50,998 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-10-24 00:11:51,184 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:51,185 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:51,186 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:51,186 INFO L85 PathProgramCache]: Analyzing trace with hash 2130442992, now seen corresponding path program 1 times [2024-10-24 00:11:51,186 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:51,186 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [403927334] [2024-10-24 00:11:51,186 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:51,187 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:51,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:11:51,208 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [274971950] [2024-10-24 00:11:51,208 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:51,208 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:51,209 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:51,211 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-10-24 00:11:51,215 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-10-24 00:11:51,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:51,264 INFO L255 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-24 00:11:51,266 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:51,354 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:51,354 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 00:11:51,354 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:51,355 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [403927334] [2024-10-24 00:11:51,355 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:11:51,355 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [274971950] [2024-10-24 00:11:51,356 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [274971950] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:11:51,356 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:11:51,356 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 00:11:51,357 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1143059460] [2024-10-24 00:11:51,357 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:11:51,360 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:11:51,361 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:51,361 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:11:51,361 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:11:51,362 INFO L87 Difference]: Start difference. First operand 127 states and 175 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-24 00:11:51,423 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:51,424 INFO L93 Difference]: Finished difference Result 142 states and 189 transitions. [2024-10-24 00:11:51,424 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:11:51,425 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 29 [2024-10-24 00:11:51,425 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:51,426 INFO L225 Difference]: With dead ends: 142 [2024-10-24 00:11:51,426 INFO L226 Difference]: Without dead ends: 140 [2024-10-24 00:11:51,426 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:11:51,428 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 9 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:51,428 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 129 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:11:51,429 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2024-10-24 00:11:51,458 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 139. [2024-10-24 00:11:51,459 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 105 states have (on average 1.3238095238095238) internal successors, (139), 106 states have internal predecessors, (139), 23 states have call successors, (23), 10 states have call predecessors, (23), 10 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-10-24 00:11:51,460 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 184 transitions. [2024-10-24 00:11:51,463 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 184 transitions. Word has length 29 [2024-10-24 00:11:51,464 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:51,464 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 184 transitions. [2024-10-24 00:11:51,464 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-24 00:11:51,464 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 184 transitions. [2024-10-24 00:11:51,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-10-24 00:11:51,465 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:51,465 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:51,483 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-24 00:11:51,666 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:51,666 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:51,667 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:51,667 INFO L85 PathProgramCache]: Analyzing trace with hash 2110713919, now seen corresponding path program 1 times [2024-10-24 00:11:51,667 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:51,667 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1949703638] [2024-10-24 00:11:51,667 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:51,667 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:51,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:11:51,687 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [205292212] [2024-10-24 00:11:51,687 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:51,687 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:51,687 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:51,689 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-10-24 00:11:51,691 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-10-24 00:11:51,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:51,741 INFO L255 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-10-24 00:11:51,742 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:51,872 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:51,873 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:52,025 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:52,026 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:52,026 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1949703638] [2024-10-24 00:11:52,026 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:11:52,026 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [205292212] [2024-10-24 00:11:52,026 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [205292212] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:11:52,027 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:11:52,027 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2024-10-24 00:11:52,027 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1959338751] [2024-10-24 00:11:52,027 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:52,028 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-10-24 00:11:52,028 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:52,028 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-24 00:11:52,028 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-10-24 00:11:52,029 INFO L87 Difference]: Start difference. First operand 139 states and 184 transitions. Second operand has 8 states, 8 states have (on average 4.875) internal successors, (39), 7 states have internal predecessors, (39), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:52,212 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:52,212 INFO L93 Difference]: Finished difference Result 174 states and 236 transitions. [2024-10-24 00:11:52,213 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-24 00:11:52,213 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.875) internal successors, (39), 7 states have internal predecessors, (39), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 31 [2024-10-24 00:11:52,214 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:52,216 INFO L225 Difference]: With dead ends: 174 [2024-10-24 00:11:52,217 INFO L226 Difference]: Without dead ends: 172 [2024-10-24 00:11:52,218 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 52 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-10-24 00:11:52,218 INFO L432 NwaCegarLoop]: 56 mSDtfsCounter, 19 mSDsluCounter, 238 mSDsCounter, 0 mSdLazyCounter, 91 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 294 SdHoareTripleChecker+Invalid, 92 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 91 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:52,219 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 294 Invalid, 92 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 91 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-24 00:11:52,219 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2024-10-24 00:11:52,240 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 169. [2024-10-24 00:11:52,241 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 169 states, 126 states have (on average 1.3492063492063493) internal successors, (170), 127 states have internal predecessors, (170), 31 states have call successors, (31), 11 states have call predecessors, (31), 11 states have return successors, (30), 30 states have call predecessors, (30), 30 states have call successors, (30) [2024-10-24 00:11:52,242 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 231 transitions. [2024-10-24 00:11:52,243 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 231 transitions. Word has length 31 [2024-10-24 00:11:52,243 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:52,243 INFO L471 AbstractCegarLoop]: Abstraction has 169 states and 231 transitions. [2024-10-24 00:11:52,243 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.875) internal successors, (39), 7 states have internal predecessors, (39), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:52,243 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 231 transitions. [2024-10-24 00:11:52,244 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-10-24 00:11:52,244 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:52,245 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:52,263 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-10-24 00:11:52,449 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:52,450 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:52,450 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:52,450 INFO L85 PathProgramCache]: Analyzing trace with hash -363027956, now seen corresponding path program 1 times [2024-10-24 00:11:52,450 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:52,450 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1182644526] [2024-10-24 00:11:52,450 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:52,451 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:52,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:52,552 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:11:52,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:52,558 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-24 00:11:52,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:52,567 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:52,567 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:52,567 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1182644526] [2024-10-24 00:11:52,567 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1182644526] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:11:52,568 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:11:52,568 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-10-24 00:11:52,568 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [855196794] [2024-10-24 00:11:52,568 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:11:52,568 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-24 00:11:52,568 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:52,569 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-24 00:11:52,569 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2024-10-24 00:11:52,571 INFO L87 Difference]: Start difference. First operand 169 states and 231 transitions. Second operand has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 7 states have internal predecessors, (23), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:52,625 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:52,626 INFO L93 Difference]: Finished difference Result 236 states and 324 transitions. [2024-10-24 00:11:52,626 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-24 00:11:52,627 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 7 states have internal predecessors, (23), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 31 [2024-10-24 00:11:52,627 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:52,629 INFO L225 Difference]: With dead ends: 236 [2024-10-24 00:11:52,629 INFO L226 Difference]: Without dead ends: 169 [2024-10-24 00:11:52,630 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2024-10-24 00:11:52,632 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 10 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:52,633 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 151 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:11:52,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2024-10-24 00:11:52,654 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 169. [2024-10-24 00:11:52,654 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 169 states, 126 states have (on average 1.3412698412698412) internal successors, (169), 127 states have internal predecessors, (169), 31 states have call successors, (31), 11 states have call predecessors, (31), 11 states have return successors, (30), 30 states have call predecessors, (30), 30 states have call successors, (30) [2024-10-24 00:11:52,655 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 230 transitions. [2024-10-24 00:11:52,656 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 230 transitions. Word has length 31 [2024-10-24 00:11:52,656 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:52,656 INFO L471 AbstractCegarLoop]: Abstraction has 169 states and 230 transitions. [2024-10-24 00:11:52,656 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 7 states have internal predecessors, (23), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:52,657 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 230 transitions. [2024-10-24 00:11:52,657 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-10-24 00:11:52,657 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:52,657 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:52,658 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2024-10-24 00:11:52,658 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:52,658 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:52,659 INFO L85 PathProgramCache]: Analyzing trace with hash -242784896, now seen corresponding path program 1 times [2024-10-24 00:11:52,659 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:52,659 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1296858476] [2024-10-24 00:11:52,659 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:52,659 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:52,670 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:11:52,671 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1493439422] [2024-10-24 00:11:52,671 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:52,671 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:52,671 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:52,673 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-10-24 00:11:52,676 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-10-24 00:11:52,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:52,729 INFO L255 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 00:11:52,730 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:52,778 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-10-24 00:11:52,779 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 00:11:52,779 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:52,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1296858476] [2024-10-24 00:11:52,779 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:11:52,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1493439422] [2024-10-24 00:11:52,779 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1493439422] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:11:52,780 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:11:52,780 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 00:11:52,780 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [487408873] [2024-10-24 00:11:52,780 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:11:52,780 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:11:52,781 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:52,781 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:11:52,781 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:11:52,781 INFO L87 Difference]: Start difference. First operand 169 states and 230 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-24 00:11:52,853 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:52,854 INFO L93 Difference]: Finished difference Result 234 states and 330 transitions. [2024-10-24 00:11:52,854 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:11:52,855 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 34 [2024-10-24 00:11:52,855 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:52,857 INFO L225 Difference]: With dead ends: 234 [2024-10-24 00:11:52,857 INFO L226 Difference]: Without dead ends: 232 [2024-10-24 00:11:52,857 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:11:52,858 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 8 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:52,858 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 121 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:11:52,859 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 232 states. [2024-10-24 00:11:52,886 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 232 to 225. [2024-10-24 00:11:52,887 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 225 states, 159 states have (on average 1.371069182389937) internal successors, (218), 160 states have internal predecessors, (218), 51 states have call successors, (51), 14 states have call predecessors, (51), 14 states have return successors, (50), 50 states have call predecessors, (50), 50 states have call successors, (50) [2024-10-24 00:11:52,889 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 225 states to 225 states and 319 transitions. [2024-10-24 00:11:52,889 INFO L78 Accepts]: Start accepts. Automaton has 225 states and 319 transitions. Word has length 34 [2024-10-24 00:11:52,890 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:52,890 INFO L471 AbstractCegarLoop]: Abstraction has 225 states and 319 transitions. [2024-10-24 00:11:52,890 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-24 00:11:52,890 INFO L276 IsEmpty]: Start isEmpty. Operand 225 states and 319 transitions. [2024-10-24 00:11:52,891 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-10-24 00:11:52,891 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:52,891 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:52,911 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-10-24 00:11:53,094 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:53,095 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:53,095 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:53,095 INFO L85 PathProgramCache]: Analyzing trace with hash -568879, now seen corresponding path program 1 times [2024-10-24 00:11:53,095 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:53,095 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1120471064] [2024-10-24 00:11:53,095 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:53,096 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:53,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:11:53,109 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [404276161] [2024-10-24 00:11:53,109 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:53,109 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:53,109 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:53,111 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-10-24 00:11:53,112 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-10-24 00:11:53,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:53,162 INFO L255 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-10-24 00:11:53,164 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:53,432 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-24 00:11:53,432 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:53,491 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:53,491 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1120471064] [2024-10-24 00:11:53,491 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:11:53,491 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [404276161] [2024-10-24 00:11:53,491 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [404276161] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:11:53,491 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-24 00:11:53,492 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2024-10-24 00:11:53,492 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [307662407] [2024-10-24 00:11:53,492 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:53,492 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-10-24 00:11:53,492 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:53,493 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-10-24 00:11:53,493 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2024-10-24 00:11:53,493 INFO L87 Difference]: Start difference. First operand 225 states and 319 transitions. Second operand has 10 states, 10 states have (on average 2.9) internal successors, (29), 8 states have internal predecessors, (29), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-24 00:11:53,703 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:53,703 INFO L93 Difference]: Finished difference Result 237 states and 329 transitions. [2024-10-24 00:11:53,704 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-24 00:11:53,704 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 8 states have internal predecessors, (29), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Word has length 36 [2024-10-24 00:11:53,704 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:53,706 INFO L225 Difference]: With dead ends: 237 [2024-10-24 00:11:53,706 INFO L226 Difference]: Without dead ends: 235 [2024-10-24 00:11:53,706 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=170, Unknown=0, NotChecked=0, Total=210 [2024-10-24 00:11:53,707 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 68 mSDsluCounter, 211 mSDsCounter, 0 mSdLazyCounter, 171 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 253 SdHoareTripleChecker+Invalid, 192 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 171 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:53,707 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 253 Invalid, 192 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 171 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-24 00:11:53,708 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2024-10-24 00:11:53,729 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 233. [2024-10-24 00:11:53,730 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 233 states, 165 states have (on average 1.3575757575757577) internal successors, (224), 166 states have internal predecessors, (224), 51 states have call successors, (51), 16 states have call predecessors, (51), 16 states have return successors, (50), 50 states have call predecessors, (50), 50 states have call successors, (50) [2024-10-24 00:11:53,731 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 233 states to 233 states and 325 transitions. [2024-10-24 00:11:53,731 INFO L78 Accepts]: Start accepts. Automaton has 233 states and 325 transitions. Word has length 36 [2024-10-24 00:11:53,732 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:53,732 INFO L471 AbstractCegarLoop]: Abstraction has 233 states and 325 transitions. [2024-10-24 00:11:53,732 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 8 states have internal predecessors, (29), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-24 00:11:53,732 INFO L276 IsEmpty]: Start isEmpty. Operand 233 states and 325 transitions. [2024-10-24 00:11:53,733 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-10-24 00:11:53,733 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:53,733 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:53,754 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-10-24 00:11:53,937 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:53,938 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:53,938 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:53,938 INFO L85 PathProgramCache]: Analyzing trace with hash 895823024, now seen corresponding path program 1 times [2024-10-24 00:11:53,938 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:53,938 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1124240362] [2024-10-24 00:11:53,939 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:53,939 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:53,948 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:11:53,949 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [186375617] [2024-10-24 00:11:53,949 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:53,949 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:53,950 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:53,952 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-10-24 00:11:53,956 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-10-24 00:11:54,002 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:54,004 INFO L255 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-24 00:11:54,005 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:54,058 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-10-24 00:11:54,058 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-24 00:11:54,058 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:54,058 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1124240362] [2024-10-24 00:11:54,058 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:11:54,059 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [186375617] [2024-10-24 00:11:54,059 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [186375617] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:11:54,059 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:11:54,059 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 00:11:54,059 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1824444203] [2024-10-24 00:11:54,059 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:11:54,059 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:11:54,059 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:54,060 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:11:54,060 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:11:54,060 INFO L87 Difference]: Start difference. First operand 233 states and 325 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-24 00:11:54,133 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:54,133 INFO L93 Difference]: Finished difference Result 308 states and 453 transitions. [2024-10-24 00:11:54,134 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:11:54,134 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 39 [2024-10-24 00:11:54,134 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:54,137 INFO L225 Difference]: With dead ends: 308 [2024-10-24 00:11:54,137 INFO L226 Difference]: Without dead ends: 306 [2024-10-24 00:11:54,138 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:11:54,138 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 5 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:54,139 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 129 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:11:54,140 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 306 states. [2024-10-24 00:11:54,173 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 306 to 291. [2024-10-24 00:11:54,174 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 291 states, 186 states have (on average 1.3602150537634408) internal successors, (253), 196 states have internal predecessors, (253), 87 states have call successors, (87), 17 states have call predecessors, (87), 17 states have return successors, (86), 77 states have call predecessors, (86), 86 states have call successors, (86) [2024-10-24 00:11:54,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 291 states to 291 states and 426 transitions. [2024-10-24 00:11:54,176 INFO L78 Accepts]: Start accepts. Automaton has 291 states and 426 transitions. Word has length 39 [2024-10-24 00:11:54,176 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:54,177 INFO L471 AbstractCegarLoop]: Abstraction has 291 states and 426 transitions. [2024-10-24 00:11:54,177 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-24 00:11:54,177 INFO L276 IsEmpty]: Start isEmpty. Operand 291 states and 426 transitions. [2024-10-24 00:11:54,177 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-10-24 00:11:54,178 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:54,178 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:54,196 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-10-24 00:11:54,378 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-10-24 00:11:54,379 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:54,379 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:54,379 INFO L85 PathProgramCache]: Analyzing trace with hash 184539710, now seen corresponding path program 1 times [2024-10-24 00:11:54,379 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:54,379 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [184641241] [2024-10-24 00:11:54,379 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:54,379 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:54,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:54,532 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:11:54,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:54,536 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-24 00:11:54,537 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:54,540 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-10-24 00:11:54,540 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:54,540 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [184641241] [2024-10-24 00:11:54,541 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [184641241] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:11:54,541 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [792115732] [2024-10-24 00:11:54,541 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:54,541 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:54,541 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:54,543 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-10-24 00:11:54,544 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-10-24 00:11:54,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:54,614 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-24 00:11:54,616 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:54,661 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-10-24 00:11:54,661 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:54,743 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-10-24 00:11:54,744 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [792115732] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:11:54,744 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 00:11:54,744 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 7] total 14 [2024-10-24 00:11:54,744 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1360975084] [2024-10-24 00:11:54,744 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:54,745 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-10-24 00:11:54,745 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:54,745 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-10-24 00:11:54,746 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=113, Unknown=0, NotChecked=0, Total=182 [2024-10-24 00:11:54,746 INFO L87 Difference]: Start difference. First operand 291 states and 426 transitions. Second operand has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-24 00:11:54,996 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:54,996 INFO L93 Difference]: Finished difference Result 724 states and 1030 transitions. [2024-10-24 00:11:54,996 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-10-24 00:11:54,997 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 37 [2024-10-24 00:11:54,997 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:55,002 INFO L225 Difference]: With dead ends: 724 [2024-10-24 00:11:55,002 INFO L226 Difference]: Without dead ends: 574 [2024-10-24 00:11:55,003 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 71 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=112, Invalid=230, Unknown=0, NotChecked=0, Total=342 [2024-10-24 00:11:55,004 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 141 mSDsluCounter, 188 mSDsCounter, 0 mSdLazyCounter, 115 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 141 SdHoareTripleChecker+Valid, 230 SdHoareTripleChecker+Invalid, 152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 115 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:55,004 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [141 Valid, 230 Invalid, 152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 115 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:11:55,009 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 574 states. [2024-10-24 00:11:55,066 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 574 to 540. [2024-10-24 00:11:55,067 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 540 states, 356 states have (on average 1.300561797752809) internal successors, (463), 370 states have internal predecessors, (463), 142 states have call successors, (142), 41 states have call predecessors, (142), 41 states have return successors, (138), 128 states have call predecessors, (138), 138 states have call successors, (138) [2024-10-24 00:11:55,071 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 540 states to 540 states and 743 transitions. [2024-10-24 00:11:55,072 INFO L78 Accepts]: Start accepts. Automaton has 540 states and 743 transitions. Word has length 37 [2024-10-24 00:11:55,072 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:55,072 INFO L471 AbstractCegarLoop]: Abstraction has 540 states and 743 transitions. [2024-10-24 00:11:55,073 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-24 00:11:55,073 INFO L276 IsEmpty]: Start isEmpty. Operand 540 states and 743 transitions. [2024-10-24 00:11:55,093 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-10-24 00:11:55,094 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:55,094 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:55,110 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-10-24 00:11:55,294 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-10-24 00:11:55,295 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:55,295 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:55,295 INFO L85 PathProgramCache]: Analyzing trace with hash -1387261216, now seen corresponding path program 2 times [2024-10-24 00:11:55,295 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:55,295 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1806851196] [2024-10-24 00:11:55,295 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:55,296 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:55,303 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:55,341 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:11:55,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:55,343 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-24 00:11:55,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:55,345 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 19 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:55,345 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:55,346 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1806851196] [2024-10-24 00:11:55,346 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1806851196] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:11:55,346 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:11:55,346 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 00:11:55,346 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [273673296] [2024-10-24 00:11:55,346 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:11:55,347 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:11:55,347 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:55,347 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:11:55,347 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:11:55,347 INFO L87 Difference]: Start difference. First operand 540 states and 743 transitions. Second operand has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:55,483 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:55,484 INFO L93 Difference]: Finished difference Result 788 states and 1135 transitions. [2024-10-24 00:11:55,484 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-24 00:11:55,484 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 38 [2024-10-24 00:11:55,485 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:55,489 INFO L225 Difference]: With dead ends: 788 [2024-10-24 00:11:55,489 INFO L226 Difference]: Without dead ends: 643 [2024-10-24 00:11:55,490 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2024-10-24 00:11:55,491 INFO L432 NwaCegarLoop]: 51 mSDtfsCounter, 29 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:55,491 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 169 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:11:55,492 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 643 states. [2024-10-24 00:11:55,552 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 643 to 538. [2024-10-24 00:11:55,554 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 538 states, 358 states have (on average 1.3072625698324023) internal successors, (468), 372 states have internal predecessors, (468), 138 states have call successors, (138), 41 states have call predecessors, (138), 41 states have return successors, (134), 124 states have call predecessors, (134), 134 states have call successors, (134) [2024-10-24 00:11:55,556 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 538 states to 538 states and 740 transitions. [2024-10-24 00:11:55,557 INFO L78 Accepts]: Start accepts. Automaton has 538 states and 740 transitions. Word has length 38 [2024-10-24 00:11:55,558 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:55,558 INFO L471 AbstractCegarLoop]: Abstraction has 538 states and 740 transitions. [2024-10-24 00:11:55,558 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-24 00:11:55,558 INFO L276 IsEmpty]: Start isEmpty. Operand 538 states and 740 transitions. [2024-10-24 00:11:55,558 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-10-24 00:11:55,559 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:55,559 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:55,559 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14 [2024-10-24 00:11:55,559 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:55,559 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:55,560 INFO L85 PathProgramCache]: Analyzing trace with hash 869918208, now seen corresponding path program 1 times [2024-10-24 00:11:55,560 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:55,560 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [264377982] [2024-10-24 00:11:55,560 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:55,560 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:55,571 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:55,689 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:11:55,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:55,693 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-24 00:11:55,694 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:55,696 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 11 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:55,696 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:55,696 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [264377982] [2024-10-24 00:11:55,696 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [264377982] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:11:55,696 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1309692946] [2024-10-24 00:11:55,697 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:55,697 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:55,697 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:55,699 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-10-24 00:11:55,700 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-10-24 00:11:55,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:55,749 INFO L255 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-24 00:11:55,751 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:55,788 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 11 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:55,789 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:55,877 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 11 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-24 00:11:55,877 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1309692946] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:11:55,877 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 00:11:55,878 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-10-24 00:11:55,878 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [127388182] [2024-10-24 00:11:55,878 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:55,878 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-24 00:11:55,878 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:55,879 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-24 00:11:55,879 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=146, Unknown=0, NotChecked=0, Total=240 [2024-10-24 00:11:55,879 INFO L87 Difference]: Start difference. First operand 538 states and 740 transitions. Second operand has 16 states, 16 states have (on average 3.375) internal successors, (54), 16 states have internal predecessors, (54), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-24 00:11:56,235 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:11:56,235 INFO L93 Difference]: Finished difference Result 1162 states and 1624 transitions. [2024-10-24 00:11:56,236 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-10-24 00:11:56,236 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.375) internal successors, (54), 16 states have internal predecessors, (54), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 38 [2024-10-24 00:11:56,236 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:11:56,241 INFO L225 Difference]: With dead ends: 1162 [2024-10-24 00:11:56,241 INFO L226 Difference]: Without dead ends: 839 [2024-10-24 00:11:56,243 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 72 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 68 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=167, Invalid=339, Unknown=0, NotChecked=0, Total=506 [2024-10-24 00:11:56,244 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 186 mSDsluCounter, 257 mSDsCounter, 0 mSdLazyCounter, 147 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 186 SdHoareTripleChecker+Valid, 293 SdHoareTripleChecker+Invalid, 188 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 147 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-24 00:11:56,244 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [186 Valid, 293 Invalid, 188 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 147 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-24 00:11:56,245 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 839 states. [2024-10-24 00:11:56,346 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 839 to 802. [2024-10-24 00:11:56,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 802 states, 532 states have (on average 1.25) internal successors, (665), 554 states have internal predecessors, (665), 212 states have call successors, (212), 57 states have call predecessors, (212), 57 states have return successors, (206), 190 states have call predecessors, (206), 206 states have call successors, (206) [2024-10-24 00:11:56,351 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 802 states to 802 states and 1083 transitions. [2024-10-24 00:11:56,352 INFO L78 Accepts]: Start accepts. Automaton has 802 states and 1083 transitions. Word has length 38 [2024-10-24 00:11:56,353 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:11:56,353 INFO L471 AbstractCegarLoop]: Abstraction has 802 states and 1083 transitions. [2024-10-24 00:11:56,353 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.375) internal successors, (54), 16 states have internal predecessors, (54), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-10-24 00:11:56,353 INFO L276 IsEmpty]: Start isEmpty. Operand 802 states and 1083 transitions. [2024-10-24 00:11:56,354 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2024-10-24 00:11:56,354 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:11:56,354 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:11:56,372 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-10-24 00:11:56,558 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-10-24 00:11:56,559 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:11:56,559 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:11:56,559 INFO L85 PathProgramCache]: Analyzing trace with hash -263121925, now seen corresponding path program 1 times [2024-10-24 00:11:56,559 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:11:56,559 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [484096264] [2024-10-24 00:11:56,559 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:56,560 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:11:56,576 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:11:56,577 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [689533905] [2024-10-24 00:11:56,577 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:11:56,577 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:11:56,577 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:11:56,579 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-10-24 00:11:56,583 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-10-24 00:11:56,647 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:11:56,649 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-10-24 00:11:56,651 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:11:57,399 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 8 proven. 9 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-10-24 00:11:57,399 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:11:59,329 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 8 proven. 6 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-24 00:11:59,330 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:11:59,330 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [484096264] [2024-10-24 00:11:59,330 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:11:59,330 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [689533905] [2024-10-24 00:11:59,330 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [689533905] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:11:59,331 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:11:59,331 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-10-24 00:11:59,331 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [714533548] [2024-10-24 00:11:59,331 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:11:59,332 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-10-24 00:11:59,332 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:11:59,332 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-10-24 00:11:59,333 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=432, Unknown=0, NotChecked=0, Total=506 [2024-10-24 00:11:59,333 INFO L87 Difference]: Start difference. First operand 802 states and 1083 transitions. Second operand has 23 states, 21 states have (on average 2.4285714285714284) internal successors, (51), 20 states have internal predecessors, (51), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-10-24 00:12:04,380 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-24 00:12:08,318 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:12:08,318 INFO L93 Difference]: Finished difference Result 1217 states and 1722 transitions. [2024-10-24 00:12:08,319 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2024-10-24 00:12:08,319 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 2.4285714285714284) internal successors, (51), 20 states have internal predecessors, (51), 6 states have call successors, (13), 3 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 53 [2024-10-24 00:12:08,319 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:12:08,327 INFO L225 Difference]: With dead ends: 1217 [2024-10-24 00:12:08,327 INFO L226 Difference]: Without dead ends: 1195 [2024-10-24 00:12:08,328 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 83 SyntacticMatches, 0 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 743 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=548, Invalid=2532, Unknown=0, NotChecked=0, Total=3080 [2024-10-24 00:12:08,329 INFO L432 NwaCegarLoop]: 83 mSDtfsCounter, 323 mSDsluCounter, 1099 mSDsCounter, 0 mSdLazyCounter, 841 mSolverCounterSat, 177 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 331 SdHoareTripleChecker+Valid, 1182 SdHoareTripleChecker+Invalid, 1019 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 177 IncrementalHoareTripleChecker+Valid, 841 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.4s IncrementalHoareTripleChecker+Time [2024-10-24 00:12:08,329 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [331 Valid, 1182 Invalid, 1019 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [177 Valid, 841 Invalid, 1 Unknown, 0 Unchecked, 6.4s Time] [2024-10-24 00:12:08,330 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1195 states. [2024-10-24 00:12:08,516 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1195 to 884. [2024-10-24 00:12:08,518 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 884 states, 591 states have (on average 1.2538071065989849) internal successors, (741), 611 states have internal predecessors, (741), 231 states have call successors, (231), 61 states have call predecessors, (231), 61 states have return successors, (226), 211 states have call predecessors, (226), 226 states have call successors, (226) [2024-10-24 00:12:08,523 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 884 states to 884 states and 1198 transitions. [2024-10-24 00:12:08,525 INFO L78 Accepts]: Start accepts. Automaton has 884 states and 1198 transitions. Word has length 53 [2024-10-24 00:12:08,525 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:12:08,525 INFO L471 AbstractCegarLoop]: Abstraction has 884 states and 1198 transitions. [2024-10-24 00:12:08,525 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 2.4285714285714284) internal successors, (51), 20 states have internal predecessors, (51), 6 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-10-24 00:12:08,526 INFO L276 IsEmpty]: Start isEmpty. Operand 884 states and 1198 transitions. [2024-10-24 00:12:08,526 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-10-24 00:12:08,526 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:12:08,527 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:12:08,542 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-10-24 00:12:08,728 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-10-24 00:12:08,729 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:12:08,729 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:12:08,729 INFO L85 PathProgramCache]: Analyzing trace with hash -2029616726, now seen corresponding path program 1 times [2024-10-24 00:12:08,729 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:12:08,729 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1699321419] [2024-10-24 00:12:08,729 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:12:08,730 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:12:08,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:08,941 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:12:08,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:08,945 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-24 00:12:08,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:08,948 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-24 00:12:08,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:08,953 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-24 00:12:08,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:08,958 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-24 00:12:08,959 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:08,961 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-24 00:12:08,963 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:08,966 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 8 proven. 17 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-24 00:12:08,967 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:12:08,967 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1699321419] [2024-10-24 00:12:08,968 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1699321419] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-24 00:12:08,968 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1057555746] [2024-10-24 00:12:08,968 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:12:08,968 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:12:08,968 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:12:08,970 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-10-24 00:12:08,971 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-10-24 00:12:09,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:09,033 INFO L255 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-10-24 00:12:09,035 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:12:09,135 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 8 proven. 17 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-24 00:12:09,135 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:12:09,286 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 8 proven. 17 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-24 00:12:09,287 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1057555746] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:12:09,287 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-24 00:12:09,287 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9, 10] total 20 [2024-10-24 00:12:09,287 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1619568162] [2024-10-24 00:12:09,287 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-24 00:12:09,287 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-10-24 00:12:09,288 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:12:09,288 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-10-24 00:12:09,288 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=158, Invalid=222, Unknown=0, NotChecked=0, Total=380 [2024-10-24 00:12:09,288 INFO L87 Difference]: Start difference. First operand 884 states and 1198 transitions. Second operand has 20 states, 20 states have (on average 3.45) internal successors, (69), 20 states have internal predecessors, (69), 6 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2024-10-24 00:12:10,172 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:12:10,174 INFO L93 Difference]: Finished difference Result 1905 states and 2712 transitions. [2024-10-24 00:12:10,174 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2024-10-24 00:12:10,175 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 3.45) internal successors, (69), 20 states have internal predecessors, (69), 6 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) Word has length 59 [2024-10-24 00:12:10,175 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:12:10,186 INFO L225 Difference]: With dead ends: 1905 [2024-10-24 00:12:10,186 INFO L226 Difference]: Without dead ends: 1883 [2024-10-24 00:12:10,187 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 120 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 122 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=303, Invalid=567, Unknown=0, NotChecked=0, Total=870 [2024-10-24 00:12:10,188 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 355 mSDsluCounter, 293 mSDsCounter, 0 mSdLazyCounter, 178 mSolverCounterSat, 117 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 355 SdHoareTripleChecker+Valid, 330 SdHoareTripleChecker+Invalid, 295 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 117 IncrementalHoareTripleChecker+Valid, 178 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-24 00:12:10,188 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [355 Valid, 330 Invalid, 295 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [117 Valid, 178 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-24 00:12:10,190 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1883 states. [2024-10-24 00:12:10,616 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1883 to 1789. [2024-10-24 00:12:10,619 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1789 states, 1180 states have (on average 1.2923728813559323) internal successors, (1525), 1240 states have internal predecessors, (1525), 511 states have call successors, (511), 97 states have call predecessors, (511), 97 states have return successors, (502), 451 states have call predecessors, (502), 502 states have call successors, (502) [2024-10-24 00:12:10,629 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1789 states to 1789 states and 2538 transitions. [2024-10-24 00:12:10,632 INFO L78 Accepts]: Start accepts. Automaton has 1789 states and 2538 transitions. Word has length 59 [2024-10-24 00:12:10,633 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:12:10,633 INFO L471 AbstractCegarLoop]: Abstraction has 1789 states and 2538 transitions. [2024-10-24 00:12:10,633 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 3.45) internal successors, (69), 20 states have internal predecessors, (69), 6 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2024-10-24 00:12:10,633 INFO L276 IsEmpty]: Start isEmpty. Operand 1789 states and 2538 transitions. [2024-10-24 00:12:10,634 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2024-10-24 00:12:10,634 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:12:10,634 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 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, 1, 1] [2024-10-24 00:12:10,652 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-10-24 00:12:10,838 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-10-24 00:12:10,839 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:12:10,839 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:12:10,839 INFO L85 PathProgramCache]: Analyzing trace with hash -240119973, now seen corresponding path program 1 times [2024-10-24 00:12:10,839 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:12:10,839 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1759419766] [2024-10-24 00:12:10,839 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:12:10,839 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:12:10,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:10,895 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-24 00:12:10,896 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:10,897 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-24 00:12:10,898 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:10,899 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2024-10-24 00:12:10,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:10,902 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-10-24 00:12:10,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:10,906 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-24 00:12:10,907 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:10,908 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-10-24 00:12:10,910 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:10,913 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-10-24 00:12:10,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:10,915 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-10-24 00:12:10,916 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:10,918 INFO L134 CoverageAnalysis]: Checked inductivity of 84 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2024-10-24 00:12:10,918 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:12:10,918 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1759419766] [2024-10-24 00:12:10,918 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1759419766] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-24 00:12:10,919 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-24 00:12:10,919 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-24 00:12:10,919 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2089714620] [2024-10-24 00:12:10,919 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:12:10,920 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:12:10,920 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:12:10,921 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:12:10,921 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-24 00:12:10,921 INFO L87 Difference]: Start difference. First operand 1789 states and 2538 transitions. Second operand has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-10-24 00:12:11,387 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:12:11,387 INFO L93 Difference]: Finished difference Result 3148 states and 4463 transitions. [2024-10-24 00:12:11,388 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:12:11,388 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 61 [2024-10-24 00:12:11,388 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:12:11,400 INFO L225 Difference]: With dead ends: 3148 [2024-10-24 00:12:11,400 INFO L226 Difference]: Without dead ends: 1883 [2024-10-24 00:12:11,406 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-24 00:12:11,407 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 3 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-24 00:12:11,407 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 126 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-24 00:12:11,409 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1883 states. [2024-10-24 00:12:11,858 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1883 to 1810. [2024-10-24 00:12:11,861 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1810 states, 1241 states have (on average 1.2957292506043514) internal successors, (1608), 1270 states have internal predecessors, (1608), 471 states have call successors, (471), 97 states have call predecessors, (471), 97 states have return successors, (462), 442 states have call predecessors, (462), 462 states have call successors, (462) [2024-10-24 00:12:11,870 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1810 states to 1810 states and 2541 transitions. [2024-10-24 00:12:11,873 INFO L78 Accepts]: Start accepts. Automaton has 1810 states and 2541 transitions. Word has length 61 [2024-10-24 00:12:11,874 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:12:11,874 INFO L471 AbstractCegarLoop]: Abstraction has 1810 states and 2541 transitions. [2024-10-24 00:12:11,874 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-10-24 00:12:11,874 INFO L276 IsEmpty]: Start isEmpty. Operand 1810 states and 2541 transitions. [2024-10-24 00:12:11,875 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2024-10-24 00:12:11,875 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:12:11,875 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 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, 1, 1] [2024-10-24 00:12:11,876 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18 [2024-10-24 00:12:11,876 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:12:11,876 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:12:11,876 INFO L85 PathProgramCache]: Analyzing trace with hash -421215721, now seen corresponding path program 1 times [2024-10-24 00:12:11,877 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:12:11,877 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [633917195] [2024-10-24 00:12:11,877 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:12:11,877 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:12:11,888 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:12:11,889 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1975685412] [2024-10-24 00:12:11,889 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:12:11,890 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:12:11,890 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:12:11,892 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-10-24 00:12:11,893 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-10-24 00:12:11,947 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:11,948 INFO L255 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-10-24 00:12:11,950 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:12:12,018 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2024-10-24 00:12:12,019 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:12:12,093 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2024-10-24 00:12:12,094 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:12:12,094 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [633917195] [2024-10-24 00:12:12,094 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:12:12,094 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1975685412] [2024-10-24 00:12:12,094 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1975685412] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-24 00:12:12,094 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-24 00:12:12,094 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-10-24 00:12:12,095 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1817718000] [2024-10-24 00:12:12,095 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-24 00:12:12,095 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-24 00:12:12,095 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:12:12,096 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-24 00:12:12,096 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-10-24 00:12:12,096 INFO L87 Difference]: Start difference. First operand 1810 states and 2541 transitions. Second operand has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-24 00:12:12,605 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:12:12,606 INFO L93 Difference]: Finished difference Result 1848 states and 2578 transitions. [2024-10-24 00:12:12,606 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-24 00:12:12,607 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 62 [2024-10-24 00:12:12,607 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:12:12,618 INFO L225 Difference]: With dead ends: 1848 [2024-10-24 00:12:12,618 INFO L226 Difference]: Without dead ends: 1846 [2024-10-24 00:12:12,620 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 115 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-10-24 00:12:12,621 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 5 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:12:12,621 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 122 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-24 00:12:12,627 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1846 states. [2024-10-24 00:12:13,046 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1846 to 1846. [2024-10-24 00:12:13,050 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1846 states, 1268 states have (on average 1.2878548895899053) internal successors, (1633), 1297 states have internal predecessors, (1633), 471 states have call successors, (471), 106 states have call predecessors, (471), 106 states have return successors, (462), 442 states have call predecessors, (462), 462 states have call successors, (462) [2024-10-24 00:12:13,063 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1846 states to 1846 states and 2566 transitions. [2024-10-24 00:12:13,066 INFO L78 Accepts]: Start accepts. Automaton has 1846 states and 2566 transitions. Word has length 62 [2024-10-24 00:12:13,067 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:12:13,067 INFO L471 AbstractCegarLoop]: Abstraction has 1846 states and 2566 transitions. [2024-10-24 00:12:13,067 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-24 00:12:13,068 INFO L276 IsEmpty]: Start isEmpty. Operand 1846 states and 2566 transitions. [2024-10-24 00:12:13,068 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2024-10-24 00:12:13,069 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:12:13,069 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 3, 3, 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, 1, 1, 1] [2024-10-24 00:12:13,088 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-10-24 00:12:13,269 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable19 [2024-10-24 00:12:13,269 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:12:13,270 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:12:13,270 INFO L85 PathProgramCache]: Analyzing trace with hash -1734545172, now seen corresponding path program 1 times [2024-10-24 00:12:13,270 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:12:13,270 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [342443493] [2024-10-24 00:12:13,270 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:12:13,270 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:12:13,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:12:13,284 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1693342387] [2024-10-24 00:12:13,285 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:12:13,285 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:12:13,285 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:12:13,288 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-10-24 00:12:13,289 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-10-24 00:12:13,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:13,350 INFO L255 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 44 conjuncts are in the unsatisfiable core [2024-10-24 00:12:13,352 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:12:13,907 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 10 proven. 19 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2024-10-24 00:12:13,907 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:12:15,170 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 10 proven. 16 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-10-24 00:12:15,171 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:12:15,171 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [342443493] [2024-10-24 00:12:15,171 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:12:15,171 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1693342387] [2024-10-24 00:12:15,171 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1693342387] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:12:15,171 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:12:15,171 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-10-24 00:12:15,172 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [744526117] [2024-10-24 00:12:15,172 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:12:15,172 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-10-24 00:12:15,172 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:12:15,173 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-10-24 00:12:15,173 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=432, Unknown=0, NotChecked=0, Total=506 [2024-10-24 00:12:15,173 INFO L87 Difference]: Start difference. First operand 1846 states and 2566 transitions. Second operand has 23 states, 23 states have (on average 2.652173913043478) internal successors, (61), 20 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) [2024-10-24 00:12:20,715 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-24 00:12:22,406 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.01s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-24 00:12:25,657 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:12:25,658 INFO L93 Difference]: Finished difference Result 2448 states and 3457 transitions. [2024-10-24 00:12:25,658 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2024-10-24 00:12:25,658 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.652173913043478) internal successors, (61), 20 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) Word has length 63 [2024-10-24 00:12:25,658 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:12:25,670 INFO L225 Difference]: With dead ends: 2448 [2024-10-24 00:12:25,671 INFO L226 Difference]: Without dead ends: 2446 [2024-10-24 00:12:25,672 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 103 SyntacticMatches, 1 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 416 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=417, Invalid=1653, Unknown=0, NotChecked=0, Total=2070 [2024-10-24 00:12:25,673 INFO L432 NwaCegarLoop]: 50 mSDtfsCounter, 262 mSDsluCounter, 559 mSDsCounter, 0 mSdLazyCounter, 469 mSolverCounterSat, 153 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 270 SdHoareTripleChecker+Valid, 609 SdHoareTripleChecker+Invalid, 623 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 153 IncrementalHoareTripleChecker+Valid, 469 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.0s IncrementalHoareTripleChecker+Time [2024-10-24 00:12:25,673 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [270 Valid, 609 Invalid, 623 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [153 Valid, 469 Invalid, 1 Unknown, 0 Unchecked, 7.0s Time] [2024-10-24 00:12:25,675 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2446 states. [2024-10-24 00:12:26,384 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2446 to 2316. [2024-10-24 00:12:26,388 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2316 states, 1610 states have (on average 1.3093167701863353) internal successors, (2108), 1647 states have internal predecessors, (2108), 591 states have call successors, (591), 114 states have call predecessors, (591), 114 states have return successors, (582), 554 states have call predecessors, (582), 582 states have call successors, (582) [2024-10-24 00:12:26,394 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2316 states to 2316 states and 3281 transitions. [2024-10-24 00:12:26,398 INFO L78 Accepts]: Start accepts. Automaton has 2316 states and 3281 transitions. Word has length 63 [2024-10-24 00:12:26,398 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:12:26,398 INFO L471 AbstractCegarLoop]: Abstraction has 2316 states and 3281 transitions. [2024-10-24 00:12:26,398 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.652173913043478) internal successors, (61), 20 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 6 states have call predecessors, (14), 6 states have call successors, (14) [2024-10-24 00:12:26,398 INFO L276 IsEmpty]: Start isEmpty. Operand 2316 states and 3281 transitions. [2024-10-24 00:12:26,400 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2024-10-24 00:12:26,400 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:12:26,400 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:12:26,419 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-10-24 00:12:26,601 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:12:26,601 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:12:26,602 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:12:26,602 INFO L85 PathProgramCache]: Analyzing trace with hash -2144187133, now seen corresponding path program 2 times [2024-10-24 00:12:26,602 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:12:26,602 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1074948714] [2024-10-24 00:12:26,602 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:12:26,602 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:12:26,618 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:12:26,619 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1553665131] [2024-10-24 00:12:26,619 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-24 00:12:26,619 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:12:26,620 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:12:26,622 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-10-24 00:12:26,625 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-10-24 00:12:26,691 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-24 00:12:26,691 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 00:12:26,697 INFO L255 TraceCheckSpWp]: Trace formula consists of 203 conjuncts, 38 conjuncts are in the unsatisfiable core [2024-10-24 00:12:26,699 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:12:26,916 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 10 proven. 35 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2024-10-24 00:12:26,917 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:12:27,006 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 32 proven. 10 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-10-24 00:12:27,006 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:12:27,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1074948714] [2024-10-24 00:12:27,007 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:12:27,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1553665131] [2024-10-24 00:12:27,007 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1553665131] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:12:27,007 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:12:27,007 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 13 [2024-10-24 00:12:27,007 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1596793284] [2024-10-24 00:12:27,008 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:12:27,008 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-10-24 00:12:27,008 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:12:27,009 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-10-24 00:12:27,009 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2024-10-24 00:12:27,009 INFO L87 Difference]: Start difference. First operand 2316 states and 3281 transitions. Second operand has 13 states, 13 states have (on average 5.230769230769231) internal successors, (68), 12 states have internal predecessors, (68), 5 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-10-24 00:12:28,207 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:12:28,209 INFO L93 Difference]: Finished difference Result 2758 states and 3906 transitions. [2024-10-24 00:12:28,209 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-10-24 00:12:28,209 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 5.230769230769231) internal successors, (68), 12 states have internal predecessors, (68), 5 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 65 [2024-10-24 00:12:28,210 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:12:28,223 INFO L225 Difference]: With dead ends: 2758 [2024-10-24 00:12:28,223 INFO L226 Difference]: Without dead ends: 2756 [2024-10-24 00:12:28,226 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 120 SyntacticMatches, 2 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=72, Invalid=270, Unknown=0, NotChecked=0, Total=342 [2024-10-24 00:12:28,227 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 88 mSDsluCounter, 291 mSDsCounter, 0 mSdLazyCounter, 198 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 92 SdHoareTripleChecker+Valid, 340 SdHoareTripleChecker+Invalid, 241 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 198 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-24 00:12:28,228 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [92 Valid, 340 Invalid, 241 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 198 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-24 00:12:28,230 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2756 states. [2024-10-24 00:12:29,055 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2756 to 2563. [2024-10-24 00:12:29,059 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2563 states, 1824 states have (on average 1.3135964912280702) internal successors, (2396), 1873 states have internal predecessors, (2396), 611 states have call successors, (611), 127 states have call predecessors, (611), 127 states have return successors, (602), 562 states have call predecessors, (602), 602 states have call successors, (602) [2024-10-24 00:12:29,066 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2563 states to 2563 states and 3609 transitions. [2024-10-24 00:12:29,073 INFO L78 Accepts]: Start accepts. Automaton has 2563 states and 3609 transitions. Word has length 65 [2024-10-24 00:12:29,073 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:12:29,073 INFO L471 AbstractCegarLoop]: Abstraction has 2563 states and 3609 transitions. [2024-10-24 00:12:29,073 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 5.230769230769231) internal successors, (68), 12 states have internal predecessors, (68), 5 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-10-24 00:12:29,073 INFO L276 IsEmpty]: Start isEmpty. Operand 2563 states and 3609 transitions. [2024-10-24 00:12:29,074 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-10-24 00:12:29,074 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:12:29,074 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 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, 1, 1, 1] [2024-10-24 00:12:29,091 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-10-24 00:12:29,275 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:12:29,275 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:12:29,276 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:12:29,276 INFO L85 PathProgramCache]: Analyzing trace with hash 1940891938, now seen corresponding path program 1 times [2024-10-24 00:12:29,276 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:12:29,276 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [235694999] [2024-10-24 00:12:29,276 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:12:29,277 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:12:29,299 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:12:29,300 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2127391570] [2024-10-24 00:12:29,300 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:12:29,300 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:12:29,300 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:12:29,302 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-10-24 00:12:29,305 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-10-24 00:12:29,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:29,366 INFO L255 TraceCheckSpWp]: Trace formula consists of 203 conjuncts, 55 conjuncts are in the unsatisfiable core [2024-10-24 00:12:29,368 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:12:30,069 INFO L134 CoverageAnalysis]: Checked inductivity of 145 backedges. 16 proven. 16 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2024-10-24 00:12:30,070 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:12:32,303 INFO L134 CoverageAnalysis]: Checked inductivity of 145 backedges. 16 proven. 13 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2024-10-24 00:12:32,303 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:12:32,303 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [235694999] [2024-10-24 00:12:32,303 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:12:32,303 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2127391570] [2024-10-24 00:12:32,303 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2127391570] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:12:32,304 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:12:32,304 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 12] total 25 [2024-10-24 00:12:32,304 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [964181596] [2024-10-24 00:12:32,304 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:12:32,304 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-10-24 00:12:32,305 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:12:32,305 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-10-24 00:12:32,305 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=512, Unknown=0, NotChecked=0, Total=600 [2024-10-24 00:12:32,307 INFO L87 Difference]: Start difference. First operand 2563 states and 3609 transitions. Second operand has 25 states, 23 states have (on average 2.4782608695652173) internal successors, (57), 22 states have internal predecessors, (57), 8 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2024-10-24 00:12:38,005 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:12:38,005 INFO L93 Difference]: Finished difference Result 2868 states and 4008 transitions. [2024-10-24 00:12:38,005 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2024-10-24 00:12:38,006 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 23 states have (on average 2.4782608695652173) internal successors, (57), 22 states have internal predecessors, (57), 8 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) Word has length 76 [2024-10-24 00:12:38,006 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:12:38,021 INFO L225 Difference]: With dead ends: 2868 [2024-10-24 00:12:38,021 INFO L226 Difference]: Without dead ends: 2861 [2024-10-24 00:12:38,025 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 127 SyntacticMatches, 0 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 867 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=737, Invalid=3045, Unknown=0, NotChecked=0, Total=3782 [2024-10-24 00:12:38,025 INFO L432 NwaCegarLoop]: 65 mSDtfsCounter, 263 mSDsluCounter, 827 mSDsCounter, 0 mSdLazyCounter, 809 mSolverCounterSat, 206 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 263 SdHoareTripleChecker+Valid, 892 SdHoareTripleChecker+Invalid, 1015 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 206 IncrementalHoareTripleChecker+Valid, 809 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2024-10-24 00:12:38,026 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [263 Valid, 892 Invalid, 1015 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [206 Valid, 809 Invalid, 0 Unknown, 0 Unchecked, 2.2s Time] [2024-10-24 00:12:38,029 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2861 states. [2024-10-24 00:12:38,913 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2861 to 2779. [2024-10-24 00:12:38,918 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2779 states, 1954 states have (on average 1.3070624360286591) internal successors, (2554), 2004 states have internal predecessors, (2554), 676 states have call successors, (676), 148 states have call predecessors, (676), 148 states have return successors, (670), 626 states have call predecessors, (670), 670 states have call successors, (670) [2024-10-24 00:12:38,925 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2779 states to 2779 states and 3900 transitions. [2024-10-24 00:12:38,928 INFO L78 Accepts]: Start accepts. Automaton has 2779 states and 3900 transitions. Word has length 76 [2024-10-24 00:12:38,928 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:12:38,929 INFO L471 AbstractCegarLoop]: Abstraction has 2779 states and 3900 transitions. [2024-10-24 00:12:38,929 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 23 states have (on average 2.4782608695652173) internal successors, (57), 22 states have internal predecessors, (57), 8 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (20), 6 states have call predecessors, (20), 6 states have call successors, (20) [2024-10-24 00:12:38,929 INFO L276 IsEmpty]: Start isEmpty. Operand 2779 states and 3900 transitions. [2024-10-24 00:12:38,930 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2024-10-24 00:12:38,930 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:12:38,931 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:12:38,947 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2024-10-24 00:12:39,134 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,SelfDestructingSolverStorable22 [2024-10-24 00:12:39,135 INFO L396 AbstractCegarLoop]: === Iteration 24 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:12:39,135 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:12:39,135 INFO L85 PathProgramCache]: Analyzing trace with hash -1286517375, now seen corresponding path program 1 times [2024-10-24 00:12:39,135 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:12:39,135 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1018702901] [2024-10-24 00:12:39,135 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:12:39,135 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:12:39,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:12:39,156 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [331951539] [2024-10-24 00:12:39,156 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:12:39,156 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:12:39,157 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:12:39,158 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-10-24 00:12:39,160 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-10-24 00:12:39,221 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-24 00:12:39,222 INFO L255 TraceCheckSpWp]: Trace formula consists of 239 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-10-24 00:12:39,224 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:12:39,446 INFO L134 CoverageAnalysis]: Checked inductivity of 233 backedges. 26 proven. 23 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2024-10-24 00:12:39,446 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:12:39,796 INFO L134 CoverageAnalysis]: Checked inductivity of 233 backedges. 29 proven. 17 refuted. 0 times theorem prover too weak. 187 trivial. 0 not checked. [2024-10-24 00:12:39,797 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:12:39,797 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1018702901] [2024-10-24 00:12:39,797 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:12:39,797 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [331951539] [2024-10-24 00:12:39,797 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [331951539] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:12:39,797 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:12:39,797 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-10-24 00:12:39,797 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1566348718] [2024-10-24 00:12:39,797 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:12:39,798 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-10-24 00:12:39,798 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:12:39,798 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-24 00:12:39,798 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=339, Unknown=0, NotChecked=0, Total=420 [2024-10-24 00:12:39,798 INFO L87 Difference]: Start difference. First operand 2779 states and 3900 transitions. Second operand has 21 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 18 states have internal predecessors, (56), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-10-24 00:12:42,154 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:12:42,155 INFO L93 Difference]: Finished difference Result 4052 states and 5924 transitions. [2024-10-24 00:12:42,155 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-10-24 00:12:42,156 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 18 states have internal predecessors, (56), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 91 [2024-10-24 00:12:42,156 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:12:42,178 INFO L225 Difference]: With dead ends: 4052 [2024-10-24 00:12:42,179 INFO L226 Difference]: Without dead ends: 4048 [2024-10-24 00:12:42,181 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 203 GetRequests, 165 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 306 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=345, Invalid=1215, Unknown=0, NotChecked=0, Total=1560 [2024-10-24 00:12:42,182 INFO L432 NwaCegarLoop]: 50 mSDtfsCounter, 183 mSDsluCounter, 409 mSDsCounter, 0 mSdLazyCounter, 333 mSolverCounterSat, 102 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 187 SdHoareTripleChecker+Valid, 459 SdHoareTripleChecker+Invalid, 435 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 102 IncrementalHoareTripleChecker+Valid, 333 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-10-24 00:12:42,182 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [187 Valid, 459 Invalid, 435 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [102 Valid, 333 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-10-24 00:12:42,186 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4048 states. [2024-10-24 00:12:43,863 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4048 to 3761. [2024-10-24 00:12:43,875 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3761 states, 2465 states have (on average 1.3509127789046653) internal successors, (3330), 2538 states have internal predecessors, (3330), 1128 states have call successors, (1128), 168 states have call predecessors, (1128), 167 states have return successors, (1122), 1054 states have call predecessors, (1122), 1122 states have call successors, (1122) [2024-10-24 00:12:43,886 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3761 states to 3761 states and 5580 transitions. [2024-10-24 00:12:43,890 INFO L78 Accepts]: Start accepts. Automaton has 3761 states and 5580 transitions. Word has length 91 [2024-10-24 00:12:43,890 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-24 00:12:43,890 INFO L471 AbstractCegarLoop]: Abstraction has 3761 states and 5580 transitions. [2024-10-24 00:12:43,891 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.6666666666666665) internal successors, (56), 18 states have internal predecessors, (56), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-10-24 00:12:43,891 INFO L276 IsEmpty]: Start isEmpty. Operand 3761 states and 5580 transitions. [2024-10-24 00:12:43,892 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2024-10-24 00:12:43,892 INFO L207 NwaCegarLoop]: Found error trace [2024-10-24 00:12:43,892 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-24 00:12:43,906 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-10-24 00:12:44,093 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable23,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:12:44,093 INFO L396 AbstractCegarLoop]: === Iteration 25 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-24 00:12:44,093 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-24 00:12:44,093 INFO L85 PathProgramCache]: Analyzing trace with hash 1994866066, now seen corresponding path program 2 times [2024-10-24 00:12:44,093 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-24 00:12:44,093 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1563477465] [2024-10-24 00:12:44,093 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-24 00:12:44,094 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-24 00:12:44,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-24 00:12:44,114 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1442171897] [2024-10-24 00:12:44,114 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-24 00:12:44,114 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-24 00:12:44,114 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-24 00:12:44,116 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-10-24 00:12:44,118 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-10-24 00:12:44,193 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-24 00:12:44,193 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-24 00:12:44,195 INFO L255 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 70 conjuncts are in the unsatisfiable core [2024-10-24 00:12:44,198 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-24 00:12:45,132 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 32 proven. 56 refuted. 0 times theorem prover too weak. 121 trivial. 0 not checked. [2024-10-24 00:12:45,132 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-24 00:12:49,307 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 38 proven. 47 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2024-10-24 00:12:49,308 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-24 00:12:49,308 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1563477465] [2024-10-24 00:12:49,308 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-24 00:12:49,308 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1442171897] [2024-10-24 00:12:49,308 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1442171897] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-24 00:12:49,308 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-24 00:12:49,308 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 16] total 33 [2024-10-24 00:12:49,308 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [45907111] [2024-10-24 00:12:49,308 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-24 00:12:49,309 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2024-10-24 00:12:49,309 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-24 00:12:49,310 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2024-10-24 00:12:49,310 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=160, Invalid=896, Unknown=0, NotChecked=0, Total=1056 [2024-10-24 00:12:49,310 INFO L87 Difference]: Start difference. First operand 3761 states and 5580 transitions. Second operand has 33 states, 33 states have (on average 2.606060606060606) internal successors, (86), 31 states have internal predecessors, (86), 9 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) [2024-10-24 00:12:53,629 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.22s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-24 00:12:58,907 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-24 00:13:11,082 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-24 00:13:11,083 INFO L93 Difference]: Finished difference Result 4856 states and 7066 transitions. [2024-10-24 00:13:11,083 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2024-10-24 00:13:11,083 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 33 states have (on average 2.606060606060606) internal successors, (86), 31 states have internal predecessors, (86), 9 states have call successors, (23), 3 states have call predecessors, (23), 3 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) Word has length 93 [2024-10-24 00:13:11,084 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-24 00:13:11,120 INFO L225 Difference]: With dead ends: 4856 [2024-10-24 00:13:11,120 INFO L226 Difference]: Without dead ends: 4854 [2024-10-24 00:13:11,124 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 246 GetRequests, 153 SyntacticMatches, 0 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2663 ImplicationChecksByTransitivity, 11.7s TimeCoverageRelationStatistics Valid=1897, Invalid=7033, Unknown=0, NotChecked=0, Total=8930 [2024-10-24 00:13:11,125 INFO L432 NwaCegarLoop]: 79 mSDtfsCounter, 533 mSDsluCounter, 1229 mSDsCounter, 0 mSdLazyCounter, 1380 mSolverCounterSat, 312 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 533 SdHoareTripleChecker+Valid, 1308 SdHoareTripleChecker+Invalid, 1693 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 312 IncrementalHoareTripleChecker+Valid, 1380 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.2s IncrementalHoareTripleChecker+Time [2024-10-24 00:13:11,125 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [533 Valid, 1308 Invalid, 1693 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [312 Valid, 1380 Invalid, 1 Unknown, 0 Unchecked, 10.2s Time] [2024-10-24 00:13:11,130 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4854 states.