./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.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/egcd3-ll_valuebound10.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 776d32abf1ae3b62e7ad4a02cd7c02c0cc6433852a1fe73b7d30c6e216da832a --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-18 13:36:46,873 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-18 13:36:46,934 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-18 13:36:46,938 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-18 13:36:46,938 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-18 13:36:46,959 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-18 13:36:46,961 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-18 13:36:46,961 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-18 13:36:46,962 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-18 13:36:46,965 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-18 13:36:46,965 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-18 13:36:46,965 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-18 13:36:46,965 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-18 13:36:46,965 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-18 13:36:46,966 INFO L153 SettingsManager]: * Use SBE=true [2024-11-18 13:36:46,966 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-18 13:36:46,966 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-18 13:36:46,966 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-18 13:36:46,966 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-18 13:36:46,966 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-18 13:36:46,966 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-18 13:36:46,968 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-18 13:36:46,968 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-18 13:36:46,969 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-18 13:36:46,969 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-18 13:36:46,969 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-18 13:36:46,969 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-18 13:36:46,969 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-18 13:36:46,969 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-18 13:36:46,969 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-18 13:36:46,970 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-18 13:36:46,970 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-18 13:36:46,970 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:36:46,970 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-18 13:36:46,970 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-18 13:36:46,970 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-18 13:36:46,970 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-18 13:36:46,970 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-18 13:36:46,971 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-18 13:36:46,971 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-18 13:36:46,971 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-18 13:36:46,972 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-18 13:36:46,972 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 -> 776d32abf1ae3b62e7ad4a02cd7c02c0cc6433852a1fe73b7d30c6e216da832a [2024-11-18 13:36:47,156 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-18 13:36:47,172 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-18 13:36:47,175 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-18 13:36:47,176 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-18 13:36:47,177 INFO L274 PluginConnector]: CDTParser initialized [2024-11-18 13:36:47,177 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c [2024-11-18 13:36:48,390 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-18 13:36:48,530 INFO L384 CDTParser]: Found 1 translation units. [2024-11-18 13:36:48,530 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound10.c [2024-11-18 13:36:48,537 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9b5be3b5f/296930e78c444ae7a037c86a34a58c2a/FLAGe5fb9d5bb [2024-11-18 13:36:48,944 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9b5be3b5f/296930e78c444ae7a037c86a34a58c2a [2024-11-18 13:36:48,946 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-18 13:36:48,947 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-18 13:36:48,950 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-18 13:36:48,950 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-18 13:36:48,955 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-18 13:36:48,956 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:36:48" (1/1) ... [2024-11-18 13:36:48,956 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@39a81d55 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:36:48, skipping insertion in model container [2024-11-18 13:36:48,957 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:36:48" (1/1) ... [2024-11-18 13:36:48,972 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-18 13:36:49,095 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/egcd3-ll_valuebound10.c[490,503] [2024-11-18 13:36:49,111 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:36:49,117 INFO L200 MainTranslator]: Completed pre-run [2024-11-18 13:36:49,126 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/egcd3-ll_valuebound10.c[490,503] [2024-11-18 13:36:49,131 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:36:49,145 INFO L204 MainTranslator]: Completed translation [2024-11-18 13:36:49,145 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:36:49 WrapperNode [2024-11-18 13:36:49,145 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-18 13:36:49,146 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-18 13:36:49,146 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-18 13:36:49,147 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-18 13:36:49,151 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:36:49" (1/1) ... [2024-11-18 13:36:49,156 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:36:49" (1/1) ... [2024-11-18 13:36:49,168 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 83 [2024-11-18 13:36:49,168 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-18 13:36:49,169 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-18 13:36:49,169 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-18 13:36:49,170 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-18 13:36:49,177 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:36:49" (1/1) ... [2024-11-18 13:36:49,177 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:36:49" (1/1) ... [2024-11-18 13:36:49,178 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:36:49" (1/1) ... [2024-11-18 13:36:49,186 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:36:49,187 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:36:49" (1/1) ... [2024-11-18 13:36:49,187 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:36:49" (1/1) ... [2024-11-18 13:36:49,189 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:36:49" (1/1) ... [2024-11-18 13:36:49,191 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:36:49" (1/1) ... [2024-11-18 13:36:49,192 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:36:49" (1/1) ... [2024-11-18 13:36:49,209 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:36:49" (1/1) ... [2024-11-18 13:36:49,210 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-18 13:36:49,211 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-18 13:36:49,211 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-18 13:36:49,211 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-18 13:36:49,212 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:36:49" (1/1) ... [2024-11-18 13:36:49,221 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:36:49,240 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:49,253 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:36:49,255 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:36:49,286 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-18 13:36:49,286 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-18 13:36:49,286 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-18 13:36:49,286 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-18 13:36:49,286 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-18 13:36:49,287 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-18 13:36:49,287 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-18 13:36:49,287 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-18 13:36:49,335 INFO L238 CfgBuilder]: Building ICFG [2024-11-18 13:36:49,336 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-18 13:36:49,467 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-18 13:36:49,467 INFO L287 CfgBuilder]: Performing block encoding [2024-11-18 13:36:49,480 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-18 13:36:49,480 INFO L316 CfgBuilder]: Removed 3 assume(true) statements. [2024-11-18 13:36:49,481 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:36:49 BoogieIcfgContainer [2024-11-18 13:36:49,481 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-18 13:36:49,482 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-18 13:36:49,482 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-18 13:36:49,485 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-18 13:36:49,485 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.11 01:36:48" (1/3) ... [2024-11-18 13:36:49,486 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d07ec6a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:36:49, skipping insertion in model container [2024-11-18 13:36:49,486 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:36:49" (2/3) ... [2024-11-18 13:36:49,486 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d07ec6a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:36:49, skipping insertion in model container [2024-11-18 13:36:49,486 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:36:49" (3/3) ... [2024-11-18 13:36:49,487 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound10.c [2024-11-18 13:36:49,500 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-18 13:36:49,500 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-18 13:36:49,543 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-18 13:36:49,548 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;@577bf7eb, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-18 13:36:49,548 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-18 13:36:49,551 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-18 13:36:49,557 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-18 13:36:49,557 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:49,558 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:36:49,558 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:49,562 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:49,562 INFO L85 PathProgramCache]: Analyzing trace with hash 872320404, now seen corresponding path program 1 times [2024-11-18 13:36:49,568 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:49,569 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [401274522] [2024-11-18 13:36:49,569 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:49,569 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:49,638 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:49,689 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:36:49,690 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:49,690 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [401274522] [2024-11-18 13:36:49,690 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [401274522] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:49,691 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1678558900] [2024-11-18 13:36:49,691 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:49,691 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:49,691 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:49,698 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:36:49,700 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:36:49,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:49,751 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-18 13:36:49,754 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:49,763 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:36:49,763 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:36:49,764 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1678558900] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:36:49,764 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:36:49,764 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-11-18 13:36:49,766 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1048154496] [2024-11-18 13:36:49,766 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:36:49,769 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-18 13:36:49,769 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:49,786 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-18 13:36:49,787 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 13:36:49,789 INFO L87 Difference]: Start difference. First operand has 35 states, 22 states have (on average 1.5454545454545454) internal successors, (34), 23 states have internal predecessors, (34), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 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:36:49,807 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:49,808 INFO L93 Difference]: Finished difference Result 67 states and 109 transitions. [2024-11-18 13:36:49,809 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-18 13:36:49,811 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 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 29 [2024-11-18 13:36:49,811 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:49,816 INFO L225 Difference]: With dead ends: 67 [2024-11-18 13:36:49,817 INFO L226 Difference]: Without dead ends: 31 [2024-11-18 13:36:49,820 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 30 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:36:49,824 INFO L432 NwaCegarLoop]: 44 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, 44 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:36:49,827 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:36:49,839 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-18 13:36:49,850 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2024-11-18 13:36:49,851 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 20 states have internal predecessors, (23), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-18 13:36:49,852 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 40 transitions. [2024-11-18 13:36:49,854 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 40 transitions. Word has length 29 [2024-11-18 13:36:49,854 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:49,854 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 40 transitions. [2024-11-18 13:36:49,854 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 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:36:49,854 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 40 transitions. [2024-11-18 13:36:49,855 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-18 13:36:49,855 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:49,856 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:36:49,868 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-18 13:36:50,056 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:36:50,057 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:50,057 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:50,057 INFO L85 PathProgramCache]: Analyzing trace with hash 1714405113, now seen corresponding path program 1 times [2024-11-18 13:36:50,057 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:50,057 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [48931859] [2024-11-18 13:36:50,058 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:50,058 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:50,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:50,261 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-18 13:36:50,261 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:50,262 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [48931859] [2024-11-18 13:36:50,262 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [48931859] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:36:50,262 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:36:50,262 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-18 13:36:50,262 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1185943027] [2024-11-18 13:36:50,262 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:36:50,263 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-18 13:36:50,263 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:50,263 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-18 13:36:50,263 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-18 13:36:50,264 INFO L87 Difference]: Start difference. First operand 31 states and 40 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-18 13:36:50,350 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:50,350 INFO L93 Difference]: Finished difference Result 50 states and 65 transitions. [2024-11-18 13:36:50,351 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-18 13:36:50,351 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) Word has length 30 [2024-11-18 13:36:50,351 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:50,352 INFO L225 Difference]: With dead ends: 50 [2024-11-18 13:36:50,352 INFO L226 Difference]: Without dead ends: 43 [2024-11-18 13:36:50,352 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-18 13:36:50,353 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 20 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 60 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 60 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:50,354 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 119 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 60 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:36:50,354 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-18 13:36:50,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 33. [2024-11-18 13:36:50,364 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 22 states have internal predecessors, (25), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-18 13:36:50,365 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 42 transitions. [2024-11-18 13:36:50,367 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 42 transitions. Word has length 30 [2024-11-18 13:36:50,367 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:50,367 INFO L471 AbstractCegarLoop]: Abstraction has 33 states and 42 transitions. [2024-11-18 13:36:50,368 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 5 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-18 13:36:50,368 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 42 transitions. [2024-11-18 13:36:50,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-11-18 13:36:50,369 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:50,369 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, 1] [2024-11-18 13:36:50,370 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-18 13:36:50,370 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:50,371 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:50,371 INFO L85 PathProgramCache]: Analyzing trace with hash -1825736765, now seen corresponding path program 1 times [2024-11-18 13:36:50,371 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:50,371 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1956793691] [2024-11-18 13:36:50,371 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:50,371 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:50,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:36:50,398 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1061288192] [2024-11-18 13:36:50,400 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:50,400 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:50,400 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:50,402 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:36:50,404 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:36:50,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:50,452 INFO L255 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-18 13:36:50,454 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:50,569 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:36:50,570 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:36:50,570 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:50,571 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1956793691] [2024-11-18 13:36:50,571 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:50,571 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1061288192] [2024-11-18 13:36:50,571 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1061288192] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:36:50,571 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:36:50,571 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:36:50,572 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1063735730] [2024-11-18 13:36:50,572 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:36:50,572 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:36:50,572 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:50,572 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:36:50,573 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:36:50,573 INFO L87 Difference]: Start difference. First operand 33 states and 42 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, (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:36:50,618 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:50,618 INFO L93 Difference]: Finished difference Result 49 states and 63 transitions. [2024-11-18 13:36:50,620 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:36:50,620 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, (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 33 [2024-11-18 13:36:50,620 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:50,621 INFO L225 Difference]: With dead ends: 49 [2024-11-18 13:36:50,622 INFO L226 Difference]: Without dead ends: 47 [2024-11-18 13:36:50,622 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 29 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:36:50,623 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 7 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:50,623 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 134 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:36:50,624 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-18 13:36:50,631 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2024-11-18 13:36:50,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 29 states have (on average 1.206896551724138) internal successors, (35), 30 states have internal predecessors, (35), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-18 13:36:50,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 60 transitions. [2024-11-18 13:36:50,635 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 60 transitions. Word has length 33 [2024-11-18 13:36:50,635 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:50,635 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 60 transitions. [2024-11-18 13:36:50,635 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, (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:36:50,635 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 60 transitions. [2024-11-18 13:36:50,636 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-18 13:36:50,636 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:50,636 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:36:50,650 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:36:50,840 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:36:50,841 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:50,844 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:50,844 INFO L85 PathProgramCache]: Analyzing trace with hash -1547103247, now seen corresponding path program 1 times [2024-11-18 13:36:50,844 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:50,844 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [33035684] [2024-11-18 13:36:50,844 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:50,844 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:50,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:51,009 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-18 13:36:51,009 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:51,011 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [33035684] [2024-11-18 13:36:51,011 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [33035684] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:51,011 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1620402799] [2024-11-18 13:36:51,011 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:51,012 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:51,012 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:51,014 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:36:51,015 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:36:51,052 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:51,053 INFO L255 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-18 13:36:51,055 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:51,093 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-18 13:36:51,094 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:51,162 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-18 13:36:51,163 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1620402799] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:51,163 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:36:51,163 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 12 [2024-11-18 13:36:51,163 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1870178254] [2024-11-18 13:36:51,163 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:51,164 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-18 13:36:51,164 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:51,164 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-18 13:36:51,164 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2024-11-18 13:36:51,164 INFO L87 Difference]: Start difference. First operand 46 states and 60 transitions. Second operand has 12 states, 12 states have (on average 2.5) internal successors, (30), 11 states have internal predecessors, (30), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-18 13:36:51,313 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:51,313 INFO L93 Difference]: Finished difference Result 99 states and 139 transitions. [2024-11-18 13:36:51,313 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-18 13:36:51,314 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.5) internal successors, (30), 11 states have internal predecessors, (30), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 35 [2024-11-18 13:36:51,314 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:51,315 INFO L225 Difference]: With dead ends: 99 [2024-11-18 13:36:51,315 INFO L226 Difference]: Without dead ends: 92 [2024-11-18 13:36:51,315 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 62 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=54, Invalid=156, Unknown=0, NotChecked=0, Total=210 [2024-11-18 13:36:51,316 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 60 mSDsluCounter, 234 mSDsCounter, 0 mSdLazyCounter, 141 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 274 SdHoareTripleChecker+Invalid, 163 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 141 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:51,316 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [68 Valid, 274 Invalid, 163 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 141 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:36:51,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2024-11-18 13:36:51,327 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 67. [2024-11-18 13:36:51,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 46 states have (on average 1.2608695652173914) internal successors, (58), 47 states have internal predecessors, (58), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-18 13:36:51,329 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 91 transitions. [2024-11-18 13:36:51,329 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 91 transitions. Word has length 35 [2024-11-18 13:36:51,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:51,329 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 91 transitions. [2024-11-18 13:36:51,330 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.5) internal successors, (30), 11 states have internal predecessors, (30), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-18 13:36:51,330 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 91 transitions. [2024-11-18 13:36:51,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-18 13:36:51,330 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:51,331 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, 1, 1, 1] [2024-11-18 13:36:51,343 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:36:51,531 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:36:51,532 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:51,532 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:51,532 INFO L85 PathProgramCache]: Analyzing trace with hash -720434099, now seen corresponding path program 1 times [2024-11-18 13:36:51,532 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:51,532 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [99797938] [2024-11-18 13:36:51,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:51,532 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:51,544 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:36:51,549 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1763125465] [2024-11-18 13:36:51,551 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:51,551 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:51,551 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:51,553 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:36:51,554 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:36:51,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:51,592 INFO L255 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-18 13:36:51,594 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:51,660 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:36:51,661 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:36:51,661 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:51,662 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [99797938] [2024-11-18 13:36:51,662 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:51,662 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1763125465] [2024-11-18 13:36:51,663 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1763125465] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:36:51,663 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:36:51,663 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:36:51,663 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2137028502] [2024-11-18 13:36:51,663 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:36:51,663 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:36:51,663 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:51,664 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:36:51,664 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:36:51,664 INFO L87 Difference]: Start difference. First operand 67 states and 91 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, (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:36:51,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:51,726 INFO L93 Difference]: Finished difference Result 75 states and 98 transitions. [2024-11-18 13:36:51,729 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:36:51,729 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, (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 38 [2024-11-18 13:36:51,729 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:51,731 INFO L225 Difference]: With dead ends: 75 [2024-11-18 13:36:51,731 INFO L226 Difference]: Without dead ends: 73 [2024-11-18 13:36:51,731 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 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:36:51,732 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 7 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:51,732 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 131 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:36:51,733 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2024-11-18 13:36:51,740 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 71. [2024-11-18 13:36:51,740 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 49 states have (on average 1.2448979591836735) internal successors, (61), 50 states have internal predecessors, (61), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-18 13:36:51,741 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 94 transitions. [2024-11-18 13:36:51,741 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 94 transitions. Word has length 38 [2024-11-18 13:36:51,742 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:51,742 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 94 transitions. [2024-11-18 13:36:51,742 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, (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:36:51,742 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 94 transitions. [2024-11-18 13:36:51,743 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-18 13:36:51,743 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:51,743 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-18 13:36:51,755 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:51,946 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:36:51,947 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:51,948 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:51,948 INFO L85 PathProgramCache]: Analyzing trace with hash -376152117, now seen corresponding path program 1 times [2024-11-18 13:36:51,949 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:51,949 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [754752800] [2024-11-18 13:36:51,949 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:51,949 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:51,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:36:51,965 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [276707124] [2024-11-18 13:36:51,965 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:51,965 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:51,965 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:51,967 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:36:51,969 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:36:52,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:52,012 INFO L255 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-18 13:36:52,014 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:52,110 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-18 13:36:52,110 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:52,192 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-18 13:36:52,192 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:52,192 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [754752800] [2024-11-18 13:36:52,193 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:52,193 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [276707124] [2024-11-18 13:36:52,193 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [276707124] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:52,193 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:36:52,193 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 9 [2024-11-18 13:36:52,193 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [238181069] [2024-11-18 13:36:52,193 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:52,193 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-18 13:36:52,193 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:52,194 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-18 13:36:52,194 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-18 13:36:52,194 INFO L87 Difference]: Start difference. First operand 71 states and 94 transitions. Second operand has 9 states, 9 states have (on average 3.4444444444444446) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-18 13:36:52,320 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:52,320 INFO L93 Difference]: Finished difference Result 107 states and 143 transitions. [2024-11-18 13:36:52,320 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-18 13:36:52,320 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.4444444444444446) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 38 [2024-11-18 13:36:52,321 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:52,321 INFO L225 Difference]: With dead ends: 107 [2024-11-18 13:36:52,322 INFO L226 Difference]: Without dead ends: 105 [2024-11-18 13:36:52,322 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 65 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2024-11-18 13:36:52,323 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 30 mSDsluCounter, 158 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 205 SdHoareTripleChecker+Invalid, 86 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:52,324 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 205 Invalid, 86 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:36:52,324 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states. [2024-11-18 13:36:52,340 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 101. [2024-11-18 13:36:52,340 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 101 states, 70 states have (on average 1.2571428571428571) internal successors, (88), 71 states have internal predecessors, (88), 25 states have call successors, (25), 5 states have call predecessors, (25), 5 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-18 13:36:52,341 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 137 transitions. [2024-11-18 13:36:52,341 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 137 transitions. Word has length 38 [2024-11-18 13:36:52,341 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:52,342 INFO L471 AbstractCegarLoop]: Abstraction has 101 states and 137 transitions. [2024-11-18 13:36:52,342 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.4444444444444446) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-18 13:36:52,342 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 137 transitions. [2024-11-18 13:36:52,343 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-18 13:36:52,343 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:52,343 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 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:36:52,356 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:36:52,543 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:52,544 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:52,544 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:52,544 INFO L85 PathProgramCache]: Analyzing trace with hash 279172547, now seen corresponding path program 1 times [2024-11-18 13:36:52,544 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:52,545 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [349639607] [2024-11-18 13:36:52,545 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:52,545 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:52,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:36:52,556 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1850630861] [2024-11-18 13:36:52,556 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:52,556 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:52,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:52,560 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:36:52,561 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:36:52,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:52,596 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-18 13:36:52,599 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:52,631 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-18 13:36:52,631 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:36:52,631 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:52,632 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [349639607] [2024-11-18 13:36:52,632 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:52,632 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1850630861] [2024-11-18 13:36:52,632 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1850630861] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:36:52,632 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:36:52,632 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:36:52,632 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [204612106] [2024-11-18 13:36:52,632 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:36:52,633 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:36:52,633 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:52,633 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:36:52,633 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:36:52,634 INFO L87 Difference]: Start difference. First operand 101 states and 137 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-18 13:36:52,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:52,685 INFO L93 Difference]: Finished difference Result 147 states and 209 transitions. [2024-11-18 13:36:52,686 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:36:52,686 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 43 [2024-11-18 13:36:52,687 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:52,688 INFO L225 Difference]: With dead ends: 147 [2024-11-18 13:36:52,689 INFO L226 Difference]: Without dead ends: 145 [2024-11-18 13:36:52,689 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 39 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:36:52,691 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:52,691 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 124 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:36:52,692 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2024-11-18 13:36:52,722 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 139. [2024-11-18 13:36:52,722 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 87 states have (on average 1.2873563218390804) internal successors, (112), 88 states have internal predecessors, (112), 45 states have call successors, (45), 6 states have call predecessors, (45), 6 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-11-18 13:36:52,738 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 201 transitions. [2024-11-18 13:36:52,738 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 201 transitions. Word has length 43 [2024-11-18 13:36:52,738 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:52,738 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 201 transitions. [2024-11-18 13:36:52,739 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-18 13:36:52,739 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 201 transitions. [2024-11-18 13:36:52,739 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-18 13:36:52,739 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:52,739 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:52,752 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:52,940 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:52,942 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:52,942 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:52,942 INFO L85 PathProgramCache]: Analyzing trace with hash -2141198011, now seen corresponding path program 1 times [2024-11-18 13:36:52,942 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:52,942 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1511024433] [2024-11-18 13:36:52,942 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:52,943 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:52,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:36:52,959 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2059495448] [2024-11-18 13:36:52,959 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:52,959 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:52,959 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:52,961 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:36:52,962 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:36:52,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:52,999 INFO L255 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-18 13:36:53,001 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:53,112 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-18 13:36:53,112 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:53,155 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:53,155 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1511024433] [2024-11-18 13:36:53,155 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:53,155 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2059495448] [2024-11-18 13:36:53,155 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2059495448] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:53,155 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:36:53,156 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2024-11-18 13:36:53,156 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [611468029] [2024-11-18 13:36:53,156 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:53,156 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-18 13:36:53,156 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:53,157 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-18 13:36:53,157 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-18 13:36:53,157 INFO L87 Difference]: Start difference. First operand 139 states and 201 transitions. Second operand has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 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:36:53,275 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:53,275 INFO L93 Difference]: Finished difference Result 152 states and 212 transitions. [2024-11-18 13:36:53,275 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-18 13:36:53,275 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 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 43 [2024-11-18 13:36:53,276 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:53,277 INFO L225 Difference]: With dead ends: 152 [2024-11-18 13:36:53,277 INFO L226 Difference]: Without dead ends: 150 [2024-11-18 13:36:53,277 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 39 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2024-11-18 13:36:53,278 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 26 mSDsluCounter, 167 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 209 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:53,278 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 209 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:36:53,279 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 150 states. [2024-11-18 13:36:53,293 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 150 to 147. [2024-11-18 13:36:53,294 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 147 states, 93 states have (on average 1.2688172043010753) internal successors, (118), 94 states have internal predecessors, (118), 45 states have call successors, (45), 8 states have call predecessors, (45), 8 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-11-18 13:36:53,295 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 147 states to 147 states and 207 transitions. [2024-11-18 13:36:53,295 INFO L78 Accepts]: Start accepts. Automaton has 147 states and 207 transitions. Word has length 43 [2024-11-18 13:36:53,295 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:53,295 INFO L471 AbstractCegarLoop]: Abstraction has 147 states and 207 transitions. [2024-11-18 13:36:53,295 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 6 states have internal predecessors, (23), 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:36:53,296 INFO L276 IsEmpty]: Start isEmpty. Operand 147 states and 207 transitions. [2024-11-18 13:36:53,296 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-18 13:36:53,296 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:53,296 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 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:53,309 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-18 13:36:53,497 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:53,497 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:53,497 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:53,498 INFO L85 PathProgramCache]: Analyzing trace with hash -1796916029, now seen corresponding path program 2 times [2024-11-18 13:36:53,498 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:53,498 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1357756355] [2024-11-18 13:36:53,498 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:36:53,498 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:53,507 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:36:53,507 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:53,592 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 9 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-18 13:36:53,592 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:53,592 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1357756355] [2024-11-18 13:36:53,592 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1357756355] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:53,593 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1658345779] [2024-11-18 13:36:53,593 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:36:53,593 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:53,593 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:53,595 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:36:53,596 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:36:53,655 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:36:53,655 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:53,656 INFO L255 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-18 13:36:53,657 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:53,685 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-18 13:36:53,685 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:36:53,685 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1658345779] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:36:53,686 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:36:53,686 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2024-11-18 13:36:53,686 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1905608776] [2024-11-18 13:36:53,686 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:36:53,686 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:36:53,688 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:53,689 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:36:53,689 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-18 13:36:53,689 INFO L87 Difference]: Start difference. First operand 147 states and 207 transitions. Second operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 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:36:53,767 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:53,768 INFO L93 Difference]: Finished difference Result 186 states and 259 transitions. [2024-11-18 13:36:53,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-18 13:36:53,769 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 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 43 [2024-11-18 13:36:53,769 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:53,770 INFO L225 Difference]: With dead ends: 186 [2024-11-18 13:36:53,771 INFO L226 Difference]: Without dead ends: 130 [2024-11-18 13:36:53,772 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-11-18 13:36:53,772 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 18 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 62 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:53,773 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 160 Invalid, 62 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:36:53,773 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2024-11-18 13:36:53,788 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 122. [2024-11-18 13:36:53,788 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 76 states have (on average 1.2105263157894737) internal successors, (92), 77 states have internal predecessors, (92), 37 states have call successors, (37), 8 states have call predecessors, (37), 8 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2024-11-18 13:36:53,790 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 165 transitions. [2024-11-18 13:36:53,790 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 165 transitions. Word has length 43 [2024-11-18 13:36:53,790 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:53,790 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 165 transitions. [2024-11-18 13:36:53,792 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 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:36:53,792 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 165 transitions. [2024-11-18 13:36:53,792 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-11-18 13:36:53,794 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:53,794 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, 1] [2024-11-18 13:36:53,801 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-18 13:36:53,995 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,SelfDestructingSolverStorable8 [2024-11-18 13:36:53,996 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:53,996 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:53,996 INFO L85 PathProgramCache]: Analyzing trace with hash -1189241395, now seen corresponding path program 1 times [2024-11-18 13:36:53,996 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:53,996 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1304951264] [2024-11-18 13:36:53,996 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:53,996 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:54,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:36:54,005 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2103161654] [2024-11-18 13:36:54,005 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:54,005 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:54,005 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:54,007 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:36:54,008 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:36:54,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:54,055 INFO L255 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-18 13:36:54,056 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:54,089 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:36:54,090 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:36:54,090 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:54,090 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1304951264] [2024-11-18 13:36:54,090 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:54,090 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2103161654] [2024-11-18 13:36:54,090 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2103161654] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:36:54,090 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:36:54,090 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:36:54,091 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1354291309] [2024-11-18 13:36:54,091 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:36:54,091 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:36:54,091 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:54,092 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:36:54,092 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:36:54,093 INFO L87 Difference]: Start difference. First operand 122 states and 165 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, (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:36:54,143 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:54,143 INFO L93 Difference]: Finished difference Result 180 states and 262 transitions. [2024-11-18 13:36:54,144 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:36:54,144 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, (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 48 [2024-11-18 13:36:54,145 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:54,146 INFO L225 Difference]: With dead ends: 180 [2024-11-18 13:36:54,146 INFO L226 Difference]: Without dead ends: 178 [2024-11-18 13:36:54,146 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 44 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:36:54,147 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 4 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:54,147 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 132 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:36:54,147 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2024-11-18 13:36:54,171 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 166. [2024-11-18 13:36:54,171 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 166 states, 87 states have (on average 1.1839080459770115) internal successors, (103), 96 states have internal predecessors, (103), 69 states have call successors, (69), 9 states have call predecessors, (69), 9 states have return successors, (68), 60 states have call predecessors, (68), 68 states have call successors, (68) [2024-11-18 13:36:54,172 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 166 states to 166 states and 240 transitions. [2024-11-18 13:36:54,173 INFO L78 Accepts]: Start accepts. Automaton has 166 states and 240 transitions. Word has length 48 [2024-11-18 13:36:54,173 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:54,173 INFO L471 AbstractCegarLoop]: Abstraction has 166 states and 240 transitions. [2024-11-18 13:36:54,173 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, (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:36:54,173 INFO L276 IsEmpty]: Start isEmpty. Operand 166 states and 240 transitions. [2024-11-18 13:36:54,174 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-11-18 13:36:54,175 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:54,175 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, 1, 1, 1] [2024-11-18 13:36:54,188 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:54,379 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-18 13:36:54,380 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:54,380 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:54,380 INFO L85 PathProgramCache]: Analyzing trace with hash -828341661, now seen corresponding path program 1 times [2024-11-18 13:36:54,380 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:54,380 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1147288961] [2024-11-18 13:36:54,380 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:54,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:54,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:36:54,400 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1743331911] [2024-11-18 13:36:54,400 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:54,400 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:54,400 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:54,402 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:36:54,403 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:36:54,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:54,448 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-11-18 13:36:54,449 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:54,949 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 14 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-18 13:36:54,950 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:56,044 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-18 13:36:56,044 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:56,045 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1147288961] [2024-11-18 13:36:56,045 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:56,045 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1743331911] [2024-11-18 13:36:56,045 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1743331911] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:56,045 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:36:56,045 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-11-18 13:36:56,045 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1790893106] [2024-11-18 13:36:56,045 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:56,045 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-18 13:36:56,045 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:56,055 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-18 13:36:56,055 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2024-11-18 13:36:56,056 INFO L87 Difference]: Start difference. First operand 166 states and 240 transitions. Second operand has 23 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 20 states have internal predecessors, (43), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-18 13:36:58,610 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:58,610 INFO L93 Difference]: Finished difference Result 445 states and 665 transitions. [2024-11-18 13:36:58,610 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2024-11-18 13:36:58,611 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 20 states have internal predecessors, (43), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 60 [2024-11-18 13:36:58,611 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:58,614 INFO L225 Difference]: With dead ends: 445 [2024-11-18 13:36:58,614 INFO L226 Difference]: Without dead ends: 342 [2024-11-18 13:36:58,615 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 429 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=398, Invalid=1672, Unknown=0, NotChecked=0, Total=2070 [2024-11-18 13:36:58,616 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 172 mSDsluCounter, 327 mSDsCounter, 0 mSdLazyCounter, 556 mSolverCounterSat, 131 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 180 SdHoareTripleChecker+Valid, 357 SdHoareTripleChecker+Invalid, 687 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 131 IncrementalHoareTripleChecker+Valid, 556 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:58,616 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [180 Valid, 357 Invalid, 687 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [131 Valid, 556 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2024-11-18 13:36:58,616 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 342 states. [2024-11-18 13:36:58,683 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 342 to 256. [2024-11-18 13:36:58,683 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 256 states, 150 states have (on average 1.2066666666666668) internal successors, (181), 157 states have internal predecessors, (181), 93 states have call successors, (93), 12 states have call predecessors, (93), 12 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-18 13:36:58,685 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 256 states to 256 states and 366 transitions. [2024-11-18 13:36:58,685 INFO L78 Accepts]: Start accepts. Automaton has 256 states and 366 transitions. Word has length 60 [2024-11-18 13:36:58,686 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:58,686 INFO L471 AbstractCegarLoop]: Abstraction has 256 states and 366 transitions. [2024-11-18 13:36:58,686 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 20 states have internal predecessors, (43), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-18 13:36:58,686 INFO L276 IsEmpty]: Start isEmpty. Operand 256 states and 366 transitions. [2024-11-18 13:36:58,687 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-11-18 13:36:58,687 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:58,687 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 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:36:58,700 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-18 13:36:58,891 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,SelfDestructingSolverStorable10 [2024-11-18 13:36:58,892 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:58,892 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:58,892 INFO L85 PathProgramCache]: Analyzing trace with hash 1607561902, now seen corresponding path program 1 times [2024-11-18 13:36:58,892 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:58,892 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1868303566] [2024-11-18 13:36:58,892 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:58,892 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:58,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:36:58,903 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [492524613] [2024-11-18 13:36:58,903 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:58,903 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:58,904 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:58,905 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:36:58,906 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:36:58,948 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:58,949 INFO L255 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-18 13:36:58,951 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:59,002 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 108 trivial. 0 not checked. [2024-11-18 13:36:59,003 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:59,058 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2024-11-18 13:36:59,058 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:59,058 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1868303566] [2024-11-18 13:36:59,058 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:59,058 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [492524613] [2024-11-18 13:36:59,058 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [492524613] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:59,059 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:36:59,059 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-18 13:36:59,059 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [489330605] [2024-11-18 13:36:59,059 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:36:59,059 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:36:59,059 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:59,060 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:36:59,060 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-18 13:36:59,060 INFO L87 Difference]: Start difference. First operand 256 states and 366 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (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:36:59,151 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:59,152 INFO L93 Difference]: Finished difference Result 262 states and 371 transitions. [2024-11-18 13:36:59,152 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:36:59,152 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (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 70 [2024-11-18 13:36:59,152 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:59,154 INFO L225 Difference]: With dead ends: 262 [2024-11-18 13:36:59,154 INFO L226 Difference]: Without dead ends: 260 [2024-11-18 13:36:59,154 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 131 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:36:59,155 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 4 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 127 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:36:59,155 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 127 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:36:59,155 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 260 states. [2024-11-18 13:36:59,210 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 260 to 260. [2024-11-18 13:36:59,210 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 260 states, 153 states have (on average 1.2026143790849673) internal successors, (184), 160 states have internal predecessors, (184), 93 states have call successors, (93), 13 states have call predecessors, (93), 13 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-18 13:36:59,212 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 260 states to 260 states and 369 transitions. [2024-11-18 13:36:59,212 INFO L78 Accepts]: Start accepts. Automaton has 260 states and 369 transitions. Word has length 70 [2024-11-18 13:36:59,212 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:59,212 INFO L471 AbstractCegarLoop]: Abstraction has 260 states and 369 transitions. [2024-11-18 13:36:59,212 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (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:36:59,212 INFO L276 IsEmpty]: Start isEmpty. Operand 260 states and 369 transitions. [2024-11-18 13:36:59,213 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-11-18 13:36:59,213 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:59,213 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:59,225 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:36:59,413 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,SelfDestructingSolverStorable11 [2024-11-18 13:36:59,414 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:59,414 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:59,414 INFO L85 PathProgramCache]: Analyzing trace with hash -1439093215, now seen corresponding path program 1 times [2024-11-18 13:36:59,414 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:59,414 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [936983166] [2024-11-18 13:36:59,414 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:59,414 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:59,424 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:36:59,425 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [255072020] [2024-11-18 13:36:59,425 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:59,425 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:59,425 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:59,426 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:36:59,427 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:36:59,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:59,467 INFO L255 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 50 conjuncts are in the unsatisfiable core [2024-11-18 13:36:59,469 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:59,825 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 16 proven. 31 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-18 13:36:59,826 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:37:00,055 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2024-11-18 13:37:00,055 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:37:00,055 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [936983166] [2024-11-18 13:37:00,055 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:37:00,055 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [255072020] [2024-11-18 13:37:00,055 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [255072020] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:37:00,055 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:37:00,055 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2024-11-18 13:37:00,055 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1319618760] [2024-11-18 13:37:00,056 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:37:00,056 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-18 13:37:00,056 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:37:00,056 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-18 13:37:00,057 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2024-11-18 13:37:00,057 INFO L87 Difference]: Start difference. First operand 260 states and 369 transitions. Second operand has 22 states, 22 states have (on average 2.772727272727273) internal successors, (61), 19 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-18 13:37:02,390 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:37:02,390 INFO L93 Difference]: Finished difference Result 322 states and 459 transitions. [2024-11-18 13:37:02,391 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-18 13:37:02,391 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.772727272727273) internal successors, (61), 19 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 68 [2024-11-18 13:37:02,391 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:37:02,393 INFO L225 Difference]: With dead ends: 322 [2024-11-18 13:37:02,393 INFO L226 Difference]: Without dead ends: 320 [2024-11-18 13:37:02,394 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 123 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 193 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=190, Invalid=932, Unknown=0, NotChecked=0, Total=1122 [2024-11-18 13:37:02,394 INFO L432 NwaCegarLoop]: 52 mSDtfsCounter, 115 mSDsluCounter, 489 mSDsCounter, 0 mSdLazyCounter, 633 mSolverCounterSat, 97 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 117 SdHoareTripleChecker+Valid, 541 SdHoareTripleChecker+Invalid, 730 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 97 IncrementalHoareTripleChecker+Valid, 633 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2024-11-18 13:37:02,394 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [117 Valid, 541 Invalid, 730 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [97 Valid, 633 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2024-11-18 13:37:02,395 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 320 states. [2024-11-18 13:37:02,465 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 320 to 268. [2024-11-18 13:37:02,465 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 268 states, 159 states have (on average 1.1949685534591195) internal successors, (190), 166 states have internal predecessors, (190), 93 states have call successors, (93), 15 states have call predecessors, (93), 15 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-18 13:37:02,467 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 268 states to 268 states and 375 transitions. [2024-11-18 13:37:02,467 INFO L78 Accepts]: Start accepts. Automaton has 268 states and 375 transitions. Word has length 68 [2024-11-18 13:37:02,467 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:37:02,467 INFO L471 AbstractCegarLoop]: Abstraction has 268 states and 375 transitions. [2024-11-18 13:37:02,467 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.772727272727273) internal successors, (61), 19 states have internal predecessors, (61), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-18 13:37:02,467 INFO L276 IsEmpty]: Start isEmpty. Operand 268 states and 375 transitions. [2024-11-18 13:37:02,468 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-18 13:37:02,468 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:37:02,468 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:37:02,480 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:37:02,672 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,SelfDestructingSolverStorable12 [2024-11-18 13:37:02,673 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:37:02,673 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:37:02,673 INFO L85 PathProgramCache]: Analyzing trace with hash 798002477, now seen corresponding path program 2 times [2024-11-18 13:37:02,673 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:37:02,673 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1607666758] [2024-11-18 13:37:02,673 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:37:02,673 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:37:02,686 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:37:02,686 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:37:02,752 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2024-11-18 13:37:02,753 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:37:02,753 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1607666758] [2024-11-18 13:37:02,753 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1607666758] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:37:02,753 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:37:02,753 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:37:02,753 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1868527769] [2024-11-18 13:37:02,753 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:37:02,753 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:37:02,754 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:37:02,754 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:37:02,754 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:37:02,754 INFO L87 Difference]: Start difference. First operand 268 states and 375 transitions. Second operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-18 13:37:02,885 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:37:02,885 INFO L93 Difference]: Finished difference Result 459 states and 645 transitions. [2024-11-18 13:37:02,886 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:37:02,886 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 73 [2024-11-18 13:37:02,886 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:37:02,887 INFO L225 Difference]: With dead ends: 459 [2024-11-18 13:37:02,887 INFO L226 Difference]: Without dead ends: 289 [2024-11-18 13:37:02,888 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:37:02,888 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 0 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:37:02,888 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 121 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:37:02,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 289 states. [2024-11-18 13:37:02,952 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 289 to 277. [2024-11-18 13:37:02,952 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 277 states, 168 states have (on average 1.1964285714285714) internal successors, (201), 169 states have internal predecessors, (201), 93 states have call successors, (93), 15 states have call predecessors, (93), 15 states have return successors, (92), 92 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-18 13:37:02,953 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 277 states to 277 states and 386 transitions. [2024-11-18 13:37:02,954 INFO L78 Accepts]: Start accepts. Automaton has 277 states and 386 transitions. Word has length 73 [2024-11-18 13:37:02,954 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:37:02,954 INFO L471 AbstractCegarLoop]: Abstraction has 277 states and 386 transitions. [2024-11-18 13:37:02,954 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-18 13:37:02,954 INFO L276 IsEmpty]: Start isEmpty. Operand 277 states and 386 transitions. [2024-11-18 13:37:02,954 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-18 13:37:02,954 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:37:02,954 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:37:02,955 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13 [2024-11-18 13:37:02,955 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:37:02,955 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:37:02,955 INFO L85 PathProgramCache]: Analyzing trace with hash -1622368081, now seen corresponding path program 3 times [2024-11-18 13:37:02,955 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:37:02,955 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2107367385] [2024-11-18 13:37:02,955 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:37:02,956 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:37:02,991 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-18 13:37:02,992 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:37:02,993 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1621739011] [2024-11-18 13:37:02,993 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:37:02,993 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:37:02,993 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:37:02,995 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:37:02,996 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:37:03,036 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-18 13:37:03,036 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:37:03,037 INFO L255 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 69 conjuncts are in the unsatisfiable core [2024-11-18 13:37:03,039 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:37:03,774 INFO L134 CoverageAnalysis]: Checked inductivity of 96 backedges. 27 proven. 26 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2024-11-18 13:37:03,774 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:37:05,284 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:37:05,284 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2107367385] [2024-11-18 13:37:05,284 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:37:05,284 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1621739011] [2024-11-18 13:37:05,284 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1621739011] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:37:05,284 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:37:05,284 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2024-11-18 13:37:05,284 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [335294335] [2024-11-18 13:37:05,284 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:37:05,285 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-18 13:37:05,285 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:37:05,285 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-18 13:37:05,285 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=632, Unknown=0, NotChecked=0, Total=756 [2024-11-18 13:37:05,285 INFO L87 Difference]: Start difference. First operand 277 states and 386 transitions. Second operand has 19 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 5 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-18 13:37:05,830 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:37:05,830 INFO L93 Difference]: Finished difference Result 344 states and 469 transitions. [2024-11-18 13:37:05,830 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-18 13:37:05,830 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 5 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 73 [2024-11-18 13:37:05,831 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:37:05,832 INFO L225 Difference]: With dead ends: 344 [2024-11-18 13:37:05,832 INFO L226 Difference]: Without dead ends: 342 [2024-11-18 13:37:05,833 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 65 SyntacticMatches, 1 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 255 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=204, Invalid=986, Unknown=0, NotChecked=0, Total=1190 [2024-11-18 13:37:05,833 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 67 mSDsluCounter, 368 mSDsCounter, 0 mSdLazyCounter, 526 mSolverCounterSat, 51 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 83 SdHoareTripleChecker+Valid, 406 SdHoareTripleChecker+Invalid, 577 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 526 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-18 13:37:05,833 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [83 Valid, 406 Invalid, 577 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 526 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-18 13:37:05,834 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 342 states. [2024-11-18 13:37:05,920 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 342 to 332. [2024-11-18 13:37:05,921 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 332 states, 202 states have (on average 1.188118811881188) internal successors, (240), 203 states have internal predecessors, (240), 109 states have call successors, (109), 20 states have call predecessors, (109), 20 states have return successors, (108), 108 states have call predecessors, (108), 108 states have call successors, (108) [2024-11-18 13:37:05,922 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 332 states to 332 states and 457 transitions. [2024-11-18 13:37:05,922 INFO L78 Accepts]: Start accepts. Automaton has 332 states and 457 transitions. Word has length 73 [2024-11-18 13:37:05,922 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:37:05,922 INFO L471 AbstractCegarLoop]: Abstraction has 332 states and 457 transitions. [2024-11-18 13:37:05,923 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 2.1666666666666665) internal successors, (39), 16 states have internal predecessors, (39), 5 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-18 13:37:05,923 INFO L276 IsEmpty]: Start isEmpty. Operand 332 states and 457 transitions. [2024-11-18 13:37:05,923 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-18 13:37:05,923 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:37:05,923 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:37:05,936 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2024-11-18 13:37:06,124 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:37:06,124 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:37:06,124 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:37:06,124 INFO L85 PathProgramCache]: Analyzing trace with hash 160585404, now seen corresponding path program 1 times [2024-11-18 13:37:06,125 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:37:06,125 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1824653014] [2024-11-18 13:37:06,125 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:37:06,125 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:37:06,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:37:06,135 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [534575749] [2024-11-18 13:37:06,135 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:37:06,135 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:37:06,135 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:37:06,137 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:37:06,138 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:37:06,183 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:37:06,184 INFO L255 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 64 conjuncts are in the unsatisfiable core [2024-11-18 13:37:06,186 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:37:07,109 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 36 proven. 29 refuted. 0 times theorem prover too weak. 106 trivial. 0 not checked. [2024-11-18 13:37:07,110 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:37:08,584 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:37:08,584 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1824653014] [2024-11-18 13:37:08,585 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:37:08,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [534575749] [2024-11-18 13:37:08,585 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [534575749] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:37:08,585 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:37:08,585 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2024-11-18 13:37:08,585 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1347740124] [2024-11-18 13:37:08,585 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:37:08,585 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-18 13:37:08,585 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:37:08,586 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-18 13:37:08,586 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=664, Unknown=0, NotChecked=0, Total=756 [2024-11-18 13:37:08,586 INFO L87 Difference]: Start difference. First operand 332 states and 457 transitions. Second operand has 21 states, 20 states have (on average 1.9) internal successors, (38), 19 states have internal predecessors, (38), 6 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-18 13:37:09,947 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:37:09,947 INFO L93 Difference]: Finished difference Result 412 states and 572 transitions. [2024-11-18 13:37:09,948 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-18 13:37:09,948 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 1.9) internal successors, (38), 19 states have internal predecessors, (38), 6 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) Word has length 87 [2024-11-18 13:37:09,949 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:37:09,950 INFO L225 Difference]: With dead ends: 412 [2024-11-18 13:37:09,951 INFO L226 Difference]: Without dead ends: 405 [2024-11-18 13:37:09,951 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 82 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 253 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=165, Invalid=1167, Unknown=0, NotChecked=0, Total=1332 [2024-11-18 13:37:09,951 INFO L432 NwaCegarLoop]: 51 mSDtfsCounter, 83 mSDsluCounter, 564 mSDsCounter, 0 mSdLazyCounter, 1010 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 99 SdHoareTripleChecker+Valid, 615 SdHoareTripleChecker+Invalid, 1068 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 1010 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-18 13:37:09,952 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [99 Valid, 615 Invalid, 1068 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 1010 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-18 13:37:09,953 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 405 states. [2024-11-18 13:37:10,069 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 405 to 393. [2024-11-18 13:37:10,070 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 393 states, 233 states have (on average 1.201716738197425) internal successors, (280), 234 states have internal predecessors, (280), 137 states have call successors, (137), 22 states have call predecessors, (137), 22 states have return successors, (136), 136 states have call predecessors, (136), 136 states have call successors, (136) [2024-11-18 13:37:10,073 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 393 states to 393 states and 553 transitions. [2024-11-18 13:37:10,074 INFO L78 Accepts]: Start accepts. Automaton has 393 states and 553 transitions. Word has length 87 [2024-11-18 13:37:10,074 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:37:10,074 INFO L471 AbstractCegarLoop]: Abstraction has 393 states and 553 transitions. [2024-11-18 13:37:10,074 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 1.9) internal successors, (38), 19 states have internal predecessors, (38), 6 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-18 13:37:10,075 INFO L276 IsEmpty]: Start isEmpty. Operand 393 states and 553 transitions. [2024-11-18 13:37:10,076 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-11-18 13:37:10,076 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:37:10,076 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:37:10,089 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2024-11-18 13:37:10,276 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:37:10,277 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:37:10,277 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:37:10,277 INFO L85 PathProgramCache]: Analyzing trace with hash -275231594, now seen corresponding path program 1 times [2024-11-18 13:37:10,277 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:37:10,277 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [60447837] [2024-11-18 13:37:10,277 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:37:10,277 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:37:10,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:37:10,299 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1005568470] [2024-11-18 13:37:10,300 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:37:10,300 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:37:10,300 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:37:10,301 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:37:10,303 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:37:10,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:37:10,348 INFO L255 TraceCheckSpWp]: Trace formula consists of 203 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-18 13:37:10,351 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:37:10,579 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 26 proven. 19 refuted. 0 times theorem prover too weak. 195 trivial. 0 not checked. [2024-11-18 13:37:10,579 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:37:10,948 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 22 proven. 14 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2024-11-18 13:37:10,948 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:37:10,948 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [60447837] [2024-11-18 13:37:10,948 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:37:10,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1005568470] [2024-11-18 13:37:10,949 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1005568470] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:37:10,949 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:37:10,949 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 10] total 22 [2024-11-18 13:37:10,949 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2010903979] [2024-11-18 13:37:10,949 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:37:10,949 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-18 13:37:10,949 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:37:10,950 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-18 13:37:10,950 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=373, Unknown=0, NotChecked=0, Total=462 [2024-11-18 13:37:10,950 INFO L87 Difference]: Start difference. First operand 393 states and 553 transitions. Second operand has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-18 13:37:12,954 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:37:12,954 INFO L93 Difference]: Finished difference Result 943 states and 1484 transitions. [2024-11-18 13:37:12,957 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2024-11-18 13:37:12,957 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 90 [2024-11-18 13:37:12,958 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:37:12,962 INFO L225 Difference]: With dead ends: 943 [2024-11-18 13:37:12,962 INFO L226 Difference]: Without dead ends: 941 [2024-11-18 13:37:12,963 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 206 GetRequests, 159 SyntacticMatches, 0 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 561 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=528, Invalid=1824, Unknown=0, NotChecked=0, Total=2352 [2024-11-18 13:37:12,963 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 148 mSDsluCounter, 460 mSDsCounter, 0 mSdLazyCounter, 517 mSolverCounterSat, 125 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 152 SdHoareTripleChecker+Valid, 504 SdHoareTripleChecker+Invalid, 642 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 125 IncrementalHoareTripleChecker+Valid, 517 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-18 13:37:12,964 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [152 Valid, 504 Invalid, 642 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [125 Valid, 517 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-18 13:37:12,965 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 941 states. [2024-11-18 13:37:13,289 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 941 to 775. [2024-11-18 13:37:13,290 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 775 states, 388 states have (on average 1.291237113402062) internal successors, (501), 389 states have internal predecessors, (501), 361 states have call successors, (361), 25 states have call predecessors, (361), 25 states have return successors, (360), 360 states have call predecessors, (360), 360 states have call successors, (360) [2024-11-18 13:37:13,293 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 775 states to 775 states and 1222 transitions. [2024-11-18 13:37:13,294 INFO L78 Accepts]: Start accepts. Automaton has 775 states and 1222 transitions. Word has length 90 [2024-11-18 13:37:13,294 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:37:13,294 INFO L471 AbstractCegarLoop]: Abstraction has 775 states and 1222 transitions. [2024-11-18 13:37:13,294 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-18 13:37:13,294 INFO L276 IsEmpty]: Start isEmpty. Operand 775 states and 1222 transitions. [2024-11-18 13:37:13,295 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-11-18 13:37:13,295 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:37:13,295 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 3, 3, 3, 3, 3, 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:37:13,315 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:37:13,495 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,SelfDestructingSolverStorable16 [2024-11-18 13:37:13,496 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:37:13,496 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:37:13,496 INFO L85 PathProgramCache]: Analyzing trace with hash 1599365144, now seen corresponding path program 1 times [2024-11-18 13:37:13,496 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:37:13,496 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1552945220] [2024-11-18 13:37:13,496 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:37:13,496 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:37:13,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:37:13,507 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [68801398] [2024-11-18 13:37:13,507 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:37:13,507 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:37:13,507 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:37:13,509 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:37:13,510 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:37:13,550 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:37:13,551 INFO L255 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-11-18 13:37:13,553 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:37:14,005 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 24 proven. 23 refuted. 0 times theorem prover too weak. 159 trivial. 0 not checked. [2024-11-18 13:37:14,005 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:37:15,364 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 18 proven. 20 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-11-18 13:37:15,365 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:37:15,365 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1552945220] [2024-11-18 13:37:15,365 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:37:15,365 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [68801398] [2024-11-18 13:37:15,365 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [68801398] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:37:15,365 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:37:15,365 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-11-18 13:37:15,365 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [76892101] [2024-11-18 13:37:15,365 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:37:15,365 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-18 13:37:15,365 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:37:15,366 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-18 13:37:15,366 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=426, Unknown=0, NotChecked=0, Total=506 [2024-11-18 13:37:15,366 INFO L87 Difference]: Start difference. First operand 775 states and 1222 transitions. Second operand has 23 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 20 states have internal predecessors, (53), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-18 13:37:19,591 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.83s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-18 13:37:24,378 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:37:24,378 INFO L93 Difference]: Finished difference Result 1070 states and 1687 transitions. [2024-11-18 13:37:24,379 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2024-11-18 13:37:24,379 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 20 states have internal predecessors, (53), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 90 [2024-11-18 13:37:24,379 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:37:24,385 INFO L225 Difference]: With dead ends: 1070 [2024-11-18 13:37:24,385 INFO L226 Difference]: Without dead ends: 1068 [2024-11-18 13:37:24,386 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 215 GetRequests, 157 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 766 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=711, Invalid=2829, Unknown=0, NotChecked=0, Total=3540 [2024-11-18 13:37:24,386 INFO L432 NwaCegarLoop]: 52 mSDtfsCounter, 179 mSDsluCounter, 563 mSDsCounter, 0 mSdLazyCounter, 803 mSolverCounterSat, 185 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 179 SdHoareTripleChecker+Valid, 615 SdHoareTripleChecker+Invalid, 988 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 185 IncrementalHoareTripleChecker+Valid, 803 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.4s IncrementalHoareTripleChecker+Time [2024-11-18 13:37:24,386 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [179 Valid, 615 Invalid, 988 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [185 Valid, 803 Invalid, 0 Unknown, 0 Unchecked, 4.4s Time] [2024-11-18 13:37:24,387 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1068 states. [2024-11-18 13:37:24,950 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1068 to 980. [2024-11-18 13:37:24,952 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 980 states, 493 states have (on average 1.3022312373225151) internal successors, (642), 494 states have internal predecessors, (642), 457 states have call successors, (457), 29 states have call predecessors, (457), 29 states have return successors, (456), 456 states have call predecessors, (456), 456 states have call successors, (456) [2024-11-18 13:37:24,956 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 980 states to 980 states and 1555 transitions. [2024-11-18 13:37:24,958 INFO L78 Accepts]: Start accepts. Automaton has 980 states and 1555 transitions. Word has length 90 [2024-11-18 13:37:24,958 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:37:24,958 INFO L471 AbstractCegarLoop]: Abstraction has 980 states and 1555 transitions. [2024-11-18 13:37:24,958 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.3043478260869565) internal successors, (53), 20 states have internal predecessors, (53), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-18 13:37:24,958 INFO L276 IsEmpty]: Start isEmpty. Operand 980 states and 1555 transitions. [2024-11-18 13:37:24,960 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2024-11-18 13:37:24,960 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:37:24,961 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:37:24,974 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:37:25,161 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-18 13:37:25,161 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:37:25,161 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:37:25,162 INFO L85 PathProgramCache]: Analyzing trace with hash -1330396859, now seen corresponding path program 2 times [2024-11-18 13:37:25,162 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:37:25,162 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [285974343] [2024-11-18 13:37:25,162 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:37:25,162 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:37:25,176 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:37:25,176 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:37:25,324 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-11-18 13:37:25,324 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:37:25,324 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [285974343] [2024-11-18 13:37:25,324 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [285974343] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:37:25,325 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [744026319] [2024-11-18 13:37:25,325 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:37:25,325 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:37:25,325 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:37:25,326 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:37:25,327 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:37:25,377 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:37:25,377 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:37:25,378 INFO L255 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-18 13:37:25,379 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:37:25,435 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-11-18 13:37:25,435 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:37:25,518 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 38 proven. 16 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-11-18 13:37:25,519 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [744026319] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:37:25,519 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:37:25,519 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 13 [2024-11-18 13:37:25,519 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1259513932] [2024-11-18 13:37:25,519 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:37:25,519 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-18 13:37:25,519 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:37:25,520 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-18 13:37:25,520 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2024-11-18 13:37:25,520 INFO L87 Difference]: Start difference. First operand 980 states and 1555 transitions. Second operand has 13 states, 13 states have (on average 3.4615384615384617) internal successors, (45), 13 states have internal predecessors, (45), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-18 13:37:26,420 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:37:26,420 INFO L93 Difference]: Finished difference Result 1091 states and 1723 transitions. [2024-11-18 13:37:26,420 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-18 13:37:26,421 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 3.4615384615384617) internal successors, (45), 13 states have internal predecessors, (45), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 95 [2024-11-18 13:37:26,421 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:37:26,426 INFO L225 Difference]: With dead ends: 1091 [2024-11-18 13:37:26,426 INFO L226 Difference]: Without dead ends: 1084 [2024-11-18 13:37:26,426 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 224 GetRequests, 187 SyntacticMatches, 8 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 164 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=214, Invalid=716, Unknown=0, NotChecked=0, Total=930 [2024-11-18 13:37:26,427 INFO L432 NwaCegarLoop]: 57 mSDtfsCounter, 80 mSDsluCounter, 419 mSDsCounter, 0 mSdLazyCounter, 318 mSolverCounterSat, 69 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 84 SdHoareTripleChecker+Valid, 476 SdHoareTripleChecker+Invalid, 387 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 69 IncrementalHoareTripleChecker+Valid, 318 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:37:26,427 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [84 Valid, 476 Invalid, 387 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [69 Valid, 318 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:37:26,428 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1084 states. [2024-11-18 13:37:27,050 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1084 to 949. [2024-11-18 13:37:27,052 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 949 states, 470 states have (on average 1.3085106382978724) internal successors, (615), 471 states have internal predecessors, (615), 449 states have call successors, (449), 29 states have call predecessors, (449), 29 states have return successors, (448), 448 states have call predecessors, (448), 448 states have call successors, (448) [2024-11-18 13:37:27,055 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 949 states to 949 states and 1512 transitions. [2024-11-18 13:37:27,057 INFO L78 Accepts]: Start accepts. Automaton has 949 states and 1512 transitions. Word has length 95 [2024-11-18 13:37:27,057 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:37:27,057 INFO L471 AbstractCegarLoop]: Abstraction has 949 states and 1512 transitions. [2024-11-18 13:37:27,057 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 3.4615384615384617) internal successors, (45), 13 states have internal predecessors, (45), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-18 13:37:27,057 INFO L276 IsEmpty]: Start isEmpty. Operand 949 states and 1512 transitions. [2024-11-18 13:37:27,058 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2024-11-18 13:37:27,058 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:37:27,058 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 5, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:37:27,071 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2024-11-18 13:37:27,259 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:37:27,259 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:37:27,259 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:37:27,260 INFO L85 PathProgramCache]: Analyzing trace with hash -577787487, now seen corresponding path program 4 times [2024-11-18 13:37:27,260 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:37:27,260 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [565497656] [2024-11-18 13:37:27,260 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:37:27,260 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:37:27,277 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:37:27,278 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:37:27,278 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2126560240] [2024-11-18 13:37:27,279 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:37:27,279 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:37:27,279 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:37:27,280 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:37:27,288 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:37:27,336 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:37:27,336 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:37:27,338 INFO L255 TraceCheckSpWp]: Trace formula consists of 217 conjuncts, 56 conjuncts are in the unsatisfiable core [2024-11-18 13:37:27,340 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:37:28,036 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 32 proven. 50 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2024-11-18 13:37:28,036 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:37:28,952 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:37:28,952 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [565497656] [2024-11-18 13:37:28,952 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:37:28,953 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2126560240] [2024-11-18 13:37:28,953 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2126560240] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:37:28,953 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:37:28,953 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2024-11-18 13:37:28,953 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1438405590] [2024-11-18 13:37:28,953 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:37:28,953 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-18 13:37:28,953 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:37:28,954 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-18 13:37:28,954 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=440, Unknown=0, NotChecked=0, Total=506 [2024-11-18 13:37:28,954 INFO L87 Difference]: Start difference. First operand 949 states and 1512 transitions. Second operand has 18 states, 18 states have (on average 2.2777777777777777) internal successors, (41), 16 states have internal predecessors, (41), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2024-11-18 13:37:30,256 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:37:30,257 INFO L93 Difference]: Finished difference Result 1059 states and 1670 transitions. [2024-11-18 13:37:30,257 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-18 13:37:30,257 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 2.2777777777777777) internal successors, (41), 16 states have internal predecessors, (41), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 98 [2024-11-18 13:37:30,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:37:30,262 INFO L225 Difference]: With dead ends: 1059 [2024-11-18 13:37:30,262 INFO L226 Difference]: Without dead ends: 1057 [2024-11-18 13:37:30,263 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 104 SyntacticMatches, 2 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 160 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=144, Invalid=912, Unknown=0, NotChecked=0, Total=1056 [2024-11-18 13:37:30,263 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 58 mSDsluCounter, 547 mSDsCounter, 0 mSdLazyCounter, 626 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 594 SdHoareTripleChecker+Invalid, 663 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 626 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-18 13:37:30,263 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 594 Invalid, 663 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 626 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-18 13:37:30,264 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1057 states. [2024-11-18 13:37:30,869 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1057 to 957. [2024-11-18 13:37:30,871 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 957 states, 476 states have (on average 1.3046218487394958) internal successors, (621), 477 states have internal predecessors, (621), 449 states have call successors, (449), 31 states have call predecessors, (449), 31 states have return successors, (448), 448 states have call predecessors, (448), 448 states have call successors, (448) [2024-11-18 13:37:30,874 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 957 states to 957 states and 1518 transitions. [2024-11-18 13:37:30,875 INFO L78 Accepts]: Start accepts. Automaton has 957 states and 1518 transitions. Word has length 98 [2024-11-18 13:37:30,875 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:37:30,876 INFO L471 AbstractCegarLoop]: Abstraction has 957 states and 1518 transitions. [2024-11-18 13:37:30,876 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 2.2777777777777777) internal successors, (41), 16 states have internal predecessors, (41), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2024-11-18 13:37:30,876 INFO L276 IsEmpty]: Start isEmpty. Operand 957 states and 1518 transitions. [2024-11-18 13:37:30,877 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2024-11-18 13:37:30,877 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:37:30,877 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 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, 1, 1, 1, 1] [2024-11-18 13:37:30,890 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2024-11-18 13:37:31,081 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:37:31,082 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:37:31,082 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:37:31,082 INFO L85 PathProgramCache]: Analyzing trace with hash 1084123749, now seen corresponding path program 2 times [2024-11-18 13:37:31,082 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:37:31,082 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [448012223] [2024-11-18 13:37:31,082 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:37:31,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:37:31,093 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:37:31,093 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:37:31,094 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [633976096] [2024-11-18 13:37:31,094 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:37:31,094 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:37:31,094 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:37:31,096 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:37:31,097 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:37:31,177 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:37:31,177 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:37:31,178 INFO L255 TraceCheckSpWp]: Trace formula consists of 237 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-11-18 13:37:31,180 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:37:31,663 INFO L134 CoverageAnalysis]: Checked inductivity of 334 backedges. 24 proven. 22 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-18 13:37:31,664 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:37:33,557 INFO L134 CoverageAnalysis]: Checked inductivity of 334 backedges. 24 proven. 22 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-18 13:37:33,557 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:37:33,558 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [448012223] [2024-11-18 13:37:33,558 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:37:33,558 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [633976096] [2024-11-18 13:37:33,558 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [633976096] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:37:33,558 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:37:33,558 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2024-11-18 13:37:33,558 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [525444681] [2024-11-18 13:37:33,558 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:37:33,558 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-18 13:37:33,558 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:37:33,559 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-18 13:37:33,559 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=381, Unknown=0, NotChecked=0, Total=462 [2024-11-18 13:37:33,559 INFO L87 Difference]: Start difference. First operand 957 states and 1518 transitions. Second operand has 22 states, 20 states have (on average 2.3) internal successors, (46), 21 states have internal predecessors, (46), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-18 13:37:41,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:37:41,259 INFO L93 Difference]: Finished difference Result 1150 states and 1798 transitions. [2024-11-18 13:37:41,260 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2024-11-18 13:37:41,260 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 2.3) internal successors, (46), 21 states have internal predecessors, (46), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 104 [2024-11-18 13:37:41,260 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:37:41,265 INFO L225 Difference]: With dead ends: 1150 [2024-11-18 13:37:41,265 INFO L226 Difference]: Without dead ends: 1142 [2024-11-18 13:37:41,266 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 253 GetRequests, 184 SyntacticMatches, 2 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1247 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=994, Invalid=3698, Unknown=0, NotChecked=0, Total=4692 [2024-11-18 13:37:41,266 INFO L432 NwaCegarLoop]: 68 mSDtfsCounter, 187 mSDsluCounter, 714 mSDsCounter, 0 mSdLazyCounter, 1034 mSolverCounterSat, 206 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 187 SdHoareTripleChecker+Valid, 782 SdHoareTripleChecker+Invalid, 1240 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 206 IncrementalHoareTripleChecker+Valid, 1034 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.5s IncrementalHoareTripleChecker+Time [2024-11-18 13:37:41,267 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [187 Valid, 782 Invalid, 1240 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [206 Valid, 1034 Invalid, 0 Unknown, 0 Unchecked, 2.5s Time] [2024-11-18 13:37:41,267 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1142 states. [2024-11-18 13:37:41,966 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1142 to 1114. [2024-11-18 13:37:41,967 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1114 states, 564 states have (on average 1.301418439716312) internal successors, (734), 565 states have internal predecessors, (734), 513 states have call successors, (513), 36 states have call predecessors, (513), 36 states have return successors, (512), 512 states have call predecessors, (512), 512 states have call successors, (512) [2024-11-18 13:37:41,971 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1114 states to 1114 states and 1759 transitions. [2024-11-18 13:37:41,972 INFO L78 Accepts]: Start accepts. Automaton has 1114 states and 1759 transitions. Word has length 104 [2024-11-18 13:37:41,972 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:37:41,972 INFO L471 AbstractCegarLoop]: Abstraction has 1114 states and 1759 transitions. [2024-11-18 13:37:41,972 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 2.3) internal successors, (46), 21 states have internal predecessors, (46), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-18 13:37:41,972 INFO L276 IsEmpty]: Start isEmpty. Operand 1114 states and 1759 transitions. [2024-11-18 13:37:41,973 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2024-11-18 13:37:41,973 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:37:41,973 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 6, 4, 4, 4, 4, 4, 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, 1] [2024-11-18 13:37:41,980 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2024-11-18 13:37:42,174 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:37:42,174 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:37:42,174 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:37:42,174 INFO L85 PathProgramCache]: Analyzing trace with hash -389938535, now seen corresponding path program 5 times [2024-11-18 13:37:42,174 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:37:42,174 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2053137935] [2024-11-18 13:37:42,174 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-18 13:37:42,175 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:37:42,211 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2024-11-18 13:37:42,215 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:37:42,216 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1000149335] [2024-11-18 13:37:42,216 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-18 13:37:42,216 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:37:42,216 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:37:42,218 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:37:42,223 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:37:42,329 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2024-11-18 13:37:42,329 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:37:42,331 INFO L255 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 92 conjuncts are in the unsatisfiable core [2024-11-18 13:37:42,333 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:37:43,020 INFO L134 CoverageAnalysis]: Checked inductivity of 244 backedges. 31 proven. 87 refuted. 0 times theorem prover too weak. 126 trivial. 0 not checked. [2024-11-18 13:37:43,021 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:37:48,713 INFO L134 CoverageAnalysis]: Checked inductivity of 244 backedges. 67 proven. 47 refuted. 0 times theorem prover too weak. 130 trivial. 0 not checked. [2024-11-18 13:37:48,714 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:37:48,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2053137935] [2024-11-18 13:37:48,714 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:37:48,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1000149335] [2024-11-18 13:37:48,714 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1000149335] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:37:48,714 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:37:48,714 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 15] total 32 [2024-11-18 13:37:48,714 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1025456945] [2024-11-18 13:37:48,714 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:37:48,714 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2024-11-18 13:37:48,714 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:37:48,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2024-11-18 13:37:48,715 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=162, Invalid=830, Unknown=0, NotChecked=0, Total=992 [2024-11-18 13:37:48,715 INFO L87 Difference]: Start difference. First operand 1114 states and 1759 transitions. Second operand has 32 states, 32 states have (on average 2.4375) internal successors, (78), 28 states have internal predecessors, (78), 9 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) [2024-11-18 13:37:53,777 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:37:53,777 INFO L93 Difference]: Finished difference Result 1342 states and 2087 transitions. [2024-11-18 13:37:53,778 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2024-11-18 13:37:53,778 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 32 states have (on average 2.4375) internal successors, (78), 28 states have internal predecessors, (78), 9 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) Word has length 103 [2024-11-18 13:37:53,778 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:37:53,784 INFO L225 Difference]: With dead ends: 1342 [2024-11-18 13:37:53,784 INFO L226 Difference]: Without dead ends: 1340 [2024-11-18 13:37:53,785 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 256 GetRequests, 195 SyntacticMatches, 0 SemanticMatches, 61 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 759 ImplicationChecksByTransitivity, 7.7s TimeCoverageRelationStatistics Valid=686, Invalid=3220, Unknown=0, NotChecked=0, Total=3906 [2024-11-18 13:37:53,786 INFO L432 NwaCegarLoop]: 50 mSDtfsCounter, 168 mSDsluCounter, 545 mSDsCounter, 0 mSdLazyCounter, 822 mSolverCounterSat, 252 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 168 SdHoareTripleChecker+Valid, 595 SdHoareTripleChecker+Invalid, 1074 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 252 IncrementalHoareTripleChecker+Valid, 822 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2024-11-18 13:37:53,786 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [168 Valid, 595 Invalid, 1074 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [252 Valid, 822 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2024-11-18 13:37:53,787 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1340 states. [2024-11-18 13:37:54,648 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1340 to 1230. [2024-11-18 13:37:54,649 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1230 states, 631 states have (on average 1.2900158478605388) internal successors, (814), 633 states have internal predecessors, (814), 555 states have call successors, (555), 43 states have call predecessors, (555), 43 states have return successors, (554), 553 states have call predecessors, (554), 554 states have call successors, (554) [2024-11-18 13:37:54,653 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1230 states to 1230 states and 1923 transitions. [2024-11-18 13:37:54,655 INFO L78 Accepts]: Start accepts. Automaton has 1230 states and 1923 transitions. Word has length 103 [2024-11-18 13:37:54,655 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:37:54,655 INFO L471 AbstractCegarLoop]: Abstraction has 1230 states and 1923 transitions. [2024-11-18 13:37:54,655 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 32 states have (on average 2.4375) internal successors, (78), 28 states have internal predecessors, (78), 9 states have call successors, (24), 3 states have call predecessors, (24), 2 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) [2024-11-18 13:37:54,655 INFO L276 IsEmpty]: Start isEmpty. Operand 1230 states and 1923 transitions. [2024-11-18 13:37:54,656 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2024-11-18 13:37:54,656 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:37:54,656 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 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, 1, 1, 1, 1] [2024-11-18 13:37:54,663 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2024-11-18 13:37:54,858 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,SelfDestructingSolverStorable21 [2024-11-18 13:37:54,859 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:37:54,859 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:37:54,859 INFO L85 PathProgramCache]: Analyzing trace with hash 2024025072, now seen corresponding path program 3 times [2024-11-18 13:37:54,859 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:37:54,859 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [221701315] [2024-11-18 13:37:54,859 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:37:54,859 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:37:54,883 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2024-11-18 13:37:54,883 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:37:54,884 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [803530124] [2024-11-18 13:37:54,884 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:37:54,884 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:37:54,884 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:37:54,887 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:37:54,888 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:37:54,967 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-18 13:37:54,967 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:37:54,969 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 53 conjuncts are in the unsatisfiable core [2024-11-18 13:37:54,970 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:37:55,566 INFO L134 CoverageAnalysis]: Checked inductivity of 339 backedges. 24 proven. 27 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-18 13:37:55,566 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:37:57,102 INFO L134 CoverageAnalysis]: Checked inductivity of 339 backedges. 24 proven. 27 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-18 13:37:57,103 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:37:57,103 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [221701315] [2024-11-18 13:37:57,103 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:37:57,103 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [803530124] [2024-11-18 13:37:57,103 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [803530124] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:37:57,103 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:37:57,103 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2024-11-18 13:37:57,103 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2016403617] [2024-11-18 13:37:57,103 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:37:57,104 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-18 13:37:57,104 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:37:57,104 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-18 13:37:57,104 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=384, Unknown=0, NotChecked=0, Total=462 [2024-11-18 13:37:57,104 INFO L87 Difference]: Start difference. First operand 1230 states and 1923 transitions. Second operand has 22 states, 20 states have (on average 2.6) internal successors, (52), 21 states have internal predecessors, (52), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-18 13:38:02,039 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:38:02,040 INFO L93 Difference]: Finished difference Result 1524 states and 2372 transitions. [2024-11-18 13:38:02,040 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2024-11-18 13:38:02,040 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 2.6) internal successors, (52), 21 states have internal predecessors, (52), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 107 [2024-11-18 13:38:02,040 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:38:02,046 INFO L225 Difference]: With dead ends: 1524 [2024-11-18 13:38:02,046 INFO L226 Difference]: Without dead ends: 1516 [2024-11-18 13:38:02,047 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 245 GetRequests, 190 SyntacticMatches, 2 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 677 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=579, Invalid=2391, Unknown=0, NotChecked=0, Total=2970 [2024-11-18 13:38:02,048 INFO L432 NwaCegarLoop]: 56 mSDtfsCounter, 206 mSDsluCounter, 685 mSDsCounter, 0 mSdLazyCounter, 907 mSolverCounterSat, 211 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 218 SdHoareTripleChecker+Valid, 741 SdHoareTripleChecker+Invalid, 1118 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 211 IncrementalHoareTripleChecker+Valid, 907 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:38:02,048 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [218 Valid, 741 Invalid, 1118 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [211 Valid, 907 Invalid, 0 Unknown, 0 Unchecked, 2.1s Time] [2024-11-18 13:38:02,049 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1516 states. [2024-11-18 13:38:03,069 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1516 to 1332. [2024-11-18 13:38:03,071 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1332 states, 681 states have (on average 1.28928046989721) internal successors, (878), 683 states have internal predecessors, (878), 603 states have call successors, (603), 47 states have call predecessors, (603), 47 states have return successors, (602), 601 states have call predecessors, (602), 602 states have call successors, (602) [2024-11-18 13:38:03,074 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1332 states to 1332 states and 2083 transitions. [2024-11-18 13:38:03,075 INFO L78 Accepts]: Start accepts. Automaton has 1332 states and 2083 transitions. Word has length 107 [2024-11-18 13:38:03,076 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:38:03,076 INFO L471 AbstractCegarLoop]: Abstraction has 1332 states and 2083 transitions. [2024-11-18 13:38:03,076 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 2.6) internal successors, (52), 21 states have internal predecessors, (52), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-18 13:38:03,076 INFO L276 IsEmpty]: Start isEmpty. Operand 1332 states and 2083 transitions. [2024-11-18 13:38:03,077 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2024-11-18 13:38:03,077 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:38:03,077 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:38:03,083 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:38:03,278 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,SelfDestructingSolverStorable22 [2024-11-18 13:38:03,278 INFO L396 AbstractCegarLoop]: === Iteration 24 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:38:03,278 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:38:03,278 INFO L85 PathProgramCache]: Analyzing trace with hash 1666306094, now seen corresponding path program 4 times [2024-11-18 13:38:03,278 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:38:03,278 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [852142755] [2024-11-18 13:38:03,278 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:38:03,278 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:38:03,292 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:38:03,292 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:38:03,293 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1142973850] [2024-11-18 13:38:03,293 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:38:03,293 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:38:03,293 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:38:03,295 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:38:03,296 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:38:03,354 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:38:03,354 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:38:03,361 INFO L255 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 77 conjuncts are in the unsatisfiable core [2024-11-18 13:38:03,363 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:38:04,452 INFO L134 CoverageAnalysis]: Checked inductivity of 350 backedges. 56 proven. 48 refuted. 0 times theorem prover too weak. 246 trivial. 0 not checked. [2024-11-18 13:38:04,452 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:38:10,949 INFO L134 CoverageAnalysis]: Checked inductivity of 350 backedges. 50 proven. 45 refuted. 0 times theorem prover too weak. 255 trivial. 0 not checked. [2024-11-18 13:38:10,949 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:38:10,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [852142755] [2024-11-18 13:38:10,949 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:38:10,949 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1142973850] [2024-11-18 13:38:10,949 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1142973850] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:38:10,949 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:38:10,949 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 19] total 39 [2024-11-18 13:38:10,949 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [171896589] [2024-11-18 13:38:10,949 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:38:10,950 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 39 states [2024-11-18 13:38:10,950 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:38:10,950 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2024-11-18 13:38:10,951 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=185, Invalid=1297, Unknown=0, NotChecked=0, Total=1482 [2024-11-18 13:38:10,951 INFO L87 Difference]: Start difference. First operand 1332 states and 2083 transitions. Second operand has 39 states, 37 states have (on average 1.945945945945946) internal successors, (72), 37 states have internal predecessors, (72), 12 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 10 states have call predecessors, (30), 10 states have call successors, (30) [2024-11-18 13:38:20,238 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:38:23,235 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.95s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers []