./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3061b6dc Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd2-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 deef9b1f63fa90bdeace0bbb769d25578ef53bda95c70ad5e444555427b2b0e2 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-18 13:35:18,027 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-18 13:35:18,081 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-18 13:35:18,086 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-18 13:35:18,086 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-18 13:35:18,109 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-18 13:35:18,110 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-18 13:35:18,110 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-18 13:35:18,111 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-18 13:35:18,113 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-18 13:35:18,114 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-18 13:35:18,114 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-18 13:35:18,114 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-18 13:35:18,114 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-18 13:35:18,115 INFO L153 SettingsManager]: * Use SBE=true [2024-11-18 13:35:18,115 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-18 13:35:18,116 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-18 13:35:18,116 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-18 13:35:18,116 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-18 13:35:18,117 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-18 13:35:18,117 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-18 13:35:18,117 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-18 13:35:18,117 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-18 13:35:18,118 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-18 13:35:18,118 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-18 13:35:18,118 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-18 13:35:18,118 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-18 13:35:18,118 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-18 13:35:18,119 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-18 13:35:18,119 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-18 13:35:18,119 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-18 13:35:18,119 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-18 13:35:18,119 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:35:18,120 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-18 13:35:18,120 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-18 13:35:18,120 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-18 13:35:18,121 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-18 13:35:18,121 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-18 13:35:18,122 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-18 13:35:18,122 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-18 13:35:18,122 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-18 13:35:18,122 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-18 13:35:18,122 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 -> deef9b1f63fa90bdeace0bbb769d25578ef53bda95c70ad5e444555427b2b0e2 [2024-11-18 13:35:18,383 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-18 13:35:18,403 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-18 13:35:18,405 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-18 13:35:18,406 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-18 13:35:18,406 INFO L274 PluginConnector]: CDTParser initialized [2024-11-18 13:35:18,407 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound50.c [2024-11-18 13:35:19,794 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-18 13:35:19,937 INFO L384 CDTParser]: Found 1 translation units. [2024-11-18 13:35:19,938 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound50.c [2024-11-18 13:35:19,943 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/defe6abf2/02e0d163fd1747f18272633ecb21d5bc/FLAG57a259481 [2024-11-18 13:35:19,953 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/defe6abf2/02e0d163fd1747f18272633ecb21d5bc [2024-11-18 13:35:19,957 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-18 13:35:19,959 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-18 13:35:19,960 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-18 13:35:19,961 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-18 13:35:19,964 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-18 13:35:19,965 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:35:19" (1/1) ... [2024-11-18 13:35:19,966 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@221e0cb6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:19, skipping insertion in model container [2024-11-18 13:35:19,966 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:35:19" (1/1) ... [2024-11-18 13:35:19,986 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-18 13:35:20,158 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound50.c[490,503] [2024-11-18 13:35:20,177 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:35:20,183 INFO L200 MainTranslator]: Completed pre-run [2024-11-18 13:35:20,192 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound50.c[490,503] [2024-11-18 13:35:20,198 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:35:20,210 INFO L204 MainTranslator]: Completed translation [2024-11-18 13:35:20,211 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20 WrapperNode [2024-11-18 13:35:20,211 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-18 13:35:20,212 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-18 13:35:20,212 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-18 13:35:20,212 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-18 13:35:20,217 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20" (1/1) ... [2024-11-18 13:35:20,222 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20" (1/1) ... [2024-11-18 13:35:20,241 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 86 [2024-11-18 13:35:20,242 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-18 13:35:20,242 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-18 13:35:20,242 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-18 13:35:20,242 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-18 13:35:20,250 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20" (1/1) ... [2024-11-18 13:35:20,250 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20" (1/1) ... [2024-11-18 13:35:20,251 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20" (1/1) ... [2024-11-18 13:35:20,259 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-18 13:35:20,259 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20" (1/1) ... [2024-11-18 13:35:20,259 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20" (1/1) ... [2024-11-18 13:35:20,261 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20" (1/1) ... [2024-11-18 13:35:20,267 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20" (1/1) ... [2024-11-18 13:35:20,268 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20" (1/1) ... [2024-11-18 13:35:20,268 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20" (1/1) ... [2024-11-18 13:35:20,269 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-18 13:35:20,270 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-18 13:35:20,273 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-18 13:35:20,273 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-18 13:35:20,274 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20" (1/1) ... [2024-11-18 13:35:20,278 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:35:20,288 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:20,309 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-18 13:35:20,311 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-18 13:35:20,346 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-18 13:35:20,347 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-18 13:35:20,347 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-18 13:35:20,347 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-18 13:35:20,347 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-18 13:35:20,348 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-18 13:35:20,348 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-18 13:35:20,348 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-18 13:35:20,428 INFO L238 CfgBuilder]: Building ICFG [2024-11-18 13:35:20,430 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-18 13:35:20,612 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-11-18 13:35:20,613 INFO L287 CfgBuilder]: Performing block encoding [2024-11-18 13:35:20,624 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-18 13:35:20,624 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-18 13:35:20,625 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:35:20 BoogieIcfgContainer [2024-11-18 13:35:20,625 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-18 13:35:20,628 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-18 13:35:20,628 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-18 13:35:20,630 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-18 13:35:20,630 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.11 01:35:19" (1/3) ... [2024-11-18 13:35:20,631 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@cdf26f4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:35:20, skipping insertion in model container [2024-11-18 13:35:20,631 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:20" (2/3) ... [2024-11-18 13:35:20,631 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@cdf26f4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:35:20, skipping insertion in model container [2024-11-18 13:35:20,632 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:35:20" (3/3) ... [2024-11-18 13:35:20,632 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound50.c [2024-11-18 13:35:20,644 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-18 13:35:20,644 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-18 13:35:20,684 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-18 13:35:20,689 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;@b4479fc, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-18 13:35:20,690 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-18 13:35:20,692 INFO L276 IsEmpty]: Start isEmpty. Operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-18 13:35:20,697 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-18 13:35:20,697 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:20,698 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:20,698 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:20,701 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:20,702 INFO L85 PathProgramCache]: Analyzing trace with hash 1022199732, now seen corresponding path program 1 times [2024-11-18 13:35:20,708 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:20,708 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [326609622] [2024-11-18 13:35:20,708 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:20,708 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:20,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:20,831 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-18 13:35:20,832 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:20,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [326609622] [2024-11-18 13:35:20,833 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [326609622] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:20,833 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [986625064] [2024-11-18 13:35:20,834 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:20,834 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:20,834 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:20,836 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:20,841 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-18 13:35:20,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:20,919 INFO L255 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-18 13:35:20,922 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:20,933 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-18 13:35:20,934 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:35:20,934 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [986625064] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:35:20,934 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:35:20,934 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-11-18 13:35:20,936 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [790857716] [2024-11-18 13:35:20,937 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:35:20,939 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-18 13:35:20,940 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:20,958 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-18 13:35:20,959 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 13:35:20,960 INFO L87 Difference]: Start difference. First operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-18 13:35:20,976 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:20,977 INFO L93 Difference]: Finished difference Result 65 states and 104 transitions. [2024-11-18 13:35:20,977 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-18 13:35:20,978 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2024-11-18 13:35:20,978 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:20,983 INFO L225 Difference]: With dead ends: 65 [2024-11-18 13:35:20,983 INFO L226 Difference]: Without dead ends: 30 [2024-11-18 13:35:20,986 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 13:35:20,988 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:20,989 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:35:21,001 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2024-11-18 13:35:21,011 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2024-11-18 13:35:21,012 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 19 states have internal predecessors, (22), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-18 13:35:21,013 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 41 transitions. [2024-11-18 13:35:21,014 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 41 transitions. Word has length 28 [2024-11-18 13:35:21,014 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:21,014 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 41 transitions. [2024-11-18 13:35:21,014 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-18 13:35:21,014 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 41 transitions. [2024-11-18 13:35:21,015 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-18 13:35:21,015 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:21,016 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:21,028 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-18 13:35:21,216 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2024-11-18 13:35:21,217 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:21,217 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:21,217 INFO L85 PathProgramCache]: Analyzing trace with hash -455220980, now seen corresponding path program 1 times [2024-11-18 13:35:21,217 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:21,218 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1368876071] [2024-11-18 13:35:21,218 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:21,218 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:21,239 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:21,348 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-18 13:35:21,349 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:21,349 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1368876071] [2024-11-18 13:35:21,349 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1368876071] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:35:21,349 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:35:21,349 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-18 13:35:21,350 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [329999269] [2024-11-18 13:35:21,350 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:35:21,350 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-18 13:35:21,350 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:21,351 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-18 13:35:21,351 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-18 13:35:21,351 INFO L87 Difference]: Start difference. First operand 30 states and 41 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-18 13:35:21,365 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:21,366 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2024-11-18 13:35:21,366 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-18 13:35:21,366 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2024-11-18 13:35:21,366 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:21,367 INFO L225 Difference]: With dead ends: 40 [2024-11-18 13:35:21,367 INFO L226 Difference]: Without dead ends: 32 [2024-11-18 13:35:21,367 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-18 13:35:21,368 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 7 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:21,369 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 100 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:35:21,369 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2024-11-18 13:35:21,373 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2024-11-18 13:35:21,373 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-18 13:35:21,374 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 43 transitions. [2024-11-18 13:35:21,374 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 43 transitions. Word has length 29 [2024-11-18 13:35:21,375 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:21,375 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 43 transitions. [2024-11-18 13:35:21,375 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-18 13:35:21,375 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 43 transitions. [2024-11-18 13:35:21,376 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-18 13:35:21,376 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:21,376 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:21,376 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-18 13:35:21,376 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:21,377 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:21,377 INFO L85 PathProgramCache]: Analyzing trace with hash -1233535180, now seen corresponding path program 1 times [2024-11-18 13:35:21,377 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:21,377 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1744086284] [2024-11-18 13:35:21,377 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:21,377 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:21,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:21,529 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-18 13:35:21,530 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:21,530 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1744086284] [2024-11-18 13:35:21,530 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1744086284] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:21,530 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1459150013] [2024-11-18 13:35:21,530 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:21,530 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:21,531 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:21,532 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:21,533 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-18 13:35:21,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:21,578 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-18 13:35:21,580 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:21,678 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-18 13:35:21,678 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:35:21,679 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1459150013] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:35:21,679 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:35:21,679 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2024-11-18 13:35:21,679 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [431844059] [2024-11-18 13:35:21,679 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:35:21,679 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-18 13:35:21,680 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:21,680 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-18 13:35:21,680 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2024-11-18 13:35:21,681 INFO L87 Difference]: Start difference. First operand 32 states and 43 transitions. Second operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-18 13:35:21,747 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:21,747 INFO L93 Difference]: Finished difference Result 49 states and 67 transitions. [2024-11-18 13:35:21,748 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-18 13:35:21,748 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 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 30 [2024-11-18 13:35:21,748 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:21,749 INFO L225 Difference]: With dead ends: 49 [2024-11-18 13:35:21,749 INFO L226 Difference]: Without dead ends: 47 [2024-11-18 13:35:21,749 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2024-11-18 13:35:21,750 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 9 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:21,751 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 146 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:35:21,751 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-18 13:35:21,757 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 45. [2024-11-18 13:35:21,758 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 28 states have internal predecessors, (34), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-18 13:35:21,759 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 63 transitions. [2024-11-18 13:35:21,759 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 63 transitions. Word has length 30 [2024-11-18 13:35:21,759 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:21,759 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 63 transitions. [2024-11-18 13:35:21,760 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-18 13:35:21,760 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 63 transitions. [2024-11-18 13:35:21,760 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-18 13:35:21,760 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:21,761 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:21,775 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-18 13:35:21,961 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,SelfDestructingSolverStorable2 [2024-11-18 13:35:21,962 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:21,962 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:21,962 INFO L85 PathProgramCache]: Analyzing trace with hash -73118621, now seen corresponding path program 1 times [2024-11-18 13:35:21,963 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:21,963 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [892658015] [2024-11-18 13:35:21,963 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:21,964 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:21,990 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:35:21,992 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1911982289] [2024-11-18 13:35:21,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:21,993 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:21,993 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:22,000 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:22,005 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-18 13:35:22,051 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:22,052 INFO L255 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-18 13:35:22,053 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:22,104 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-18 13:35:22,104 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:35:22,104 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:22,105 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [892658015] [2024-11-18 13:35:22,105 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:35:22,106 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1911982289] [2024-11-18 13:35:22,106 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1911982289] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:35:22,106 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:35:22,106 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:35:22,106 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [645206852] [2024-11-18 13:35:22,106 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:35:22,107 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:35:22,107 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:22,107 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:35:22,107 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:35:22,108 INFO L87 Difference]: Start difference. First operand 45 states and 63 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-18 13:35:22,144 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:22,144 INFO L93 Difference]: Finished difference Result 66 states and 95 transitions. [2024-11-18 13:35:22,145 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:35:22,145 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2024-11-18 13:35:22,145 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:22,148 INFO L225 Difference]: With dead ends: 66 [2024-11-18 13:35:22,148 INFO L226 Difference]: Without dead ends: 64 [2024-11-18 13:35:22,148 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-18 13:35:22,149 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 5 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:22,149 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 139 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:35:22,150 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2024-11-18 13:35:22,157 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 55. [2024-11-18 13:35:22,158 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 33 states have (on average 1.303030303030303) internal successors, (43), 37 states have internal predecessors, (43), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 13 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-18 13:35:22,159 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 76 transitions. [2024-11-18 13:35:22,159 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 76 transitions. Word has length 32 [2024-11-18 13:35:22,159 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:22,159 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 76 transitions. [2024-11-18 13:35:22,159 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-18 13:35:22,160 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 76 transitions. [2024-11-18 13:35:22,160 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-18 13:35:22,160 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:22,160 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:22,173 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-18 13:35:22,361 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:22,361 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:22,361 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:22,361 INFO L85 PathProgramCache]: Analyzing trace with hash -910809492, now seen corresponding path program 1 times [2024-11-18 13:35:22,362 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:22,362 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [258739372] [2024-11-18 13:35:22,362 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:22,362 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:22,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:22,458 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-18 13:35:22,458 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:22,458 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [258739372] [2024-11-18 13:35:22,459 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [258739372] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:22,459 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1107764604] [2024-11-18 13:35:22,459 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:22,459 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:22,459 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:22,460 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:22,464 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-18 13:35:22,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:22,501 INFO L255 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-18 13:35:22,502 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:22,570 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-18 13:35:22,571 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:35:22,571 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1107764604] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:35:22,571 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:35:22,571 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2024-11-18 13:35:22,571 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [135331143] [2024-11-18 13:35:22,572 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:35:22,572 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:35:22,572 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:22,572 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:35:22,573 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2024-11-18 13:35:22,573 INFO L87 Difference]: Start difference. First operand 55 states and 76 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-18 13:35:22,610 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:22,610 INFO L93 Difference]: Finished difference Result 63 states and 83 transitions. [2024-11-18 13:35:22,610 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:35:22,610 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 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 35 [2024-11-18 13:35:22,611 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:22,611 INFO L225 Difference]: With dead ends: 63 [2024-11-18 13:35:22,612 INFO L226 Difference]: Without dead ends: 59 [2024-11-18 13:35:22,612 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2024-11-18 13:35:22,612 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 9 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:22,613 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 142 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:35:22,613 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2024-11-18 13:35:22,630 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2024-11-18 13:35:22,631 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 36 states have (on average 1.25) internal successors, (45), 39 states have internal predecessors, (45), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-18 13:35:22,632 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 76 transitions. [2024-11-18 13:35:22,632 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 76 transitions. Word has length 35 [2024-11-18 13:35:22,632 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:22,632 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 76 transitions. [2024-11-18 13:35:22,632 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-18 13:35:22,632 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 76 transitions. [2024-11-18 13:35:22,633 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-18 13:35:22,633 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:22,634 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:22,651 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-18 13:35:22,834 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:22,835 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:22,835 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:22,835 INFO L85 PathProgramCache]: Analyzing trace with hash 96561445, now seen corresponding path program 1 times [2024-11-18 13:35:22,836 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:22,836 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [554898168] [2024-11-18 13:35:22,836 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:22,836 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:22,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:22,919 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-18 13:35:22,920 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:22,920 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [554898168] [2024-11-18 13:35:22,920 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [554898168] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:35:22,920 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:35:22,920 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:35:22,920 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1983321895] [2024-11-18 13:35:22,920 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:35:22,922 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:35:22,922 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:22,923 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:35:22,923 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:35:22,923 INFO L87 Difference]: Start difference. First operand 58 states and 76 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-18 13:35:22,955 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:22,956 INFO L93 Difference]: Finished difference Result 84 states and 111 transitions. [2024-11-18 13:35:22,956 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:35:22,956 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 35 [2024-11-18 13:35:22,957 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:22,957 INFO L225 Difference]: With dead ends: 84 [2024-11-18 13:35:22,957 INFO L226 Difference]: Without dead ends: 58 [2024-11-18 13:35:22,958 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:35:22,958 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 10 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:22,958 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 100 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:35:22,959 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2024-11-18 13:35:22,968 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2024-11-18 13:35:22,969 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 36 states have (on average 1.2222222222222223) internal successors, (44), 39 states have internal predecessors, (44), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-18 13:35:22,969 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2024-11-18 13:35:22,970 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 35 [2024-11-18 13:35:22,970 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:22,970 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2024-11-18 13:35:22,970 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-18 13:35:22,970 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2024-11-18 13:35:22,971 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-18 13:35:22,971 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:22,971 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:22,971 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-18 13:35:22,971 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:22,972 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:22,972 INFO L85 PathProgramCache]: Analyzing trace with hash 2115683101, now seen corresponding path program 1 times [2024-11-18 13:35:22,972 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:22,972 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1559283864] [2024-11-18 13:35:22,972 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:22,972 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:22,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:35:22,990 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1201843183] [2024-11-18 13:35:22,990 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:22,991 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:22,991 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:22,992 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:22,993 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-18 13:35:23,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:23,036 INFO L255 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-18 13:35:23,039 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:23,199 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-18 13:35:23,199 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:35:23,200 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:23,200 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1559283864] [2024-11-18 13:35:23,200 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:35:23,200 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1201843183] [2024-11-18 13:35:23,201 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1201843183] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:35:23,201 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:35:23,201 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:35:23,201 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [991372701] [2024-11-18 13:35:23,202 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:35:23,202 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:35:23,202 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:23,202 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:35:23,203 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:35:23,203 INFO L87 Difference]: Start difference. First operand 58 states and 75 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-18 13:35:23,257 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:23,257 INFO L93 Difference]: Finished difference Result 65 states and 81 transitions. [2024-11-18 13:35:23,258 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:35:23,258 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 47 [2024-11-18 13:35:23,258 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:23,259 INFO L225 Difference]: With dead ends: 65 [2024-11-18 13:35:23,259 INFO L226 Difference]: Without dead ends: 63 [2024-11-18 13:35:23,259 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-18 13:35:23,260 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 6 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:23,260 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 130 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:35:23,261 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-11-18 13:35:23,268 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2024-11-18 13:35:23,268 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 39 states have (on average 1.205128205128205) internal successors, (47), 42 states have internal predecessors, (47), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-18 13:35:23,269 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 78 transitions. [2024-11-18 13:35:23,269 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 78 transitions. Word has length 47 [2024-11-18 13:35:23,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:23,269 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 78 transitions. [2024-11-18 13:35:23,270 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-18 13:35:23,270 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 78 transitions. [2024-11-18 13:35:23,271 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2024-11-18 13:35:23,271 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:23,271 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 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] [2024-11-18 13:35:23,283 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-18 13:35:23,471 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:23,472 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:23,472 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:23,473 INFO L85 PathProgramCache]: Analyzing trace with hash 559010241, now seen corresponding path program 1 times [2024-11-18 13:35:23,473 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:23,473 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [598254611] [2024-11-18 13:35:23,473 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:23,475 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:23,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:35:23,491 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2082075119] [2024-11-18 13:35:23,491 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:23,491 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:23,491 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:23,492 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:23,494 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-18 13:35:23,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:23,541 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-18 13:35:23,544 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:23,627 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-18 13:35:23,627 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:23,713 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2024-11-18 13:35:23,713 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:23,713 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [598254611] [2024-11-18 13:35:23,713 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:35:23,713 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2082075119] [2024-11-18 13:35:23,713 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2082075119] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:23,714 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:35:23,714 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-18 13:35:23,714 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [919605438] [2024-11-18 13:35:23,714 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:35:23,714 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:35:23,714 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:23,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:35:23,715 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-18 13:35:23,715 INFO L87 Difference]: Start difference. First operand 62 states and 78 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-18 13:35:23,759 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:23,759 INFO L93 Difference]: Finished difference Result 68 states and 83 transitions. [2024-11-18 13:35:23,760 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:35:23,760 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 55 [2024-11-18 13:35:23,760 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:23,762 INFO L225 Difference]: With dead ends: 68 [2024-11-18 13:35:23,762 INFO L226 Difference]: Without dead ends: 66 [2024-11-18 13:35:23,762 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 101 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-18 13:35:23,762 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 5 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:23,763 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 124 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:35:23,763 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2024-11-18 13:35:23,777 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 58. [2024-11-18 13:35:23,778 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 37 states have (on average 1.1891891891891893) internal successors, (44), 38 states have internal predecessors, (44), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-18 13:35:23,780 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 71 transitions. [2024-11-18 13:35:23,780 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 71 transitions. Word has length 55 [2024-11-18 13:35:23,780 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:23,782 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 71 transitions. [2024-11-18 13:35:23,782 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-18 13:35:23,783 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 71 transitions. [2024-11-18 13:35:23,783 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-11-18 13:35:23,783 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:23,784 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:23,796 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-18 13:35:23,984 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:23,985 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:23,985 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:23,985 INFO L85 PathProgramCache]: Analyzing trace with hash -879665460, now seen corresponding path program 1 times [2024-11-18 13:35:23,985 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:23,985 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [415774180] [2024-11-18 13:35:23,985 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:23,986 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:24,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:24,107 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-18 13:35:24,108 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:24,108 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [415774180] [2024-11-18 13:35:24,108 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [415774180] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:24,108 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [75404045] [2024-11-18 13:35:24,108 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:24,108 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:24,108 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:24,110 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:24,115 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-18 13:35:24,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:24,158 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-18 13:35:24,159 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:24,215 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-18 13:35:24,215 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:24,291 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-18 13:35:24,291 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [75404045] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:35:24,291 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:35:24,291 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2024-11-18 13:35:24,291 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [591218669] [2024-11-18 13:35:24,291 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:35:24,292 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-18 13:35:24,292 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:24,292 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-18 13:35:24,292 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-11-18 13:35:24,293 INFO L87 Difference]: Start difference. First operand 58 states and 71 transitions. Second operand has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2024-11-18 13:35:24,419 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:24,419 INFO L93 Difference]: Finished difference Result 211 states and 250 transitions. [2024-11-18 13:35:24,419 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-18 13:35:24,419 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 56 [2024-11-18 13:35:24,421 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:24,422 INFO L225 Difference]: With dead ends: 211 [2024-11-18 13:35:24,422 INFO L226 Difference]: Without dead ends: 203 [2024-11-18 13:35:24,422 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 108 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2024-11-18 13:35:24,423 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 72 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 72 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 85 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:24,423 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [72 Valid, 151 Invalid, 85 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:35:24,423 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2024-11-18 13:35:24,453 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 195. [2024-11-18 13:35:24,454 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 195 states, 125 states have (on average 1.192) internal successors, (149), 129 states have internal predecessors, (149), 44 states have call successors, (44), 25 states have call predecessors, (44), 25 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2024-11-18 13:35:24,455 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 195 states to 195 states and 233 transitions. [2024-11-18 13:35:24,456 INFO L78 Accepts]: Start accepts. Automaton has 195 states and 233 transitions. Word has length 56 [2024-11-18 13:35:24,456 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:24,456 INFO L471 AbstractCegarLoop]: Abstraction has 195 states and 233 transitions. [2024-11-18 13:35:24,457 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2024-11-18 13:35:24,457 INFO L276 IsEmpty]: Start isEmpty. Operand 195 states and 233 transitions. [2024-11-18 13:35:24,457 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2024-11-18 13:35:24,458 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:24,458 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:24,476 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-18 13:35:24,658 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:24,659 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:24,659 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:24,660 INFO L85 PathProgramCache]: Analyzing trace with hash -1506412172, now seen corresponding path program 1 times [2024-11-18 13:35:24,660 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:24,660 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1489828794] [2024-11-18 13:35:24,660 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:24,660 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:24,669 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:24,760 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-18 13:35:24,760 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:24,760 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1489828794] [2024-11-18 13:35:24,760 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1489828794] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:24,761 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1334749565] [2024-11-18 13:35:24,761 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:24,761 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:24,761 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:24,762 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:24,766 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-18 13:35:24,809 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:24,810 INFO L255 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-18 13:35:24,811 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:24,834 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-18 13:35:24,834 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:24,947 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-18 13:35:24,951 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1334749565] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:35:24,951 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:35:24,951 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2024-11-18 13:35:24,951 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1722621444] [2024-11-18 13:35:24,951 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:35:24,952 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-18 13:35:24,952 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:24,952 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-18 13:35:24,952 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-18 13:35:24,952 INFO L87 Difference]: Start difference. First operand 195 states and 233 transitions. Second operand has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-18 13:35:25,127 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:25,127 INFO L93 Difference]: Finished difference Result 279 states and 364 transitions. [2024-11-18 13:35:25,128 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-18 13:35:25,128 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 57 [2024-11-18 13:35:25,128 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:25,130 INFO L225 Difference]: With dead ends: 279 [2024-11-18 13:35:25,131 INFO L226 Difference]: Without dead ends: 259 [2024-11-18 13:35:25,131 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 109 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=134, Unknown=0, NotChecked=0, Total=182 [2024-11-18 13:35:25,132 INFO L432 NwaCegarLoop]: 48 mSDtfsCounter, 60 mSDsluCounter, 201 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:25,132 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 249 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:35:25,134 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states. [2024-11-18 13:35:25,177 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 235. [2024-11-18 13:35:25,178 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 235 states, 152 states have (on average 1.2236842105263157) internal successors, (186), 155 states have internal predecessors, (186), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2024-11-18 13:35:25,179 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 299 transitions. [2024-11-18 13:35:25,179 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 299 transitions. Word has length 57 [2024-11-18 13:35:25,179 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:25,179 INFO L471 AbstractCegarLoop]: Abstraction has 235 states and 299 transitions. [2024-11-18 13:35:25,179 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-18 13:35:25,179 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 299 transitions. [2024-11-18 13:35:25,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-11-18 13:35:25,180 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:25,180 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:25,193 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-18 13:35:25,384 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,SelfDestructingSolverStorable9 [2024-11-18 13:35:25,385 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:25,386 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:25,386 INFO L85 PathProgramCache]: Analyzing trace with hash -1869160295, now seen corresponding path program 1 times [2024-11-18 13:35:25,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:25,386 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [527502545] [2024-11-18 13:35:25,386 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:25,386 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:25,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:25,458 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-18 13:35:25,458 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:25,458 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [527502545] [2024-11-18 13:35:25,459 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [527502545] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:25,459 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1595525426] [2024-11-18 13:35:25,459 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:25,459 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:25,459 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:25,461 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:25,463 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-18 13:35:25,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:25,517 INFO L255 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-18 13:35:25,519 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:25,577 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-18 13:35:25,578 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:25,653 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-18 13:35:25,653 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1595525426] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:35:25,653 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:35:25,653 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2024-11-18 13:35:25,653 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [7903625] [2024-11-18 13:35:25,654 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:35:25,654 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-18 13:35:25,654 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:25,655 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-18 13:35:25,655 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-11-18 13:35:25,655 INFO L87 Difference]: Start difference. First operand 235 states and 299 transitions. Second operand has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2024-11-18 13:35:25,818 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:25,818 INFO L93 Difference]: Finished difference Result 344 states and 448 transitions. [2024-11-18 13:35:25,819 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-18 13:35:25,819 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 59 [2024-11-18 13:35:25,819 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:25,820 INFO L225 Difference]: With dead ends: 344 [2024-11-18 13:35:25,821 INFO L226 Difference]: Without dead ends: 248 [2024-11-18 13:35:25,822 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 114 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2024-11-18 13:35:25,822 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 79 mSDsluCounter, 137 mSDsCounter, 0 mSdLazyCounter, 69 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 175 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 69 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:25,822 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 175 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 69 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:35:25,823 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 248 states. [2024-11-18 13:35:25,847 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 248 to 244. [2024-11-18 13:35:25,848 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 244 states, 161 states have (on average 1.173913043478261) internal successors, (189), 164 states have internal predecessors, (189), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2024-11-18 13:35:25,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 244 states to 244 states and 302 transitions. [2024-11-18 13:35:25,850 INFO L78 Accepts]: Start accepts. Automaton has 244 states and 302 transitions. Word has length 59 [2024-11-18 13:35:25,850 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:25,850 INFO L471 AbstractCegarLoop]: Abstraction has 244 states and 302 transitions. [2024-11-18 13:35:25,851 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2024-11-18 13:35:25,851 INFO L276 IsEmpty]: Start isEmpty. Operand 244 states and 302 transitions. [2024-11-18 13:35:25,851 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2024-11-18 13:35:25,851 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:25,852 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:25,869 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-18 13:35:26,052 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:26,053 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:26,053 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:26,054 INFO L85 PathProgramCache]: Analyzing trace with hash 991223133, now seen corresponding path program 1 times [2024-11-18 13:35:26,054 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:26,054 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1106975166] [2024-11-18 13:35:26,054 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:26,054 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:26,068 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:35:26,068 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1888006793] [2024-11-18 13:35:26,069 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:26,069 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:26,069 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:26,070 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:26,072 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-18 13:35:26,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:26,129 INFO L255 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-18 13:35:26,131 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:26,355 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 19 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-11-18 13:35:26,355 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:26,446 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2024-11-18 13:35:26,446 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:26,446 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1106975166] [2024-11-18 13:35:26,447 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:35:26,447 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1888006793] [2024-11-18 13:35:26,447 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1888006793] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:35:26,447 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:35:26,447 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6] total 12 [2024-11-18 13:35:26,447 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1757784711] [2024-11-18 13:35:26,447 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:35:26,447 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-18 13:35:26,447 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:26,448 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-18 13:35:26,448 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2024-11-18 13:35:26,448 INFO L87 Difference]: Start difference. First operand 244 states and 302 transitions. Second operand has 12 states, 11 states have (on average 3.6363636363636362) internal successors, (40), 9 states have internal predecessors, (40), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-18 13:35:26,616 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:26,616 INFO L93 Difference]: Finished difference Result 283 states and 355 transitions. [2024-11-18 13:35:26,616 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-18 13:35:26,617 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 3.6363636363636362) internal successors, (40), 9 states have internal predecessors, (40), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) Word has length 64 [2024-11-18 13:35:26,617 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:26,618 INFO L225 Difference]: With dead ends: 283 [2024-11-18 13:35:26,618 INFO L226 Difference]: Without dead ends: 278 [2024-11-18 13:35:26,618 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 114 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=143, Unknown=0, NotChecked=0, Total=182 [2024-11-18 13:35:26,619 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 38 mSDsluCounter, 283 mSDsCounter, 0 mSdLazyCounter, 168 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 329 SdHoareTripleChecker+Invalid, 181 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 168 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:26,619 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 329 Invalid, 181 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 168 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:35:26,620 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 278 states. [2024-11-18 13:35:26,649 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 278 to 276. [2024-11-18 13:35:26,649 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 276 states, 183 states have (on average 1.185792349726776) internal successors, (217), 187 states have internal predecessors, (217), 65 states have call successors, (65), 27 states have call predecessors, (65), 27 states have return successors, (61), 61 states have call predecessors, (61), 61 states have call successors, (61) [2024-11-18 13:35:26,651 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 276 states to 276 states and 343 transitions. [2024-11-18 13:35:26,651 INFO L78 Accepts]: Start accepts. Automaton has 276 states and 343 transitions. Word has length 64 [2024-11-18 13:35:26,652 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:26,652 INFO L471 AbstractCegarLoop]: Abstraction has 276 states and 343 transitions. [2024-11-18 13:35:26,652 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 3.6363636363636362) internal successors, (40), 9 states have internal predecessors, (40), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-18 13:35:26,653 INFO L276 IsEmpty]: Start isEmpty. Operand 276 states and 343 transitions. [2024-11-18 13:35:26,653 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2024-11-18 13:35:26,653 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:26,653 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 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, 1] [2024-11-18 13:35:26,665 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-18 13:35:26,857 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,SelfDestructingSolverStorable11 [2024-11-18 13:35:26,858 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:26,858 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:26,858 INFO L85 PathProgramCache]: Analyzing trace with hash 1694315171, now seen corresponding path program 2 times [2024-11-18 13:35:26,858 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:26,858 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1875595137] [2024-11-18 13:35:26,859 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:35:26,859 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:26,871 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:35:26,871 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:35:26,871 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [176126753] [2024-11-18 13:35:26,871 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:35:26,872 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:26,872 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:26,873 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:26,874 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-18 13:35:26,918 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:35:26,919 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:35:26,923 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-18 13:35:26,925 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:27,204 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 17 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2024-11-18 13:35:27,204 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:27,446 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-18 13:35:27,446 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:27,446 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1875595137] [2024-11-18 13:35:27,446 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:35:27,446 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [176126753] [2024-11-18 13:35:27,446 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [176126753] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:35:27,446 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:35:27,447 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 15 [2024-11-18 13:35:27,447 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1633881028] [2024-11-18 13:35:27,447 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:35:27,447 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-18 13:35:27,447 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:27,448 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-18 13:35:27,448 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=172, Unknown=0, NotChecked=0, Total=210 [2024-11-18 13:35:27,448 INFO L87 Difference]: Start difference. First operand 276 states and 343 transitions. Second operand has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 13 states have internal predecessors, (40), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-18 13:35:28,403 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:28,403 INFO L93 Difference]: Finished difference Result 440 states and 595 transitions. [2024-11-18 13:35:28,403 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-18 13:35:28,404 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 13 states have internal predecessors, (40), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) Word has length 69 [2024-11-18 13:35:28,404 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:28,405 INFO L225 Difference]: With dead ends: 440 [2024-11-18 13:35:28,406 INFO L226 Difference]: Without dead ends: 438 [2024-11-18 13:35:28,406 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 121 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 161 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=198, Invalid=672, Unknown=0, NotChecked=0, Total=870 [2024-11-18 13:35:28,406 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 104 mSDsluCounter, 355 mSDsCounter, 0 mSdLazyCounter, 255 mSolverCounterSat, 82 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 109 SdHoareTripleChecker+Valid, 400 SdHoareTripleChecker+Invalid, 337 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 82 IncrementalHoareTripleChecker+Valid, 255 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:28,407 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [109 Valid, 400 Invalid, 337 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [82 Valid, 255 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-18 13:35:28,407 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 438 states. [2024-11-18 13:35:28,449 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 438 to 393. [2024-11-18 13:35:28,449 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 393 states, 258 states have (on average 1.244186046511628) internal successors, (321), 262 states have internal predecessors, (321), 101 states have call successors, (101), 33 states have call predecessors, (101), 33 states have return successors, (97), 97 states have call predecessors, (97), 97 states have call successors, (97) [2024-11-18 13:35:28,451 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 393 states to 393 states and 519 transitions. [2024-11-18 13:35:28,451 INFO L78 Accepts]: Start accepts. Automaton has 393 states and 519 transitions. Word has length 69 [2024-11-18 13:35:28,451 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:28,451 INFO L471 AbstractCegarLoop]: Abstraction has 393 states and 519 transitions. [2024-11-18 13:35:28,451 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 13 states have internal predecessors, (40), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-18 13:35:28,451 INFO L276 IsEmpty]: Start isEmpty. Operand 393 states and 519 transitions. [2024-11-18 13:35:28,452 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-18 13:35:28,452 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:28,452 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 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-11-18 13:35:28,467 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-18 13:35:28,656 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,SelfDestructingSolverStorable12 [2024-11-18 13:35:28,656 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:28,657 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:28,657 INFO L85 PathProgramCache]: Analyzing trace with hash -1349365539, now seen corresponding path program 3 times [2024-11-18 13:35:28,657 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:28,657 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [585050843] [2024-11-18 13:35:28,657 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:35:28,657 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:28,673 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-18 13:35:28,673 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:35:28,674 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1882416002] [2024-11-18 13:35:28,674 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:35:28,674 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:28,674 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:28,676 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:28,683 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-18 13:35:28,749 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-18 13:35:28,749 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:35:28,754 INFO L255 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 59 conjuncts are in the unsatisfiable core [2024-11-18 13:35:28,755 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:29,696 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 42 proven. 23 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-18 13:35:29,696 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:17,296 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:17,297 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [585050843] [2024-11-18 13:36:17,297 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:17,297 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1882416002] [2024-11-18 13:36:17,297 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1882416002] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:17,297 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:36:17,297 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-11-18 13:36:17,297 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2055935654] [2024-11-18 13:36:17,298 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:17,298 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-18 13:36:17,298 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:17,298 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-18 13:36:17,299 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=533, Unknown=3, NotChecked=0, Total=650 [2024-11-18 13:36:17,299 INFO L87 Difference]: Start difference. First operand 393 states and 519 transitions. Second operand has 16 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-11-18 13:36:17,974 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:17,974 INFO L93 Difference]: Finished difference Result 416 states and 539 transitions. [2024-11-18 13:36:17,975 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-18 13:36:17,975 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) Word has length 74 [2024-11-18 13:36:17,975 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:17,977 INFO L225 Difference]: With dead ends: 416 [2024-11-18 13:36:17,977 INFO L226 Difference]: Without dead ends: 412 [2024-11-18 13:36:17,977 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 15.1s TimeCoverageRelationStatistics Valid=167, Invalid=700, Unknown=3, NotChecked=0, Total=870 [2024-11-18 13:36:17,978 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 51 mSDsluCounter, 231 mSDsCounter, 0 mSdLazyCounter, 275 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 264 SdHoareTripleChecker+Invalid, 304 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 275 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:17,978 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 264 Invalid, 304 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 275 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-18 13:36:17,978 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 412 states. [2024-11-18 13:36:18,019 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 412 to 411. [2024-11-18 13:36:18,020 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 411 states, 272 states have (on average 1.2279411764705883) internal successors, (334), 275 states have internal predecessors, (334), 101 states have call successors, (101), 38 states have call predecessors, (101), 37 states have return successors, (97), 97 states have call predecessors, (97), 97 states have call successors, (97) [2024-11-18 13:36:18,021 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 411 states to 411 states and 532 transitions. [2024-11-18 13:36:18,022 INFO L78 Accepts]: Start accepts. Automaton has 411 states and 532 transitions. Word has length 74 [2024-11-18 13:36:18,022 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:18,022 INFO L471 AbstractCegarLoop]: Abstraction has 411 states and 532 transitions. [2024-11-18 13:36:18,022 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-11-18 13:36:18,022 INFO L276 IsEmpty]: Start isEmpty. Operand 411 states and 532 transitions. [2024-11-18 13:36:18,023 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2024-11-18 13:36:18,023 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:18,023 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 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, 1, 1] [2024-11-18 13:36:18,040 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-18 13:36:18,227 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,SelfDestructingSolverStorable13 [2024-11-18 13:36:18,228 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:18,228 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:18,228 INFO L85 PathProgramCache]: Analyzing trace with hash -484140586, now seen corresponding path program 1 times [2024-11-18 13:36:18,228 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:18,228 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [393716448] [2024-11-18 13:36:18,228 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:18,228 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:18,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:36:18,244 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1122947776] [2024-11-18 13:36:18,244 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:18,244 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:18,244 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:18,246 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:18,248 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-18 13:36:18,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:18,301 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-18 13:36:18,302 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:18,808 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 19 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2024-11-18 13:36:18,808 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:19,566 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2024-11-18 13:36:19,567 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:19,567 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [393716448] [2024-11-18 13:36:19,567 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:19,567 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1122947776] [2024-11-18 13:36:19,567 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1122947776] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:19,567 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:36:19,567 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-11-18 13:36:19,567 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1333777873] [2024-11-18 13:36:19,567 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:19,568 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-18 13:36:19,568 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:19,568 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-18 13:36:19,568 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2024-11-18 13:36:19,568 INFO L87 Difference]: Start difference. First operand 411 states and 532 transitions. Second operand has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 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-11-18 13:36:24,441 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-18 13:36:26,548 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:26,549 INFO L93 Difference]: Finished difference Result 671 states and 957 transitions. [2024-11-18 13:36:26,549 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-18 13:36:26,549 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 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 80 [2024-11-18 13:36:26,549 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:26,552 INFO L225 Difference]: With dead ends: 671 [2024-11-18 13:36:26,552 INFO L226 Difference]: Without dead ends: 660 [2024-11-18 13:36:26,552 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 139 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 262 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=296, Invalid=1264, Unknown=0, NotChecked=0, Total=1560 [2024-11-18 13:36:26,553 INFO L432 NwaCegarLoop]: 62 mSDtfsCounter, 106 mSDsluCounter, 712 mSDsCounter, 0 mSdLazyCounter, 588 mSolverCounterSat, 101 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 111 SdHoareTripleChecker+Valid, 774 SdHoareTripleChecker+Invalid, 690 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 101 IncrementalHoareTripleChecker+Valid, 588 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:26,553 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [111 Valid, 774 Invalid, 690 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [101 Valid, 588 Invalid, 1 Unknown, 0 Unchecked, 6.0s Time] [2024-11-18 13:36:26,554 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 660 states. [2024-11-18 13:36:26,679 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 660 to 636. [2024-11-18 13:36:26,680 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 636 states, 404 states have (on average 1.3242574257425743) internal successors, (535), 407 states have internal predecessors, (535), 192 states have call successors, (192), 39 states have call predecessors, (192), 39 states have return successors, (190), 189 states have call predecessors, (190), 190 states have call successors, (190) [2024-11-18 13:36:26,683 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 636 states to 636 states and 917 transitions. [2024-11-18 13:36:26,684 INFO L78 Accepts]: Start accepts. Automaton has 636 states and 917 transitions. Word has length 80 [2024-11-18 13:36:26,684 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:26,684 INFO L471 AbstractCegarLoop]: Abstraction has 636 states and 917 transitions. [2024-11-18 13:36:26,684 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 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-11-18 13:36:26,684 INFO L276 IsEmpty]: Start isEmpty. Operand 636 states and 917 transitions. [2024-11-18 13:36:26,685 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2024-11-18 13:36:26,685 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:26,685 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:26,697 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-18 13:36:26,889 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,SelfDestructingSolverStorable14 [2024-11-18 13:36:26,890 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:26,890 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:26,890 INFO L85 PathProgramCache]: Analyzing trace with hash 225609629, now seen corresponding path program 4 times [2024-11-18 13:36:26,890 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:26,891 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1788127634] [2024-11-18 13:36:26,891 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:36:26,891 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:26,904 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:36:26,908 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:26,976 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 43 proven. 0 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-11-18 13:36:26,977 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:26,977 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1788127634] [2024-11-18 13:36:26,977 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1788127634] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:36:26,977 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:36:26,977 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:36:26,977 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1566658922] [2024-11-18 13:36:26,977 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:36:26,978 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:36:26,978 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:26,978 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:36:26,978 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:36:26,978 INFO L87 Difference]: Start difference. First operand 636 states and 917 transitions. Second operand has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2024-11-18 13:36:27,152 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:27,153 INFO L93 Difference]: Finished difference Result 953 states and 1440 transitions. [2024-11-18 13:36:27,153 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-18 13:36:27,153 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) Word has length 91 [2024-11-18 13:36:27,153 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:27,156 INFO L225 Difference]: With dead ends: 953 [2024-11-18 13:36:27,156 INFO L226 Difference]: Without dead ends: 613 [2024-11-18 13:36:27,157 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 3 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-11-18 13:36:27,158 INFO L432 NwaCegarLoop]: 55 mSDtfsCounter, 12 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:27,158 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 186 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:36:27,158 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 613 states. [2024-11-18 13:36:27,238 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 613 to 525. [2024-11-18 13:36:27,239 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 525 states, 333 states have (on average 1.2732732732732732) internal successors, (424), 336 states have internal predecessors, (424), 152 states have call successors, (152), 39 states have call predecessors, (152), 39 states have return successors, (150), 149 states have call predecessors, (150), 150 states have call successors, (150) [2024-11-18 13:36:27,240 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 525 states to 525 states and 726 transitions. [2024-11-18 13:36:27,241 INFO L78 Accepts]: Start accepts. Automaton has 525 states and 726 transitions. Word has length 91 [2024-11-18 13:36:27,241 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:27,241 INFO L471 AbstractCegarLoop]: Abstraction has 525 states and 726 transitions. [2024-11-18 13:36:27,241 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2024-11-18 13:36:27,242 INFO L276 IsEmpty]: Start isEmpty. Operand 525 states and 726 transitions. [2024-11-18 13:36:27,242 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2024-11-18 13:36:27,242 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:27,242 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:27,242 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15 [2024-11-18 13:36:27,243 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:27,243 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:27,243 INFO L85 PathProgramCache]: Analyzing trace with hash -1718599493, now seen corresponding path program 1 times [2024-11-18 13:36:27,243 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:27,243 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [935213201] [2024-11-18 13:36:27,243 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:27,243 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:27,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:36:27,257 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [713590633] [2024-11-18 13:36:27,258 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:27,258 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:27,258 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:27,259 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:27,260 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-18 13:36:27,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:27,330 INFO L255 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 38 conjuncts are in the unsatisfiable core [2024-11-18 13:36:27,332 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:28,339 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 51 proven. 32 refuted. 0 times theorem prover too weak. 205 trivial. 0 not checked. [2024-11-18 13:36:28,339 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:28,578 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:28,578 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [935213201] [2024-11-18 13:36:28,578 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:28,578 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [713590633] [2024-11-18 13:36:28,578 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [713590633] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:28,578 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:36:28,578 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-11-18 13:36:28,579 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1246587754] [2024-11-18 13:36:28,579 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:28,579 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-18 13:36:28,579 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:28,580 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-18 13:36:28,580 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2024-11-18 13:36:28,580 INFO L87 Difference]: Start difference. First operand 525 states and 726 transitions. Second operand has 16 states, 15 states have (on average 2.2) internal successors, (33), 13 states have internal predecessors, (33), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2024-11-18 13:36:29,615 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:29,615 INFO L93 Difference]: Finished difference Result 534 states and 734 transitions. [2024-11-18 13:36:29,619 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-18 13:36:29,619 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.2) internal successors, (33), 13 states have internal predecessors, (33), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) Word has length 97 [2024-11-18 13:36:29,620 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:29,622 INFO L225 Difference]: With dead ends: 534 [2024-11-18 13:36:29,622 INFO L226 Difference]: Without dead ends: 532 [2024-11-18 13:36:29,622 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=84, Invalid=422, Unknown=0, NotChecked=0, Total=506 [2024-11-18 13:36:29,622 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 41 mSDsluCounter, 394 mSDsCounter, 0 mSdLazyCounter, 427 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 440 SdHoareTripleChecker+Invalid, 439 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 427 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:29,623 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 440 Invalid, 439 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 427 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-18 13:36:29,623 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 532 states. [2024-11-18 13:36:29,715 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 532 to 529. [2024-11-18 13:36:29,716 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 529 states, 336 states have (on average 1.2678571428571428) internal successors, (426), 339 states have internal predecessors, (426), 152 states have call successors, (152), 40 states have call predecessors, (152), 40 states have return successors, (150), 149 states have call predecessors, (150), 150 states have call successors, (150) [2024-11-18 13:36:29,718 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 529 states to 529 states and 728 transitions. [2024-11-18 13:36:29,718 INFO L78 Accepts]: Start accepts. Automaton has 529 states and 728 transitions. Word has length 97 [2024-11-18 13:36:29,719 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:29,719 INFO L471 AbstractCegarLoop]: Abstraction has 529 states and 728 transitions. [2024-11-18 13:36:29,719 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.2) internal successors, (33), 13 states have internal predecessors, (33), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2024-11-18 13:36:29,719 INFO L276 IsEmpty]: Start isEmpty. Operand 529 states and 728 transitions. [2024-11-18 13:36:29,722 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2024-11-18 13:36:29,722 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:29,722 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:29,734 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-11-18 13:36:29,926 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:29,927 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:29,927 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:29,927 INFO L85 PathProgramCache]: Analyzing trace with hash -1252794678, now seen corresponding path program 1 times [2024-11-18 13:36:29,927 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:29,927 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [29081631] [2024-11-18 13:36:29,928 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:29,928 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:29,937 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:30,011 INFO L134 CoverageAnalysis]: Checked inductivity of 393 backedges. 46 proven. 11 refuted. 0 times theorem prover too weak. 336 trivial. 0 not checked. [2024-11-18 13:36:30,012 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:30,012 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [29081631] [2024-11-18 13:36:30,012 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [29081631] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:30,012 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2109548812] [2024-11-18 13:36:30,012 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:30,012 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:30,012 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:30,013 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:30,014 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-18 13:36:30,070 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:30,071 INFO L255 TraceCheckSpWp]: Trace formula consists of 282 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-18 13:36:30,073 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:30,109 INFO L134 CoverageAnalysis]: Checked inductivity of 393 backedges. 92 proven. 11 refuted. 0 times theorem prover too weak. 290 trivial. 0 not checked. [2024-11-18 13:36:30,110 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:30,212 INFO L134 CoverageAnalysis]: Checked inductivity of 393 backedges. 46 proven. 11 refuted. 0 times theorem prover too weak. 336 trivial. 0 not checked. [2024-11-18 13:36:30,212 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2109548812] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:30,212 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:36:30,212 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 7 [2024-11-18 13:36:30,213 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1619074334] [2024-11-18 13:36:30,213 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:30,213 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-18 13:36:30,213 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:30,214 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-18 13:36:30,214 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-11-18 13:36:30,214 INFO L87 Difference]: Start difference. First operand 529 states and 728 transitions. Second operand has 7 states, 7 states have (on average 4.857142857142857) internal successors, (34), 7 states have internal predecessors, (34), 4 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-18 13:36:30,497 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:30,497 INFO L93 Difference]: Finished difference Result 660 states and 933 transitions. [2024-11-18 13:36:30,497 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-18 13:36:30,498 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 4.857142857142857) internal successors, (34), 7 states have internal predecessors, (34), 4 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) Word has length 112 [2024-11-18 13:36:30,498 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:30,513 INFO L225 Difference]: With dead ends: 660 [2024-11-18 13:36:30,513 INFO L226 Difference]: Without dead ends: 647 [2024-11-18 13:36:30,514 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 243 GetRequests, 223 SyntacticMatches, 6 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=68, Invalid=172, Unknown=0, NotChecked=0, Total=240 [2024-11-18 13:36:30,518 INFO L432 NwaCegarLoop]: 87 mSDtfsCounter, 31 mSDsluCounter, 321 mSDsCounter, 0 mSdLazyCounter, 143 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 408 SdHoareTripleChecker+Invalid, 153 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 143 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:30,519 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 408 Invalid, 153 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 143 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:36:30,519 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 647 states. [2024-11-18 13:36:30,646 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 647 to 504. [2024-11-18 13:36:30,647 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 504 states, 329 states have (on average 1.2462006079027355) internal successors, (410), 331 states have internal predecessors, (410), 135 states have call successors, (135), 39 states have call predecessors, (135), 39 states have return successors, (133), 133 states have call predecessors, (133), 133 states have call successors, (133) [2024-11-18 13:36:30,649 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 504 states to 504 states and 678 transitions. [2024-11-18 13:36:30,650 INFO L78 Accepts]: Start accepts. Automaton has 504 states and 678 transitions. Word has length 112 [2024-11-18 13:36:30,650 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:30,650 INFO L471 AbstractCegarLoop]: Abstraction has 504 states and 678 transitions. [2024-11-18 13:36:30,651 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 4.857142857142857) internal successors, (34), 7 states have internal predecessors, (34), 4 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-18 13:36:30,651 INFO L276 IsEmpty]: Start isEmpty. Operand 504 states and 678 transitions. [2024-11-18 13:36:30,651 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2024-11-18 13:36:30,652 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:30,652 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:30,665 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:30,852 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-18 13:36:30,852 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:30,853 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:30,853 INFO L85 PathProgramCache]: Analyzing trace with hash -245423741, now seen corresponding path program 1 times [2024-11-18 13:36:30,853 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:30,853 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1576449859] [2024-11-18 13:36:30,853 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:30,853 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:30,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:31,056 INFO L134 CoverageAnalysis]: Checked inductivity of 357 backedges. 32 proven. 37 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-18 13:36:31,056 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:31,057 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1576449859] [2024-11-18 13:36:31,057 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1576449859] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:31,057 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [410812984] [2024-11-18 13:36:31,057 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:31,057 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:31,057 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:31,059 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:31,062 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-18 13:36:31,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:31,134 INFO L255 TraceCheckSpWp]: Trace formula consists of 298 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-18 13:36:31,136 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:31,237 INFO L134 CoverageAnalysis]: Checked inductivity of 357 backedges. 32 proven. 229 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2024-11-18 13:36:31,237 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:31,387 INFO L134 CoverageAnalysis]: Checked inductivity of 357 backedges. 32 proven. 37 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-18 13:36:31,387 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [410812984] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:31,387 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:36:31,387 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 10] total 18 [2024-11-18 13:36:31,387 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1226057126] [2024-11-18 13:36:31,387 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:31,388 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-18 13:36:31,388 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:31,388 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-18 13:36:31,388 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=125, Invalid=181, Unknown=0, NotChecked=0, Total=306 [2024-11-18 13:36:31,389 INFO L87 Difference]: Start difference. First operand 504 states and 678 transitions. Second operand has 18 states, 18 states have (on average 4.111111111111111) internal successors, (74), 18 states have internal predecessors, (74), 9 states have call successors, (49), 6 states have call predecessors, (49), 5 states have return successors, (48), 8 states have call predecessors, (48), 8 states have call successors, (48) [2024-11-18 13:36:31,959 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:31,960 INFO L93 Difference]: Finished difference Result 1748 states and 2392 transitions. [2024-11-18 13:36:31,960 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2024-11-18 13:36:31,961 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 4.111111111111111) internal successors, (74), 18 states have internal predecessors, (74), 9 states have call successors, (49), 6 states have call predecessors, (49), 5 states have return successors, (48), 8 states have call predecessors, (48), 8 states have call successors, (48) Word has length 112 [2024-11-18 13:36:31,961 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:31,967 INFO L225 Difference]: With dead ends: 1748 [2024-11-18 13:36:31,967 INFO L226 Difference]: Without dead ends: 1514 [2024-11-18 13:36:31,968 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 244 GetRequests, 216 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 100 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=311, Invalid=559, Unknown=0, NotChecked=0, Total=870 [2024-11-18 13:36:31,969 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 255 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 187 mSolverCounterSat, 70 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 255 SdHoareTripleChecker+Valid, 290 SdHoareTripleChecker+Invalid, 257 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 70 IncrementalHoareTripleChecker+Valid, 187 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:31,969 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [255 Valid, 290 Invalid, 257 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [70 Valid, 187 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:36:31,970 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1514 states. [2024-11-18 13:36:32,237 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1514 to 1440. [2024-11-18 13:36:32,239 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1440 states, 900 states have (on average 1.19) internal successors, (1071), 916 states have internal predecessors, (1071), 404 states have call successors, (404), 135 states have call predecessors, (404), 135 states have return successors, (388), 388 states have call predecessors, (388), 388 states have call successors, (388) [2024-11-18 13:36:32,242 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1440 states to 1440 states and 1863 transitions. [2024-11-18 13:36:32,243 INFO L78 Accepts]: Start accepts. Automaton has 1440 states and 1863 transitions. Word has length 112 [2024-11-18 13:36:32,243 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:32,243 INFO L471 AbstractCegarLoop]: Abstraction has 1440 states and 1863 transitions. [2024-11-18 13:36:32,244 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 4.111111111111111) internal successors, (74), 18 states have internal predecessors, (74), 9 states have call successors, (49), 6 states have call predecessors, (49), 5 states have return successors, (48), 8 states have call predecessors, (48), 8 states have call successors, (48) [2024-11-18 13:36:32,244 INFO L276 IsEmpty]: Start isEmpty. Operand 1440 states and 1863 transitions. [2024-11-18 13:36:32,244 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2024-11-18 13:36:32,244 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:32,245 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:32,257 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:32,448 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:32,449 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:32,449 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:32,449 INFO L85 PathProgramCache]: Analyzing trace with hash -1796458373, now seen corresponding path program 2 times [2024-11-18 13:36:32,449 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:32,449 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1159804110] [2024-11-18 13:36:32,450 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:36:32,450 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:32,471 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:36:32,471 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:36:32,472 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [675777429] [2024-11-18 13:36:32,472 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:36:32,472 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:32,472 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:32,476 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:32,479 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-18 13:36:32,539 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:36:32,539 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:32,543 INFO L255 TraceCheckSpWp]: Trace formula consists of 290 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-11-18 13:36:32,544 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:33,145 INFO L134 CoverageAnalysis]: Checked inductivity of 405 backedges. 58 proven. 56 refuted. 0 times theorem prover too weak. 291 trivial. 0 not checked. [2024-11-18 13:36:33,145 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:33,394 INFO L134 CoverageAnalysis]: Checked inductivity of 405 backedges. 78 proven. 7 refuted. 0 times theorem prover too weak. 320 trivial. 0 not checked. [2024-11-18 13:36:33,394 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:33,394 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1159804110] [2024-11-18 13:36:33,395 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:33,395 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [675777429] [2024-11-18 13:36:33,395 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [675777429] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:33,395 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:36:33,395 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 8] total 23 [2024-11-18 13:36:33,395 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1940361341] [2024-11-18 13:36:33,395 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:33,396 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-18 13:36:33,396 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:33,396 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-18 13:36:33,396 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2024-11-18 13:36:33,396 INFO L87 Difference]: Start difference. First operand 1440 states and 1863 transitions. Second operand has 23 states, 22 states have (on average 2.772727272727273) internal successors, (61), 20 states have internal predecessors, (61), 9 states have call successors, (29), 3 states have call predecessors, (29), 3 states have return successors, (28), 10 states have call predecessors, (28), 9 states have call successors, (28) [2024-11-18 13:36:35,944 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:35,944 INFO L93 Difference]: Finished difference Result 1601 states and 2066 transitions. [2024-11-18 13:36:35,945 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-18 13:36:35,945 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 22 states have (on average 2.772727272727273) internal successors, (61), 20 states have internal predecessors, (61), 9 states have call successors, (29), 3 states have call predecessors, (29), 3 states have return successors, (28), 10 states have call predecessors, (28), 9 states have call successors, (28) Word has length 114 [2024-11-18 13:36:35,945 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:35,951 INFO L225 Difference]: With dead ends: 1601 [2024-11-18 13:36:35,951 INFO L226 Difference]: Without dead ends: 1591 [2024-11-18 13:36:35,952 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 242 GetRequests, 210 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 178 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=194, Invalid=928, Unknown=0, NotChecked=0, Total=1122 [2024-11-18 13:36:35,952 INFO L432 NwaCegarLoop]: 53 mSDtfsCounter, 96 mSDsluCounter, 535 mSDsCounter, 0 mSdLazyCounter, 574 mSolverCounterSat, 88 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 588 SdHoareTripleChecker+Invalid, 662 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 88 IncrementalHoareTripleChecker+Valid, 574 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:35,952 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [101 Valid, 588 Invalid, 662 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [88 Valid, 574 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2024-11-18 13:36:35,953 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1591 states. [2024-11-18 13:36:36,218 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1591 to 1528. [2024-11-18 13:36:36,220 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1528 states, 974 states have (on average 1.1878850102669405) internal successors, (1157), 988 states have internal predecessors, (1157), 402 states have call successors, (402), 151 states have call predecessors, (402), 151 states have return successors, (393), 388 states have call predecessors, (393), 393 states have call successors, (393) [2024-11-18 13:36:36,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1528 states to 1528 states and 1952 transitions. [2024-11-18 13:36:36,225 INFO L78 Accepts]: Start accepts. Automaton has 1528 states and 1952 transitions. Word has length 114 [2024-11-18 13:36:36,225 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:36,226 INFO L471 AbstractCegarLoop]: Abstraction has 1528 states and 1952 transitions. [2024-11-18 13:36:36,226 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 22 states have (on average 2.772727272727273) internal successors, (61), 20 states have internal predecessors, (61), 9 states have call successors, (29), 3 states have call predecessors, (29), 3 states have return successors, (28), 10 states have call predecessors, (28), 9 states have call successors, (28) [2024-11-18 13:36:36,226 INFO L276 IsEmpty]: Start isEmpty. Operand 1528 states and 1952 transitions. [2024-11-18 13:36:36,227 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2024-11-18 13:36:36,227 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:36,227 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:36,239 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:36,430 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:36,431 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:36,431 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:36,431 INFO L85 PathProgramCache]: Analyzing trace with hash 364386885, now seen corresponding path program 3 times [2024-11-18 13:36:36,431 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:36,431 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [215603421] [2024-11-18 13:36:36,432 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:36:36,432 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:36,458 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-18 13:36:36,458 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:36:36,459 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [579489061] [2024-11-18 13:36:36,459 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:36:36,459 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:36,459 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:36,460 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:36,465 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-18 13:36:36,525 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-18 13:36:36,525 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:36,526 INFO L255 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 67 conjuncts are in the unsatisfiable core [2024-11-18 13:36:36,528 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:37,366 INFO L134 CoverageAnalysis]: Checked inductivity of 462 backedges. 75 proven. 47 refuted. 0 times theorem prover too weak. 340 trivial. 0 not checked. [2024-11-18 13:36:37,366 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:42,611 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:42,612 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [215603421] [2024-11-18 13:36:42,612 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:42,612 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [579489061] [2024-11-18 13:36:42,612 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [579489061] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:42,612 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:36:42,612 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2024-11-18 13:36:42,612 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [424204935] [2024-11-18 13:36:42,612 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:42,613 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-18 13:36:42,613 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:42,613 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-18 13:36:42,613 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=425, Unknown=0, NotChecked=0, Total=506 [2024-11-18 13:36:42,614 INFO L87 Difference]: Start difference. First operand 1528 states and 1952 transitions. Second operand has 17 states, 16 states have (on average 2.5) internal successors, (40), 15 states have internal predecessors, (40), 7 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-18 13:36:43,397 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:43,398 INFO L93 Difference]: Finished difference Result 1658 states and 2089 transitions. [2024-11-18 13:36:43,398 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-18 13:36:43,398 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 2.5) internal successors, (40), 15 states have internal predecessors, (40), 7 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) Word has length 119 [2024-11-18 13:36:43,398 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:43,405 INFO L225 Difference]: With dead ends: 1658 [2024-11-18 13:36:43,405 INFO L226 Difference]: Without dead ends: 1656 [2024-11-18 13:36:43,405 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 146 GetRequests, 119 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 89 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=133, Invalid=679, Unknown=0, NotChecked=0, Total=812 [2024-11-18 13:36:43,406 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 30 mSDsluCounter, 586 mSDsCounter, 0 mSdLazyCounter, 587 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 635 SdHoareTripleChecker+Invalid, 625 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 587 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:43,406 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 635 Invalid, 625 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 587 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-18 13:36:43,407 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1656 states. [2024-11-18 13:36:43,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1656 to 1641. [2024-11-18 13:36:43,714 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1641 states, 1048 states have (on average 1.1803435114503817) internal successors, (1237), 1062 states have internal predecessors, (1237), 422 states have call successors, (422), 170 states have call predecessors, (422), 170 states have return successors, (413), 408 states have call predecessors, (413), 413 states have call successors, (413) [2024-11-18 13:36:43,718 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1641 states to 1641 states and 2072 transitions. [2024-11-18 13:36:43,719 INFO L78 Accepts]: Start accepts. Automaton has 1641 states and 2072 transitions. Word has length 119 [2024-11-18 13:36:43,719 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:43,720 INFO L471 AbstractCegarLoop]: Abstraction has 1641 states and 2072 transitions. [2024-11-18 13:36:43,720 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 2.5) internal successors, (40), 15 states have internal predecessors, (40), 7 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-18 13:36:43,720 INFO L276 IsEmpty]: Start isEmpty. Operand 1641 states and 2072 transitions. [2024-11-18 13:36:43,721 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 121 [2024-11-18 13:36:43,721 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:43,721 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:43,733 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:43,925 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:43,927 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:43,927 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:43,927 INFO L85 PathProgramCache]: Analyzing trace with hash -1062250723, now seen corresponding path program 4 times [2024-11-18 13:36:43,927 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:43,927 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [572918878] [2024-11-18 13:36:43,927 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:36:43,927 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:43,953 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:36:43,953 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:36:43,954 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [559627106] [2024-11-18 13:36:43,954 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:36:43,954 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:43,954 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:43,957 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:43,958 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2024-11-18 13:36:44,042 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:36:44,042 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:44,044 INFO L255 TraceCheckSpWp]: Trace formula consists of 251 conjuncts, 48 conjuncts are in the unsatisfiable core [2024-11-18 13:36:44,047 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:45,358 INFO L134 CoverageAnalysis]: Checked inductivity of 516 backedges. 100 proven. 59 refuted. 0 times theorem prover too weak. 357 trivial. 0 not checked. [2024-11-18 13:36:45,358 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:45,727 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:45,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [572918878] [2024-11-18 13:36:45,728 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:45,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [559627106] [2024-11-18 13:36:45,728 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [559627106] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:45,728 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:36:45,728 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2024-11-18 13:36:45,729 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1514785444] [2024-11-18 13:36:45,729 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:45,729 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-18 13:36:45,729 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:45,730 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-18 13:36:45,730 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=352, Unknown=0, NotChecked=0, Total=420 [2024-11-18 13:36:45,730 INFO L87 Difference]: Start difference. First operand 1641 states and 2072 transitions. Second operand has 18 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 14 states have internal predecessors, (36), 8 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 7 states have call successors, (19) [2024-11-18 13:36:46,992 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:46,992 INFO L93 Difference]: Finished difference Result 1754 states and 2208 transitions. [2024-11-18 13:36:46,992 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-18 13:36:46,993 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 14 states have internal predecessors, (36), 8 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 7 states have call successors, (19) Word has length 120 [2024-11-18 13:36:46,993 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:46,999 INFO L225 Difference]: With dead ends: 1754 [2024-11-18 13:36:46,999 INFO L226 Difference]: Without dead ends: 1752 [2024-11-18 13:36:47,000 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 105 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 101 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=122, Invalid=580, Unknown=0, NotChecked=0, Total=702 [2024-11-18 13:36:47,000 INFO L432 NwaCegarLoop]: 52 mSDtfsCounter, 47 mSDsluCounter, 598 mSDsCounter, 0 mSdLazyCounter, 643 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 650 SdHoareTripleChecker+Invalid, 670 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 643 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:47,000 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 650 Invalid, 670 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 643 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-18 13:36:47,001 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1752 states. [2024-11-18 13:36:47,279 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1752 to 1638. [2024-11-18 13:36:47,281 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1638 states, 1048 states have (on average 1.1784351145038168) internal successors, (1235), 1062 states have internal predecessors, (1235), 418 states have call successors, (418), 171 states have call predecessors, (418), 171 states have return successors, (409), 404 states have call predecessors, (409), 409 states have call successors, (409) [2024-11-18 13:36:47,285 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1638 states to 1638 states and 2062 transitions. [2024-11-18 13:36:47,286 INFO L78 Accepts]: Start accepts. Automaton has 1638 states and 2062 transitions. Word has length 120 [2024-11-18 13:36:47,287 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:47,287 INFO L471 AbstractCegarLoop]: Abstraction has 1638 states and 2062 transitions. [2024-11-18 13:36:47,287 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 14 states have internal predecessors, (36), 8 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 7 states have call successors, (19) [2024-11-18 13:36:47,287 INFO L276 IsEmpty]: Start isEmpty. Operand 1638 states and 2062 transitions. [2024-11-18 13:36:47,288 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2024-11-18 13:36:47,288 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:47,288 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:47,301 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2024-11-18 13:36:47,492 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:47,492 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:47,493 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:47,493 INFO L85 PathProgramCache]: Analyzing trace with hash -1493115269, now seen corresponding path program 5 times [2024-11-18 13:36:47,493 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:47,493 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [953971704] [2024-11-18 13:36:47,493 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-18 13:36:47,493 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:47,520 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2024-11-18 13:36:47,520 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:36:47,521 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [946736527] [2024-11-18 13:36:47,521 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-18 13:36:47,521 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:47,521 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:47,523 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:47,527 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2024-11-18 13:36:47,659 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2024-11-18 13:36:47,659 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:47,661 INFO L255 TraceCheckSpWp]: Trace formula consists of 308 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-18 13:36:47,663 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:49,300 INFO L134 CoverageAnalysis]: Checked inductivity of 523 backedges. 74 proven. 56 refuted. 0 times theorem prover too weak. 393 trivial. 0 not checked. [2024-11-18 13:36:49,301 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:53,776 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:53,777 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [953971704] [2024-11-18 13:36:53,777 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:53,777 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [946736527] [2024-11-18 13:36:53,777 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [946736527] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:53,777 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:36:53,777 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2024-11-18 13:36:53,777 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1226806833] [2024-11-18 13:36:53,777 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:53,778 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-18 13:36:53,778 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:53,778 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-18 13:36:53,778 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=357, Unknown=1, NotChecked=0, Total=420 [2024-11-18 13:36:53,778 INFO L87 Difference]: Start difference. First operand 1638 states and 2062 transitions. Second operand has 18 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 15 states have internal predecessors, (40), 7 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) [2024-11-18 13:36:55,619 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:55,619 INFO L93 Difference]: Finished difference Result 1897 states and 2412 transitions. [2024-11-18 13:36:55,620 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-18 13:36:55,620 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 15 states have internal predecessors, (40), 7 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) Word has length 124 [2024-11-18 13:36:55,620 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:55,627 INFO L225 Difference]: With dead ends: 1897 [2024-11-18 13:36:55,627 INFO L226 Difference]: Without dead ends: 1895 [2024-11-18 13:36:55,628 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 109 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 5.4s TimeCoverageRelationStatistics Valid=103, Invalid=598, Unknown=1, NotChecked=0, Total=702 [2024-11-18 13:36:55,629 INFO L432 NwaCegarLoop]: 58 mSDtfsCounter, 51 mSDsluCounter, 651 mSDsCounter, 0 mSdLazyCounter, 700 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 709 SdHoareTripleChecker+Invalid, 714 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 700 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:55,629 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 709 Invalid, 714 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 700 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2024-11-18 13:36:55,631 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1895 states. [2024-11-18 13:36:56,015 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1895 to 1850. [2024-11-18 13:36:56,017 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1850 states, 1174 states have (on average 1.176320272572402) internal successors, (1381), 1188 states have internal predecessors, (1381), 490 states have call successors, (490), 185 states have call predecessors, (490), 185 states have return successors, (481), 476 states have call predecessors, (481), 481 states have call successors, (481) [2024-11-18 13:36:56,020 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1850 states to 1850 states and 2352 transitions. [2024-11-18 13:36:56,024 INFO L78 Accepts]: Start accepts. Automaton has 1850 states and 2352 transitions. Word has length 124 [2024-11-18 13:36:56,024 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:56,024 INFO L471 AbstractCegarLoop]: Abstraction has 1850 states and 2352 transitions. [2024-11-18 13:36:56,025 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 2.3529411764705883) internal successors, (40), 15 states have internal predecessors, (40), 7 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) [2024-11-18 13:36:56,025 INFO L276 IsEmpty]: Start isEmpty. Operand 1850 states and 2352 transitions. [2024-11-18 13:36:56,026 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2024-11-18 13:36:56,026 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:56,026 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:56,033 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:56,227 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable22 [2024-11-18 13:36:56,227 INFO L396 AbstractCegarLoop]: === Iteration 24 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:56,227 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:56,228 INFO L85 PathProgramCache]: Analyzing trace with hash -1036292276, now seen corresponding path program 1 times [2024-11-18 13:36:56,228 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:56,228 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2058470843] [2024-11-18 13:36:56,228 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:56,228 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:56,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:56,400 INFO L134 CoverageAnalysis]: Checked inductivity of 586 backedges. 32 proven. 50 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2024-11-18 13:36:56,400 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:56,400 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2058470843] [2024-11-18 13:36:56,401 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2058470843] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:56,401 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [403194720] [2024-11-18 13:36:56,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:56,401 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:56,401 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:56,405 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:56,409 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2024-11-18 13:36:56,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:56,473 INFO L255 TraceCheckSpWp]: Trace formula consists of 317 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-18 13:36:56,475 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:56,587 INFO L134 CoverageAnalysis]: Checked inductivity of 586 backedges. 32 proven. 434 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-18 13:36:56,587 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:56,745 INFO L134 CoverageAnalysis]: Checked inductivity of 586 backedges. 32 proven. 50 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2024-11-18 13:36:56,745 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [403194720] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:56,745 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:36:56,746 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 10] total 18 [2024-11-18 13:36:56,746 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1825104682] [2024-11-18 13:36:56,746 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:56,746 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-18 13:36:56,746 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:56,747 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-18 13:36:56,747 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=125, Invalid=181, Unknown=0, NotChecked=0, Total=306 [2024-11-18 13:36:56,747 INFO L87 Difference]: Start difference. First operand 1850 states and 2352 transitions. Second operand has 18 states, 18 states have (on average 4.111111111111111) internal successors, (74), 18 states have internal predecessors, (74), 11 states have call successors, (61), 7 states have call predecessors, (61), 6 states have return successors, (60), 10 states have call predecessors, (60), 10 states have call successors, (60) [2024-11-18 13:36:57,367 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:57,367 INFO L93 Difference]: Finished difference Result 1921 states and 2420 transitions. [2024-11-18 13:36:57,368 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2024-11-18 13:36:57,368 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 4.111111111111111) internal successors, (74), 18 states have internal predecessors, (74), 11 states have call successors, (61), 7 states have call predecessors, (61), 6 states have return successors, (60), 10 states have call predecessors, (60), 10 states have call successors, (60) Word has length 129 [2024-11-18 13:36:57,369 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:57,384 INFO L225 Difference]: With dead ends: 1921 [2024-11-18 13:36:57,384 INFO L226 Difference]: Without dead ends: 1879 [2024-11-18 13:36:57,385 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 278 GetRequests, 250 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 103 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=312, Invalid=558, Unknown=0, NotChecked=0, Total=870 [2024-11-18 13:36:57,385 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 178 mSDsluCounter, 217 mSDsCounter, 0 mSdLazyCounter, 170 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 178 SdHoareTripleChecker+Valid, 255 SdHoareTripleChecker+Invalid, 201 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 170 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:57,385 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [178 Valid, 255 Invalid, 201 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 170 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:36:57,386 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1879 states. [2024-11-18 13:36:57,792 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1879 to 1865. [2024-11-18 13:36:57,794 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1865 states, 1189 states have (on average 1.152228763666947) internal successors, (1370), 1203 states have internal predecessors, (1370), 490 states have call successors, (490), 185 states have call predecessors, (490), 185 states have return successors, (481), 476 states have call predecessors, (481), 481 states have call successors, (481) [2024-11-18 13:36:57,797 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1865 states to 1865 states and 2341 transitions. [2024-11-18 13:36:57,799 INFO L78 Accepts]: Start accepts. Automaton has 1865 states and 2341 transitions. Word has length 129 [2024-11-18 13:36:57,799 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:57,799 INFO L471 AbstractCegarLoop]: Abstraction has 1865 states and 2341 transitions. [2024-11-18 13:36:57,799 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 4.111111111111111) internal successors, (74), 18 states have internal predecessors, (74), 11 states have call successors, (61), 7 states have call predecessors, (61), 6 states have return successors, (60), 10 states have call predecessors, (60), 10 states have call successors, (60) [2024-11-18 13:36:57,799 INFO L276 IsEmpty]: Start isEmpty. Operand 1865 states and 2341 transitions. [2024-11-18 13:36:57,800 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2024-11-18 13:36:57,801 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:57,801 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:57,813 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:58,001 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable23 [2024-11-18 13:36:58,002 INFO L396 AbstractCegarLoop]: === Iteration 25 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:58,002 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:58,002 INFO L85 PathProgramCache]: Analyzing trace with hash -2066876172, now seen corresponding path program 2 times [2024-11-18 13:36:58,003 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:58,003 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [704820335] [2024-11-18 13:36:58,003 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:36:58,003 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:58,021 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:36:58,021 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:36:58,022 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1218626219] [2024-11-18 13:36:58,022 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:36:58,022 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:58,022 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:58,028 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:58,029 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2024-11-18 13:36:58,103 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:36:58,103 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:58,105 INFO L255 TraceCheckSpWp]: Trace formula consists of 319 conjuncts, 64 conjuncts are in the unsatisfiable core [2024-11-18 13:36:58,107 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:59,018 INFO L134 CoverageAnalysis]: Checked inductivity of 588 backedges. 73 proven. 65 refuted. 0 times theorem prover too weak. 450 trivial. 0 not checked. [2024-11-18 13:36:59,019 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:37:01,486 INFO L134 CoverageAnalysis]: Checked inductivity of 588 backedges. 73 proven. 56 refuted. 0 times theorem prover too weak. 459 trivial. 0 not checked. [2024-11-18 13:37:01,486 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:37:01,486 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [704820335] [2024-11-18 13:37:01,486 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:37:01,486 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1218626219] [2024-11-18 13:37:01,486 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1218626219] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:37:01,487 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:37:01,487 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 16] total 33 [2024-11-18 13:37:01,487 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2123518617] [2024-11-18 13:37:01,487 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:37:01,487 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2024-11-18 13:37:01,487 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:37:01,488 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2024-11-18 13:37:01,488 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=148, Invalid=908, Unknown=0, NotChecked=0, Total=1056 [2024-11-18 13:37:01,488 INFO L87 Difference]: Start difference. First operand 1865 states and 2341 transitions. Second operand has 33 states, 31 states have (on average 2.225806451612903) internal successors, (69), 29 states have internal predecessors, (69), 16 states have call successors, (41), 3 states have call predecessors, (41), 3 states have return successors, (40), 14 states have call predecessors, (40), 14 states have call successors, (40)