./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench/egcd2-ll.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/egcd2-ll.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 ed6536c9cb0e4b2be9a327fc4a25c6bfba6e98b1dfb78e314dd25bca8cbdb087 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-18 13:26:35,326 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-18 13:26:35,381 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-18 13:26:35,389 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-18 13:26:35,389 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-18 13:26:35,423 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-18 13:26:35,424 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-18 13:26:35,424 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-18 13:26:35,426 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-18 13:26:35,427 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-18 13:26:35,427 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-18 13:26:35,427 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-18 13:26:35,428 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-18 13:26:35,429 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-18 13:26:35,431 INFO L153 SettingsManager]: * Use SBE=true [2024-11-18 13:26:35,431 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-18 13:26:35,432 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-18 13:26:35,432 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-18 13:26:35,432 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-18 13:26:35,432 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-18 13:26:35,433 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-18 13:26:35,434 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-18 13:26:35,434 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-18 13:26:35,435 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-18 13:26:35,435 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-18 13:26:35,435 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-18 13:26:35,436 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-18 13:26:35,436 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-18 13:26:35,436 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-18 13:26:35,437 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-18 13:26:35,437 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-18 13:26:35,437 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-18 13:26:35,438 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:26:35,438 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-18 13:26:35,438 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-18 13:26:35,438 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-18 13:26:35,439 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-18 13:26:35,439 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-18 13:26:35,439 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-18 13:26:35,439 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-18 13:26:35,439 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-18 13:26:35,440 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-18 13:26:35,440 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 -> ed6536c9cb0e4b2be9a327fc4a25c6bfba6e98b1dfb78e314dd25bca8cbdb087 [2024-11-18 13:26:35,749 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-18 13:26:35,779 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-18 13:26:35,782 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-18 13:26:35,783 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-18 13:26:35,784 INFO L274 PluginConnector]: CDTParser initialized [2024-11-18 13:26:35,785 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench/egcd2-ll.c [2024-11-18 13:26:37,258 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-18 13:26:37,429 INFO L384 CDTParser]: Found 1 translation units. [2024-11-18 13:26:37,430 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench/egcd2-ll.c [2024-11-18 13:26:37,437 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/22f1abff2/d9393e4f39d64c0e8e22ed9262df4e63/FLAGff7e267d7 [2024-11-18 13:26:37,450 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/22f1abff2/d9393e4f39d64c0e8e22ed9262df4e63 [2024-11-18 13:26:37,453 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-18 13:26:37,454 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-18 13:26:37,456 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-18 13:26:37,456 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-18 13:26:37,461 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-18 13:26:37,462 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:26:37" (1/1) ... [2024-11-18 13:26:37,463 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7e0d1cf4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:26:37, skipping insertion in model container [2024-11-18 13:26:37,463 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:26:37" (1/1) ... [2024-11-18 13:26:37,489 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-18 13:26:37,658 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/egcd2-ll.c[490,503] [2024-11-18 13:26:37,678 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:26:37,687 INFO L200 MainTranslator]: Completed pre-run [2024-11-18 13:26:37,697 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/egcd2-ll.c[490,503] [2024-11-18 13:26:37,707 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:26:37,726 INFO L204 MainTranslator]: Completed translation [2024-11-18 13:26:37,727 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:26:37 WrapperNode [2024-11-18 13:26:37,727 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-18 13:26:37,728 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-18 13:26:37,728 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-18 13:26:37,728 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-18 13:26:37,736 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:26:37" (1/1) ... [2024-11-18 13:26:37,743 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:26:37" (1/1) ... [2024-11-18 13:26:37,762 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 77 [2024-11-18 13:26:37,764 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-18 13:26:37,765 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-18 13:26:37,765 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-18 13:26:37,765 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-18 13:26:37,775 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:26:37" (1/1) ... [2024-11-18 13:26:37,775 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:26:37" (1/1) ... [2024-11-18 13:26:37,777 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:26:37" (1/1) ... [2024-11-18 13:26:37,788 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:26:37,789 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:26:37" (1/1) ... [2024-11-18 13:26:37,789 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:26:37" (1/1) ... [2024-11-18 13:26:37,792 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:26:37" (1/1) ... [2024-11-18 13:26:37,795 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:26:37" (1/1) ... [2024-11-18 13:26:37,796 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:26:37" (1/1) ... [2024-11-18 13:26:37,797 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:26:37" (1/1) ... [2024-11-18 13:26:37,799 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-18 13:26:37,800 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-18 13:26:37,800 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-18 13:26:37,800 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-18 13:26:37,801 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:26:37" (1/1) ... [2024-11-18 13:26:37,810 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:26:37,820 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:37,835 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:26:37,839 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:26:37,891 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-18 13:26:37,892 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-18 13:26:37,892 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-18 13:26:37,892 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-18 13:26:37,892 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-18 13:26:37,892 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-18 13:26:37,892 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-18 13:26:37,892 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-18 13:26:37,960 INFO L238 CfgBuilder]: Building ICFG [2024-11-18 13:26:37,963 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-18 13:26:38,151 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-11-18 13:26:38,151 INFO L287 CfgBuilder]: Performing block encoding [2024-11-18 13:26:38,175 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-18 13:26:38,176 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-18 13:26:38,176 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:26:38 BoogieIcfgContainer [2024-11-18 13:26:38,176 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-18 13:26:38,179 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-18 13:26:38,179 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-18 13:26:38,183 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-18 13:26:38,183 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.11 01:26:37" (1/3) ... [2024-11-18 13:26:38,184 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6ec15d5f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:26:38, skipping insertion in model container [2024-11-18 13:26:38,184 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:26:37" (2/3) ... [2024-11-18 13:26:38,185 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6ec15d5f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:26:38, skipping insertion in model container [2024-11-18 13:26:38,185 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:26:38" (3/3) ... [2024-11-18 13:26:38,186 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll.c [2024-11-18 13:26:38,205 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-18 13:26:38,206 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-18 13:26:38,272 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-18 13:26:38,281 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;@22f5f084, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-18 13:26:38,282 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-18 13:26:38,287 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 18 states have (on average 1.5) internal successors, (27), 20 states have internal predecessors, (27), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-18 13:26:38,295 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-18 13:26:38,296 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:38,297 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:26:38,297 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:38,302 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:38,304 INFO L85 PathProgramCache]: Analyzing trace with hash 223354930, now seen corresponding path program 1 times [2024-11-18 13:26:38,312 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:38,313 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [776894021] [2024-11-18 13:26:38,313 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:38,314 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:38,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:38,481 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:26:38,482 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:38,482 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [776894021] [2024-11-18 13:26:38,483 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [776894021] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:26:38,483 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1591809104] [2024-11-18 13:26:38,483 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:38,483 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:38,484 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:38,486 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:26:38,487 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:26:38,576 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:38,582 INFO L255 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-18 13:26:38,591 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:26:38,603 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:26:38,603 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:26:38,604 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1591809104] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:26:38,604 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:26:38,604 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-11-18 13:26:38,607 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1679489757] [2024-11-18 13:26:38,608 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:26:38,612 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-18 13:26:38,612 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:38,629 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-18 13:26:38,630 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 13:26:38,632 INFO L87 Difference]: Start difference. First operand has 32 states, 18 states have (on average 1.5) internal successors, (27), 20 states have internal predecessors, (27), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-18 13:26:38,654 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:26:38,655 INFO L93 Difference]: Finished difference Result 61 states and 100 transitions. [2024-11-18 13:26:38,656 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-18 13:26:38,657 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2024-11-18 13:26:38,657 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:26:38,662 INFO L225 Difference]: With dead ends: 61 [2024-11-18 13:26:38,663 INFO L226 Difference]: Without dead ends: 28 [2024-11-18 13:26:38,666 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 13:26:38,669 INFO L432 NwaCegarLoop]: 41 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, 41 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:26:38,672 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:26:38,690 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2024-11-18 13:26:38,707 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2024-11-18 13:26:38,708 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 15 states have (on average 1.2) internal successors, (18), 17 states have internal predecessors, (18), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-18 13:26:38,709 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2024-11-18 13:26:38,710 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 28 [2024-11-18 13:26:38,711 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:26:38,711 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2024-11-18 13:26:38,711 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-18 13:26:38,711 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2024-11-18 13:26:38,713 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-18 13:26:38,713 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:38,713 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:26:38,726 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:26:38,914 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:26:38,914 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:38,915 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:38,915 INFO L85 PathProgramCache]: Analyzing trace with hash 727709964, now seen corresponding path program 1 times [2024-11-18 13:26:38,915 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:38,915 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [337985800] [2024-11-18 13:26:38,916 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:38,916 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:38,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:39,218 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-18 13:26:39,219 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:39,219 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [337985800] [2024-11-18 13:26:39,221 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [337985800] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:26:39,222 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1833545652] [2024-11-18 13:26:39,222 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:39,222 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:39,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:39,224 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:26:39,226 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:26:39,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:39,294 INFO L255 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-18 13:26:39,297 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:26:39,467 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:26:39,468 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:26:39,468 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1833545652] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:26:39,468 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:26:39,468 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2024-11-18 13:26:39,469 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [904349428] [2024-11-18 13:26:39,471 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:26:39,472 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-18 13:26:39,472 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:39,473 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-18 13:26:39,474 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2024-11-18 13:26:39,474 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-18 13:26:39,600 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:26:39,600 INFO L93 Difference]: Finished difference Result 45 states and 60 transitions. [2024-11-18 13:26:39,600 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-18 13:26:39,601 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2024-11-18 13:26:39,601 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:26:39,603 INFO L225 Difference]: With dead ends: 45 [2024-11-18 13:26:39,603 INFO L226 Difference]: Without dead ends: 43 [2024-11-18 13:26:39,604 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2024-11-18 13:26:39,605 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 7 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:26:39,606 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 126 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:26:39,606 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-18 13:26:39,621 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 41. [2024-11-18 13:26:39,621 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 24 states have internal predecessors, (27), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-18 13:26:39,622 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 56 transitions. [2024-11-18 13:26:39,623 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 56 transitions. Word has length 29 [2024-11-18 13:26:39,623 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:26:39,623 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 56 transitions. [2024-11-18 13:26:39,623 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-18 13:26:39,623 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 56 transitions. [2024-11-18 13:26:39,624 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-18 13:26:39,624 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:39,624 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:26:39,640 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-18 13:26:39,825 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,SelfDestructingSolverStorable1 [2024-11-18 13:26:39,826 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:39,827 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:39,827 INFO L85 PathProgramCache]: Analyzing trace with hash 1088429638, now seen corresponding path program 1 times [2024-11-18 13:26:39,827 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:39,828 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2141365353] [2024-11-18 13:26:39,828 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:39,828 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:39,861 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:26:39,867 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [191086004] [2024-11-18 13:26:39,868 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:39,868 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:39,868 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:39,869 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:26:39,871 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:26:39,930 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:39,931 INFO L255 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-18 13:26:39,933 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:26:39,981 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:26:39,982 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:26:39,982 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:39,982 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2141365353] [2024-11-18 13:26:39,983 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:26:39,983 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [191086004] [2024-11-18 13:26:39,983 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [191086004] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:26:39,983 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:26:39,983 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:26:39,984 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1635022407] [2024-11-18 13:26:39,984 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:26:39,984 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:26:39,984 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:39,985 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:26:39,985 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:26:39,985 INFO L87 Difference]: Start difference. First operand 41 states and 56 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-18 13:26:40,038 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:26:40,039 INFO L93 Difference]: Finished difference Result 60 states and 84 transitions. [2024-11-18 13:26:40,039 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:26:40,039 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 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 30 [2024-11-18 13:26:40,039 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:26:40,042 INFO L225 Difference]: With dead ends: 60 [2024-11-18 13:26:40,043 INFO L226 Difference]: Without dead ends: 58 [2024-11-18 13:26:40,044 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 26 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:26:40,045 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 4 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 123 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:26:40,046 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 123 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:26:40,047 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2024-11-18 13:26:40,081 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 49. [2024-11-18 13:26:40,082 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 31 states have internal predecessors, (32), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 13 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-18 13:26:40,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 65 transitions. [2024-11-18 13:26:40,083 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 65 transitions. Word has length 30 [2024-11-18 13:26:40,090 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:26:40,091 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 65 transitions. [2024-11-18 13:26:40,091 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 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:26:40,091 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 65 transitions. [2024-11-18 13:26:40,092 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-11-18 13:26:40,092 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:40,092 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] [2024-11-18 13:26:40,120 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-18 13:26:40,292 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:40,293 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:40,294 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:40,294 INFO L85 PathProgramCache]: Analyzing trace with hash 692401170, now seen corresponding path program 1 times [2024-11-18 13:26:40,294 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:40,294 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1252129707] [2024-11-18 13:26:40,294 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:40,294 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:40,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:40,457 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-18 13:26:40,459 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:40,459 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1252129707] [2024-11-18 13:26:40,459 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1252129707] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:26:40,459 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1478470594] [2024-11-18 13:26:40,460 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:40,460 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:40,460 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:40,462 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:26:40,463 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:26:40,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:40,512 INFO L255 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-18 13:26:40,514 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:26:40,613 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:26:40,615 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:26:40,615 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1478470594] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:26:40,615 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:26:40,615 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2024-11-18 13:26:40,616 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1366069401] [2024-11-18 13:26:40,616 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:26:40,617 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:26:40,617 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:40,618 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:26:40,618 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2024-11-18 13:26:40,619 INFO L87 Difference]: Start difference. First operand 49 states and 65 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (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:26:40,671 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:26:40,671 INFO L93 Difference]: Finished difference Result 57 states and 72 transitions. [2024-11-18 13:26:40,674 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:26:40,675 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (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 34 [2024-11-18 13:26:40,675 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:26:40,676 INFO L225 Difference]: With dead ends: 57 [2024-11-18 13:26:40,676 INFO L226 Difference]: Without dead ends: 53 [2024-11-18 13:26:40,676 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2024-11-18 13:26:40,677 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 7 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:26:40,677 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 126 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:26:40,678 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2024-11-18 13:26:40,691 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 52. [2024-11-18 13:26:40,692 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 33 states have internal predecessors, (34), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-18 13:26:40,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 65 transitions. [2024-11-18 13:26:40,693 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 65 transitions. Word has length 34 [2024-11-18 13:26:40,693 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:26:40,693 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 65 transitions. [2024-11-18 13:26:40,693 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (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:26:40,693 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 65 transitions. [2024-11-18 13:26:40,695 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-11-18 13:26:40,696 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:40,696 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] [2024-11-18 13:26:40,712 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-18 13:26:40,900 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:40,901 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:40,901 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:40,901 INFO L85 PathProgramCache]: Analyzing trace with hash -98301800, now seen corresponding path program 1 times [2024-11-18 13:26:40,901 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:40,901 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1276705516] [2024-11-18 13:26:40,902 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:40,902 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:40,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:26:40,918 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2067934077] [2024-11-18 13:26:40,918 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:40,919 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:40,919 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:40,920 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:26:40,922 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:26:40,988 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:40,990 INFO L255 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-18 13:26:40,992 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:26:41,173 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:26:41,173 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:26:41,173 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:41,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1276705516] [2024-11-18 13:26:41,173 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:26:41,173 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2067934077] [2024-11-18 13:26:41,173 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2067934077] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:26:41,173 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:26:41,174 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:26:41,174 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [325949591] [2024-11-18 13:26:41,174 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:26:41,174 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:26:41,174 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:41,175 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:26:41,175 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:26:41,176 INFO L87 Difference]: Start difference. First operand 52 states and 65 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, (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:26:41,249 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:26:41,249 INFO L93 Difference]: Finished difference Result 59 states and 71 transitions. [2024-11-18 13:26:41,249 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:26:41,250 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, (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 45 [2024-11-18 13:26:41,251 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:26:41,252 INFO L225 Difference]: With dead ends: 59 [2024-11-18 13:26:41,252 INFO L226 Difference]: Without dead ends: 57 [2024-11-18 13:26:41,252 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 41 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:26:41,253 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 5 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:26:41,254 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 114 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:26:41,257 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2024-11-18 13:26:41,266 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 56. [2024-11-18 13:26:41,266 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 33 states have (on average 1.121212121212121) internal successors, (37), 36 states have internal predecessors, (37), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-18 13:26:41,267 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 68 transitions. [2024-11-18 13:26:41,268 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 68 transitions. Word has length 45 [2024-11-18 13:26:41,268 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:26:41,268 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 68 transitions. [2024-11-18 13:26:41,268 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, (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:26:41,271 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 68 transitions. [2024-11-18 13:26:41,272 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-11-18 13:26:41,272 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:41,272 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] [2024-11-18 13:26:41,291 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:26:41,473 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:41,473 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:41,474 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:41,474 INFO L85 PathProgramCache]: Analyzing trace with hash -137832731, now seen corresponding path program 1 times [2024-11-18 13:26:41,474 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:41,474 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1102552093] [2024-11-18 13:26:41,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:41,474 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:41,494 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:26:41,495 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [202322931] [2024-11-18 13:26:41,495 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:41,495 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:41,496 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:41,497 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:26:41,499 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:26:41,550 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:41,551 INFO L255 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-18 13:26:41,553 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:26:41,655 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-18 13:26:41,655 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:26:41,784 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-18 13:26:41,785 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:41,785 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1102552093] [2024-11-18 13:26:41,786 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:26:41,786 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [202322931] [2024-11-18 13:26:41,786 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [202322931] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:26:41,786 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:26:41,786 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2024-11-18 13:26:41,786 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [299863028] [2024-11-18 13:26:41,786 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:26:41,787 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-18 13:26:41,787 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:41,787 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-18 13:26:41,789 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-18 13:26:41,789 INFO L87 Difference]: Start difference. First operand 56 states and 68 transitions. Second operand has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-18 13:26:41,907 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:26:41,908 INFO L93 Difference]: Finished difference Result 84 states and 113 transitions. [2024-11-18 13:26:41,909 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-18 13:26:41,909 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 52 [2024-11-18 13:26:41,909 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:26:41,911 INFO L225 Difference]: With dead ends: 84 [2024-11-18 13:26:41,911 INFO L226 Difference]: Without dead ends: 82 [2024-11-18 13:26:41,911 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 94 SyntacticMatches, 3 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-18 13:26:41,912 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 6 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 191 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:26:41,912 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 191 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:26:41,915 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2024-11-18 13:26:41,933 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 52. [2024-11-18 13:26:41,934 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 32 states have internal predecessors, (35), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-18 13:26:41,935 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 62 transitions. [2024-11-18 13:26:41,935 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 62 transitions. Word has length 52 [2024-11-18 13:26:41,936 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:26:41,936 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 62 transitions. [2024-11-18 13:26:41,937 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 4 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-18 13:26:41,937 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 62 transitions. [2024-11-18 13:26:41,938 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2024-11-18 13:26:41,938 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:41,938 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:26:41,955 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-18 13:26:42,138 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:42,139 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:42,140 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:42,140 INFO L85 PathProgramCache]: Analyzing trace with hash -1721617041, now seen corresponding path program 1 times [2024-11-18 13:26:42,140 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:42,140 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1747483776] [2024-11-18 13:26:42,140 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:42,141 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:42,163 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:42,312 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-18 13:26:42,312 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:42,312 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1747483776] [2024-11-18 13:26:42,312 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1747483776] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:26:42,313 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [393782643] [2024-11-18 13:26:42,313 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:42,313 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:42,313 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:42,314 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:26:42,316 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:26:42,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:42,385 INFO L255 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-18 13:26:42,387 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:26:42,432 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-18 13:26:42,432 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:26:42,536 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-18 13:26:42,538 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [393782643] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:26:42,538 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:26:42,538 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2024-11-18 13:26:42,538 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [900468989] [2024-11-18 13:26:42,538 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:26:42,539 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-18 13:26:42,539 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:42,539 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-18 13:26:42,540 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-18 13:26:42,543 INFO L87 Difference]: Start difference. First operand 52 states and 62 transitions. Second operand has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-18 13:26:42,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:26:42,724 INFO L93 Difference]: Finished difference Result 99 states and 137 transitions. [2024-11-18 13:26:42,725 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-18 13:26:42,725 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 54 [2024-11-18 13:26:42,725 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:26:42,726 INFO L225 Difference]: With dead ends: 99 [2024-11-18 13:26:42,726 INFO L226 Difference]: Without dead ends: 91 [2024-11-18 13:26:42,727 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 103 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2024-11-18 13:26:42,728 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 32 mSDsluCounter, 236 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 277 SdHoareTripleChecker+Invalid, 128 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:26:42,728 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 277 Invalid, 128 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:26:42,728 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2024-11-18 13:26:42,747 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 82. [2024-11-18 13:26:42,748 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 45 states have (on average 1.2) internal successors, (54), 46 states have internal predecessors, (54), 30 states have call successors, (30), 6 states have call predecessors, (30), 6 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2024-11-18 13:26:42,748 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 113 transitions. [2024-11-18 13:26:42,749 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 113 transitions. Word has length 54 [2024-11-18 13:26:42,749 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:26:42,749 INFO L471 AbstractCegarLoop]: Abstraction has 82 states and 113 transitions. [2024-11-18 13:26:42,749 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-18 13:26:42,750 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 113 transitions. [2024-11-18 13:26:42,750 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-11-18 13:26:42,750 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:42,751 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 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:26:42,767 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:26:42,954 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:42,955 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:42,955 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:42,955 INFO L85 PathProgramCache]: Analyzing trace with hash -653850053, now seen corresponding path program 1 times [2024-11-18 13:26:42,955 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:42,955 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [73064264] [2024-11-18 13:26:42,956 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:42,956 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:42,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:26:42,975 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [866356541] [2024-11-18 13:26:42,975 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:42,976 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:42,976 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:42,978 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:26:42,995 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:26:43,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:43,057 INFO L255 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-18 13:26:43,059 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:26:43,294 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-11-18 13:26:43,294 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:26:43,554 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-11-18 13:26:43,554 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:43,554 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [73064264] [2024-11-18 13:26:43,554 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:26:43,554 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [866356541] [2024-11-18 13:26:43,554 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [866356541] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:26:43,555 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:26:43,555 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 14 [2024-11-18 13:26:43,555 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1419847916] [2024-11-18 13:26:43,555 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:26:43,555 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-18 13:26:43,555 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:43,556 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-18 13:26:43,556 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2024-11-18 13:26:43,556 INFO L87 Difference]: Start difference. First operand 82 states and 113 transitions. Second operand has 14 states, 14 states have (on average 2.5714285714285716) internal successors, (36), 13 states have internal predecessors, (36), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2024-11-18 13:26:43,797 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:26:43,797 INFO L93 Difference]: Finished difference Result 125 states and 178 transitions. [2024-11-18 13:26:43,798 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-18 13:26:43,798 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.5714285714285716) internal successors, (36), 13 states have internal predecessors, (36), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) Word has length 60 [2024-11-18 13:26:43,799 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:26:43,801 INFO L225 Difference]: With dead ends: 125 [2024-11-18 13:26:43,801 INFO L226 Difference]: Without dead ends: 121 [2024-11-18 13:26:43,802 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 106 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=59, Invalid=213, Unknown=0, NotChecked=0, Total=272 [2024-11-18 13:26:43,802 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 20 mSDsluCounter, 212 mSDsCounter, 0 mSdLazyCounter, 164 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 187 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 164 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:26:43,803 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 249 Invalid, 187 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 164 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:26:43,804 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2024-11-18 13:26:43,846 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 89. [2024-11-18 13:26:43,848 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 49 states have (on average 1.183673469387755) internal successors, (58), 51 states have internal predecessors, (58), 32 states have call successors, (32), 7 states have call predecessors, (32), 7 states have return successors, (31), 30 states have call predecessors, (31), 31 states have call successors, (31) [2024-11-18 13:26:43,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 121 transitions. [2024-11-18 13:26:43,852 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 121 transitions. Word has length 60 [2024-11-18 13:26:43,852 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:26:43,852 INFO L471 AbstractCegarLoop]: Abstraction has 89 states and 121 transitions. [2024-11-18 13:26:43,853 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.5714285714285716) internal successors, (36), 13 states have internal predecessors, (36), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2024-11-18 13:26:43,853 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 121 transitions. [2024-11-18 13:26:43,854 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2024-11-18 13:26:43,854 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:43,854 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 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] [2024-11-18 13:26:43,873 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:26:44,054 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,SelfDestructingSolverStorable7 [2024-11-18 13:26:44,055 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:44,055 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:44,055 INFO L85 PathProgramCache]: Analyzing trace with hash 1044201731, now seen corresponding path program 2 times [2024-11-18 13:26:44,055 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:44,055 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [44363398] [2024-11-18 13:26:44,056 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:26:44,056 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:44,075 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:26:44,075 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:26:44,076 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [720030740] [2024-11-18 13:26:44,076 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:26:44,077 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:44,077 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:44,078 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:26:44,082 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:26:44,140 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:26:44,140 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:26:44,152 INFO L255 TraceCheckSpWp]: Trace formula consists of 171 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-18 13:26:44,154 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:26:44,333 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-18 13:26:44,334 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:26:44,421 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:44,421 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [44363398] [2024-11-18 13:26:44,421 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:26:44,421 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [720030740] [2024-11-18 13:26:44,421 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [720030740] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:26:44,421 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:26:44,421 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2024-11-18 13:26:44,421 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [875652214] [2024-11-18 13:26:44,421 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:26:44,422 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-18 13:26:44,422 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:44,422 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-18 13:26:44,422 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-18 13:26:44,422 INFO L87 Difference]: Start difference. First operand 89 states and 121 transitions. Second operand has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2024-11-18 13:26:44,585 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:26:44,585 INFO L93 Difference]: Finished difference Result 121 states and 160 transitions. [2024-11-18 13:26:44,585 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-18 13:26:44,585 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 65 [2024-11-18 13:26:44,587 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:26:44,588 INFO L225 Difference]: With dead ends: 121 [2024-11-18 13:26:44,588 INFO L226 Difference]: Without dead ends: 119 [2024-11-18 13:26:44,588 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 75 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2024-11-18 13:26:44,589 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 12 mSDsluCounter, 139 mSDsCounter, 0 mSdLazyCounter, 95 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 175 SdHoareTripleChecker+Invalid, 102 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 95 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:26:44,589 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 175 Invalid, 102 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 95 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:26:44,590 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2024-11-18 13:26:44,620 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 116. [2024-11-18 13:26:44,621 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 65 states have (on average 1.1692307692307693) internal successors, (76), 67 states have internal predecessors, (76), 40 states have call successors, (40), 10 states have call predecessors, (40), 10 states have return successors, (39), 38 states have call predecessors, (39), 39 states have call successors, (39) [2024-11-18 13:26:44,623 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 155 transitions. [2024-11-18 13:26:44,624 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 155 transitions. Word has length 65 [2024-11-18 13:26:44,624 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:26:44,624 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 155 transitions. [2024-11-18 13:26:44,624 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2024-11-18 13:26:44,624 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 155 transitions. [2024-11-18 13:26:44,625 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-11-18 13:26:44,625 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:44,625 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:26:44,643 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-18 13:26:44,826 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:44,826 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:44,827 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:44,827 INFO L85 PathProgramCache]: Analyzing trace with hash 635379451, now seen corresponding path program 3 times [2024-11-18 13:26:44,827 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:44,827 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [568588571] [2024-11-18 13:26:44,827 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:26:44,827 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:44,862 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-18 13:26:44,862 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:26:44,864 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1933608777] [2024-11-18 13:26:44,864 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:26:44,864 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:44,865 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:44,866 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:26:44,868 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:26:44,928 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-18 13:26:44,928 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:26:44,930 INFO L255 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 42 conjuncts are in the unsatisfiable core [2024-11-18 13:26:44,932 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:26:45,329 INFO L134 CoverageAnalysis]: Checked inductivity of 129 backedges. 40 proven. 8 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2024-11-18 13:26:45,329 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:26:46,005 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:46,005 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [568588571] [2024-11-18 13:26:46,005 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:26:46,006 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1933608777] [2024-11-18 13:26:46,006 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1933608777] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:26:46,006 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:26:46,006 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2024-11-18 13:26:46,006 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [205615772] [2024-11-18 13:26:46,006 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:26:46,006 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-18 13:26:46,006 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:46,007 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-18 13:26:46,007 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=231, Unknown=0, NotChecked=0, Total=272 [2024-11-18 13:26:46,010 INFO L87 Difference]: Start difference. First operand 116 states and 155 transitions. Second operand has 12 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-18 13:26:46,461 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:26:46,461 INFO L93 Difference]: Finished difference Result 125 states and 163 transitions. [2024-11-18 13:26:46,462 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-18 13:26:46,462 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 70 [2024-11-18 13:26:46,462 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:26:46,463 INFO L225 Difference]: With dead ends: 125 [2024-11-18 13:26:46,463 INFO L226 Difference]: Without dead ends: 123 [2024-11-18 13:26:46,464 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 79 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2024-11-18 13:26:46,464 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 13 mSDsluCounter, 181 mSDsCounter, 0 mSdLazyCounter, 245 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 206 SdHoareTripleChecker+Invalid, 257 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 245 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-18 13:26:46,464 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 206 Invalid, 257 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 245 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-18 13:26:46,465 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2024-11-18 13:26:46,488 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 120. [2024-11-18 13:26:46,489 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 68 states have (on average 1.161764705882353) internal successors, (79), 70 states have internal predecessors, (79), 40 states have call successors, (40), 11 states have call predecessors, (40), 11 states have return successors, (39), 38 states have call predecessors, (39), 39 states have call successors, (39) [2024-11-18 13:26:46,490 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 158 transitions. [2024-11-18 13:26:46,490 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 158 transitions. Word has length 70 [2024-11-18 13:26:46,490 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:26:46,490 INFO L471 AbstractCegarLoop]: Abstraction has 120 states and 158 transitions. [2024-11-18 13:26:46,491 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 11 states have internal predecessors, (26), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-18 13:26:46,491 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 158 transitions. [2024-11-18 13:26:46,492 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-18 13:26:46,492 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:46,492 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:26:46,507 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-18 13:26:46,692 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,SelfDestructingSolverStorable9 [2024-11-18 13:26:46,693 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:46,693 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:46,693 INFO L85 PathProgramCache]: Analyzing trace with hash -375209714, now seen corresponding path program 1 times [2024-11-18 13:26:46,693 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:46,694 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [383816309] [2024-11-18 13:26:46,694 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:46,694 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:46,708 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:26:46,709 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [787254266] [2024-11-18 13:26:46,709 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:46,709 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:46,709 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:46,711 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:26:46,713 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:26:46,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:46,781 INFO L255 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-18 13:26:46,783 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:26:47,286 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 16 proven. 17 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2024-11-18 13:26:47,286 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:26:48,064 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2024-11-18 13:26:48,065 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:48,065 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [383816309] [2024-11-18 13:26:48,065 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:26:48,065 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [787254266] [2024-11-18 13:26:48,065 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [787254266] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:26:48,065 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:26:48,065 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-11-18 13:26:48,066 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1196567371] [2024-11-18 13:26:48,066 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:26:48,066 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-18 13:26:48,066 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:48,067 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-18 13:26:48,067 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2024-11-18 13:26:48,067 INFO L87 Difference]: Start difference. First operand 120 states and 158 transitions. Second operand has 21 states, 19 states have (on average 1.894736842105263) internal successors, (36), 18 states have internal predecessors, (36), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-18 13:26:50,963 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:26:50,963 INFO L93 Difference]: Finished difference Result 205 states and 290 transitions. [2024-11-18 13:26:50,963 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-18 13:26:50,964 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 1.894736842105263) internal successors, (36), 18 states have internal predecessors, (36), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 76 [2024-11-18 13:26:50,964 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:26:50,966 INFO L225 Difference]: With dead ends: 205 [2024-11-18 13:26:50,966 INFO L226 Difference]: Without dead ends: 201 [2024-11-18 13:26:50,967 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 167 GetRequests, 131 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=255, Invalid=1151, Unknown=0, NotChecked=0, Total=1406 [2024-11-18 13:26:50,968 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 75 mSDsluCounter, 320 mSDsCounter, 0 mSdLazyCounter, 458 mSolverCounterSat, 106 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 362 SdHoareTripleChecker+Invalid, 564 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 106 IncrementalHoareTripleChecker+Valid, 458 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2024-11-18 13:26:50,968 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 362 Invalid, 564 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [106 Valid, 458 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2024-11-18 13:26:50,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 201 states. [2024-11-18 13:26:51,043 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 201 to 197. [2024-11-18 13:26:51,044 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 197 states, 105 states have (on average 1.2) internal successors, (126), 106 states have internal predecessors, (126), 77 states have call successors, (77), 14 states have call predecessors, (77), 14 states have return successors, (76), 76 states have call predecessors, (76), 76 states have call successors, (76) [2024-11-18 13:26:51,046 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 197 states to 197 states and 279 transitions. [2024-11-18 13:26:51,046 INFO L78 Accepts]: Start accepts. Automaton has 197 states and 279 transitions. Word has length 76 [2024-11-18 13:26:51,046 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:26:51,047 INFO L471 AbstractCegarLoop]: Abstraction has 197 states and 279 transitions. [2024-11-18 13:26:51,047 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 1.894736842105263) internal successors, (36), 18 states have internal predecessors, (36), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-18 13:26:51,047 INFO L276 IsEmpty]: Start isEmpty. Operand 197 states and 279 transitions. [2024-11-18 13:26:51,048 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-11-18 13:26:51,048 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:51,048 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:26:51,067 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-11-18 13:26:51,252 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,SelfDestructingSolverStorable10 [2024-11-18 13:26:51,253 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:51,253 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:51,253 INFO L85 PathProgramCache]: Analyzing trace with hash 1119373286, now seen corresponding path program 4 times [2024-11-18 13:26:51,253 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:51,253 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [731410703] [2024-11-18 13:26:51,253 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:26:51,254 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:51,267 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:26:51,267 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:26:51,363 INFO L134 CoverageAnalysis]: Checked inductivity of 245 backedges. 41 proven. 0 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2024-11-18 13:26:51,364 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:51,364 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [731410703] [2024-11-18 13:26:51,364 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [731410703] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:26:51,364 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:26:51,364 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:26:51,364 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1891844755] [2024-11-18 13:26:51,364 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:26:51,365 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:26:51,365 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:51,365 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:26:51,365 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:26:51,365 INFO L87 Difference]: Start difference. First operand 197 states and 279 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, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) [2024-11-18 13:26:51,476 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:26:51,476 INFO L93 Difference]: Finished difference Result 250 states and 351 transitions. [2024-11-18 13:26:51,476 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-18 13:26:51,476 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, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) Word has length 90 [2024-11-18 13:26:51,477 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:26:51,478 INFO L225 Difference]: With dead ends: 250 [2024-11-18 13:26:51,478 INFO L226 Difference]: Without dead ends: 178 [2024-11-18 13:26:51,479 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2024-11-18 13:26:51,479 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 6 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 143 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:26:51,480 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 143 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:26:51,480 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2024-11-18 13:26:51,533 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 164. [2024-11-18 13:26:51,533 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 164 states, 88 states have (on average 1.1477272727272727) internal successors, (101), 89 states have internal predecessors, (101), 61 states have call successors, (61), 14 states have call predecessors, (61), 14 states have return successors, (60), 60 states have call predecessors, (60), 60 states have call successors, (60) [2024-11-18 13:26:51,534 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 164 states to 164 states and 222 transitions. [2024-11-18 13:26:51,535 INFO L78 Accepts]: Start accepts. Automaton has 164 states and 222 transitions. Word has length 90 [2024-11-18 13:26:51,535 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:26:51,535 INFO L471 AbstractCegarLoop]: Abstraction has 164 states and 222 transitions. [2024-11-18 13:26:51,535 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, (15), 2 states have call predecessors, (15), 1 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) [2024-11-18 13:26:51,535 INFO L276 IsEmpty]: Start isEmpty. Operand 164 states and 222 transitions. [2024-11-18 13:26:51,536 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2024-11-18 13:26:51,536 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:51,537 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 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] [2024-11-18 13:26:51,537 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11 [2024-11-18 13:26:51,537 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:51,537 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:51,537 INFO L85 PathProgramCache]: Analyzing trace with hash 1261079706, now seen corresponding path program 1 times [2024-11-18 13:26:51,538 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:51,538 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1400767151] [2024-11-18 13:26:51,538 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:51,538 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:51,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:26:51,561 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [452367018] [2024-11-18 13:26:51,561 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:26:51,561 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:51,561 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:51,563 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:26:51,564 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:26:51,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:26:51,643 INFO L255 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-11-18 13:26:51,646 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:26:52,605 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 68 proven. 35 refuted. 0 times theorem prover too weak. 181 trivial. 0 not checked. [2024-11-18 13:26:52,605 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:26:52,737 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:52,738 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1400767151] [2024-11-18 13:26:52,738 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:26:52,738 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [452367018] [2024-11-18 13:26:52,738 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [452367018] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:26:52,738 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:26:52,738 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2024-11-18 13:26:52,738 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [952527970] [2024-11-18 13:26:52,739 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:26:52,739 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-18 13:26:52,740 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:52,741 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-18 13:26:52,741 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=324, Unknown=0, NotChecked=0, Total=380 [2024-11-18 13:26:52,741 INFO L87 Difference]: Start difference. First operand 164 states and 222 transitions. Second operand has 17 states, 16 states have (on average 1.75) internal successors, (28), 13 states have internal predecessors, (28), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) [2024-11-18 13:26:53,450 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:26:53,451 INFO L93 Difference]: Finished difference Result 174 states and 231 transitions. [2024-11-18 13:26:53,451 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-18 13:26:53,452 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 1.75) internal successors, (28), 13 states have internal predecessors, (28), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) Word has length 92 [2024-11-18 13:26:53,452 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:26:53,454 INFO L225 Difference]: With dead ends: 174 [2024-11-18 13:26:53,454 INFO L226 Difference]: Without dead ends: 172 [2024-11-18 13:26:53,455 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 81 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=93, Invalid=507, Unknown=0, NotChecked=0, Total=600 [2024-11-18 13:26:53,456 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 27 mSDsluCounter, 397 mSDsCounter, 0 mSdLazyCounter, 533 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 432 SdHoareTripleChecker+Invalid, 546 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 533 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-18 13:26:53,457 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 432 Invalid, 546 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 533 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-18 13:26:53,458 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2024-11-18 13:26:53,518 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 135. [2024-11-18 13:26:53,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 135 states, 73 states have (on average 1.1506849315068493) internal successors, (84), 74 states have internal predecessors, (84), 49 states have call successors, (49), 12 states have call predecessors, (49), 12 states have return successors, (48), 48 states have call predecessors, (48), 48 states have call successors, (48) [2024-11-18 13:26:53,520 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 135 states to 135 states and 181 transitions. [2024-11-18 13:26:53,520 INFO L78 Accepts]: Start accepts. Automaton has 135 states and 181 transitions. Word has length 92 [2024-11-18 13:26:53,520 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:26:53,520 INFO L471 AbstractCegarLoop]: Abstraction has 135 states and 181 transitions. [2024-11-18 13:26:53,520 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 1.75) internal successors, (28), 13 states have internal predecessors, (28), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) [2024-11-18 13:26:53,521 INFO L276 IsEmpty]: Start isEmpty. Operand 135 states and 181 transitions. [2024-11-18 13:26:53,523 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2024-11-18 13:26:53,523 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:26:53,523 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:26:53,541 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:26:53,727 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:26:53,728 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:26:53,728 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:26:53,728 INFO L85 PathProgramCache]: Analyzing trace with hash 1880436805, now seen corresponding path program 2 times [2024-11-18 13:26:53,728 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:26:53,728 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1303385707] [2024-11-18 13:26:53,728 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:26:53,728 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:26:53,757 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:26:53,757 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:26:53,758 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [975944595] [2024-11-18 13:26:53,758 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:26:53,758 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:26:53,759 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:26:53,760 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:26:53,762 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:26:53,828 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:26:53,829 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:26:53,835 INFO L255 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-11-18 13:26:53,838 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:26:54,374 INFO L134 CoverageAnalysis]: Checked inductivity of 448 backedges. 31 proven. 38 refuted. 0 times theorem prover too weak. 379 trivial. 0 not checked. [2024-11-18 13:26:54,374 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:26:55,467 INFO L134 CoverageAnalysis]: Checked inductivity of 448 backedges. 28 proven. 32 refuted. 0 times theorem prover too weak. 388 trivial. 0 not checked. [2024-11-18 13:26:55,467 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:26:55,467 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1303385707] [2024-11-18 13:26:55,467 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:26:55,468 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [975944595] [2024-11-18 13:26:55,468 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [975944595] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:26:55,468 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:26:55,468 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-11-18 13:26:55,468 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1602833713] [2024-11-18 13:26:55,468 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:26:55,469 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-18 13:26:55,469 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:26:55,469 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-18 13:26:55,469 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=352, Unknown=0, NotChecked=0, Total=420 [2024-11-18 13:26:55,470 INFO L87 Difference]: Start difference. First operand 135 states and 181 transitions. Second operand has 21 states, 21 states have (on average 2.0) internal successors, (42), 18 states have internal predecessors, (42), 11 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (35), 12 states have call predecessors, (35), 11 states have call successors, (35) [2024-11-18 13:26:58,634 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.24s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-18 13:27:00,475 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:27:00,476 INFO L93 Difference]: Finished difference Result 219 states and 306 transitions. [2024-11-18 13:27:00,476 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-18 13:27:00,476 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.0) internal successors, (42), 18 states have internal predecessors, (42), 11 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (35), 12 states have call predecessors, (35), 11 states have call successors, (35) Word has length 109 [2024-11-18 13:27:00,477 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:27:00,478 INFO L225 Difference]: With dead ends: 219 [2024-11-18 13:27:00,478 INFO L226 Difference]: Without dead ends: 217 [2024-11-18 13:27:00,479 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 235 GetRequests, 197 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 222 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=305, Invalid=1255, Unknown=0, NotChecked=0, Total=1560 [2024-11-18 13:27:00,480 INFO L432 NwaCegarLoop]: 56 mSDtfsCounter, 76 mSDsluCounter, 517 mSDsCounter, 0 mSdLazyCounter, 614 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 80 SdHoareTripleChecker+Valid, 573 SdHoareTripleChecker+Invalid, 705 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 614 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:27:00,480 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [80 Valid, 573 Invalid, 705 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 614 Invalid, 0 Unknown, 0 Unchecked, 3.1s Time] [2024-11-18 13:27:00,480 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 217 states. [2024-11-18 13:27:00,573 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 217 to 183. [2024-11-18 13:27:00,574 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 183 states, 98 states have (on average 1.163265306122449) internal successors, (114), 99 states have internal predecessors, (114), 69 states have call successors, (69), 15 states have call predecessors, (69), 15 states have return successors, (68), 68 states have call predecessors, (68), 68 states have call successors, (68) [2024-11-18 13:27:00,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 183 states to 183 states and 251 transitions. [2024-11-18 13:27:00,575 INFO L78 Accepts]: Start accepts. Automaton has 183 states and 251 transitions. Word has length 109 [2024-11-18 13:27:00,575 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:27:00,575 INFO L471 AbstractCegarLoop]: Abstraction has 183 states and 251 transitions. [2024-11-18 13:27:00,576 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.0) internal successors, (42), 18 states have internal predecessors, (42), 11 states have call successors, (36), 3 states have call predecessors, (36), 2 states have return successors, (35), 12 states have call predecessors, (35), 11 states have call successors, (35) [2024-11-18 13:27:00,576 INFO L276 IsEmpty]: Start isEmpty. Operand 183 states and 251 transitions. [2024-11-18 13:27:00,577 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2024-11-18 13:27:00,577 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:27:00,577 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:27:00,591 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:27:00,781 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,SelfDestructingSolverStorable13 [2024-11-18 13:27:00,781 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:27:00,782 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:27:00,782 INFO L85 PathProgramCache]: Analyzing trace with hash 468383399, now seen corresponding path program 3 times [2024-11-18 13:27:00,782 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:27:00,782 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [759532151] [2024-11-18 13:27:00,782 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:27:00,782 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:27:00,830 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-18 13:27:00,830 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:27:00,831 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1916053485] [2024-11-18 13:27:00,831 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:27:00,831 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:27:00,832 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:27:00,833 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:27:00,835 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:27:00,907 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-18 13:27:00,907 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:27:00,913 INFO L255 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 66 conjuncts are in the unsatisfiable core [2024-11-18 13:27:00,916 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:27:02,735 INFO L134 CoverageAnalysis]: Checked inductivity of 453 backedges. 69 proven. 44 refuted. 0 times theorem prover too weak. 340 trivial. 0 not checked. [2024-11-18 13:27:02,735 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:27:17,470 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:27:17,470 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [759532151] [2024-11-18 13:27:17,471 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:27:17,471 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1916053485] [2024-11-18 13:27:17,471 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1916053485] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:27:17,471 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:27:17,471 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2024-11-18 13:27:17,471 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [500356304] [2024-11-18 13:27:17,471 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:27:17,471 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-18 13:27:17,471 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:27:17,472 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-18 13:27:17,472 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=709, Unknown=3, NotChecked=0, Total=812 [2024-11-18 13:27:17,473 INFO L87 Difference]: Start difference. First operand 183 states and 251 transitions. Second operand has 19 states, 18 states have (on average 1.8333333333333333) internal successors, (33), 17 states have internal predecessors, (33), 6 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 8 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-18 13:27:18,976 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:27:18,978 INFO L93 Difference]: Finished difference Result 254 states and 351 transitions. [2024-11-18 13:27:18,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-18 13:27:18,978 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 1.8333333333333333) internal successors, (33), 17 states have internal predecessors, (33), 6 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 8 states have call predecessors, (18), 6 states have call successors, (18) Word has length 112 [2024-11-18 13:27:18,979 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:27:18,980 INFO L225 Difference]: With dead ends: 254 [2024-11-18 13:27:18,980 INFO L226 Difference]: Without dead ends: 252 [2024-11-18 13:27:18,981 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 185 GetRequests, 151 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 249 ImplicationChecksByTransitivity, 14.9s TimeCoverageRelationStatistics Valid=175, Invalid=1082, Unknown=3, NotChecked=0, Total=1260 [2024-11-18 13:27:18,981 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 45 mSDsluCounter, 415 mSDsCounter, 0 mSdLazyCounter, 590 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 452 SdHoareTripleChecker+Invalid, 636 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 590 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:27:18,982 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 452 Invalid, 636 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 590 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2024-11-18 13:27:18,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 252 states. [2024-11-18 13:27:19,121 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 252 to 247. [2024-11-18 13:27:19,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 247 states, 130 states have (on average 1.1615384615384616) internal successors, (151), 131 states have internal predecessors, (151), 97 states have call successors, (97), 19 states have call predecessors, (97), 19 states have return successors, (96), 96 states have call predecessors, (96), 96 states have call successors, (96) [2024-11-18 13:27:19,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 247 states to 247 states and 344 transitions. [2024-11-18 13:27:19,124 INFO L78 Accepts]: Start accepts. Automaton has 247 states and 344 transitions. Word has length 112 [2024-11-18 13:27:19,124 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:27:19,124 INFO L471 AbstractCegarLoop]: Abstraction has 247 states and 344 transitions. [2024-11-18 13:27:19,124 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 1.8333333333333333) internal successors, (33), 17 states have internal predecessors, (33), 6 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 8 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-18 13:27:19,124 INFO L276 IsEmpty]: Start isEmpty. Operand 247 states and 344 transitions. [2024-11-18 13:27:19,127 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2024-11-18 13:27:19,127 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:27:19,127 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:27:19,145 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-11-18 13:27:19,331 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:27:19,332 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:27:19,332 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:27:19,332 INFO L85 PathProgramCache]: Analyzing trace with hash -918263559, now seen corresponding path program 4 times [2024-11-18 13:27:19,332 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:27:19,332 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [172204980] [2024-11-18 13:27:19,332 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:27:19,332 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:27:19,365 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:27:19,365 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:27:19,366 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1309970311] [2024-11-18 13:27:19,366 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:27:19,366 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:27:19,366 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:27:19,369 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:27:19,371 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:27:19,448 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:27:19,448 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:27:19,450 INFO L255 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 40 conjuncts are in the unsatisfiable core [2024-11-18 13:27:19,455 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:27:20,594 INFO L134 CoverageAnalysis]: Checked inductivity of 509 backedges. 100 proven. 43 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2024-11-18 13:27:20,595 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:27:20,908 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:27:20,908 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [172204980] [2024-11-18 13:27:20,909 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:27:20,909 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1309970311] [2024-11-18 13:27:20,909 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1309970311] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:27:20,909 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:27:20,909 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-11-18 13:27:20,909 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2105531066] [2024-11-18 13:27:20,909 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:27:20,909 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-18 13:27:20,909 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:27:20,910 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-18 13:27:20,910 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=222, Unknown=0, NotChecked=0, Total=272 [2024-11-18 13:27:20,910 INFO L87 Difference]: Start difference. First operand 247 states and 344 transitions. Second operand has 15 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) [2024-11-18 13:27:21,970 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:27:21,970 INFO L93 Difference]: Finished difference Result 288 states and 402 transitions. [2024-11-18 13:27:21,970 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-18 13:27:21,971 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) Word has length 114 [2024-11-18 13:27:21,971 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:27:21,973 INFO L225 Difference]: With dead ends: 288 [2024-11-18 13:27:21,973 INFO L226 Difference]: Without dead ends: 286 [2024-11-18 13:27:21,974 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 101 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=88, Invalid=374, Unknown=0, NotChecked=0, Total=462 [2024-11-18 13:27:21,974 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 25 mSDsluCounter, 359 mSDsCounter, 0 mSdLazyCounter, 444 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 405 SdHoareTripleChecker+Invalid, 469 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 444 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-18 13:27:21,974 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 405 Invalid, 469 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 444 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-18 13:27:21,975 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 286 states. [2024-11-18 13:27:22,119 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 286 to 282. [2024-11-18 13:27:22,120 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 282 states, 147 states have (on average 1.163265306122449) internal successors, (171), 148 states have internal predecessors, (171), 113 states have call successors, (113), 21 states have call predecessors, (113), 21 states have return successors, (112), 112 states have call predecessors, (112), 112 states have call successors, (112) [2024-11-18 13:27:22,122 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 282 states to 282 states and 396 transitions. [2024-11-18 13:27:22,122 INFO L78 Accepts]: Start accepts. Automaton has 282 states and 396 transitions. Word has length 114 [2024-11-18 13:27:22,125 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:27:22,125 INFO L471 AbstractCegarLoop]: Abstraction has 282 states and 396 transitions. [2024-11-18 13:27:22,125 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 12 states have internal predecessors, (27), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) [2024-11-18 13:27:22,125 INFO L276 IsEmpty]: Start isEmpty. Operand 282 states and 396 transitions. [2024-11-18 13:27:22,127 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2024-11-18 13:27:22,127 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:27:22,127 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:27:22,148 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-18 13:27:22,327 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,SelfDestructingSolverStorable15 [2024-11-18 13:27:22,327 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:27:22,328 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:27:22,328 INFO L85 PathProgramCache]: Analyzing trace with hash -1051373609, now seen corresponding path program 5 times [2024-11-18 13:27:22,328 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:27:22,328 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1107019695] [2024-11-18 13:27:22,328 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-18 13:27:22,328 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:27:22,352 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2024-11-18 13:27:22,352 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:27:22,353 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [137333195] [2024-11-18 13:27:22,353 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-18 13:27:22,353 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:27:22,353 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:27:22,355 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:27:22,356 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:27:22,672 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2024-11-18 13:27:22,672 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:27:22,673 INFO L255 TraceCheckSpWp]: Trace formula consists of 278 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-18 13:27:22,675 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:27:23,811 INFO L134 CoverageAnalysis]: Checked inductivity of 514 backedges. 71 proven. 41 refuted. 0 times theorem prover too weak. 402 trivial. 0 not checked. [2024-11-18 13:27:23,811 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:27:24,428 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:27:24,428 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1107019695] [2024-11-18 13:27:24,429 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:27:24,429 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [137333195] [2024-11-18 13:27:24,429 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [137333195] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:27:24,429 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:27:24,429 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-11-18 13:27:24,429 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1440561033] [2024-11-18 13:27:24,429 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:27:24,429 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-18 13:27:24,429 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:27:24,430 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-18 13:27:24,430 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=259, Unknown=0, NotChecked=0, Total=306 [2024-11-18 13:27:24,430 INFO L87 Difference]: Start difference. First operand 282 states and 396 transitions. Second operand has 15 states, 14 states have (on average 2.142857142857143) internal successors, (30), 13 states have internal predecessors, (30), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (19), 7 states have call predecessors, (19), 6 states have call successors, (19) [2024-11-18 13:27:25,531 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:27:25,531 INFO L93 Difference]: Finished difference Result 297 states and 409 transitions. [2024-11-18 13:27:25,532 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-18 13:27:25,532 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.142857142857143) internal successors, (30), 13 states have internal predecessors, (30), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (19), 7 states have call predecessors, (19), 6 states have call successors, (19) Word has length 117 [2024-11-18 13:27:25,533 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:27:25,534 INFO L225 Difference]: With dead ends: 297 [2024-11-18 13:27:25,534 INFO L226 Difference]: Without dead ends: 295 [2024-11-18 13:27:25,535 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 105 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=83, Invalid=469, Unknown=0, NotChecked=0, Total=552 [2024-11-18 13:27:25,536 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 25 mSDsluCounter, 450 mSDsCounter, 0 mSdLazyCounter, 520 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 497 SdHoareTripleChecker+Invalid, 534 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 520 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-11-18 13:27:25,536 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 497 Invalid, 534 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 520 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-11-18 13:27:25,536 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 295 states. [2024-11-18 13:27:25,657 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 295 to 290. [2024-11-18 13:27:25,658 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 290 states, 153 states have (on average 1.1568627450980393) internal successors, (177), 154 states have internal predecessors, (177), 113 states have call successors, (113), 23 states have call predecessors, (113), 23 states have return successors, (112), 112 states have call predecessors, (112), 112 states have call successors, (112) [2024-11-18 13:27:25,659 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 290 states to 290 states and 402 transitions. [2024-11-18 13:27:25,660 INFO L78 Accepts]: Start accepts. Automaton has 290 states and 402 transitions. Word has length 117 [2024-11-18 13:27:25,660 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:27:25,660 INFO L471 AbstractCegarLoop]: Abstraction has 290 states and 402 transitions. [2024-11-18 13:27:25,660 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.142857142857143) internal successors, (30), 13 states have internal predecessors, (30), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (19), 7 states have call predecessors, (19), 6 states have call successors, (19) [2024-11-18 13:27:25,661 INFO L276 IsEmpty]: Start isEmpty. Operand 290 states and 402 transitions. [2024-11-18 13:27:25,662 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2024-11-18 13:27:25,662 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:27:25,662 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:27:25,671 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:27:25,863 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,SelfDestructingSolverStorable16 [2024-11-18 13:27:25,864 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:27:25,864 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:27:25,864 INFO L85 PathProgramCache]: Analyzing trace with hash 898620650, now seen corresponding path program 2 times [2024-11-18 13:27:25,864 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:27:25,864 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1149638909] [2024-11-18 13:27:25,864 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:27:25,865 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:27:25,901 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:27:25,901 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:27:25,902 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [10671161] [2024-11-18 13:27:25,902 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:27:25,903 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:27:25,903 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:27:25,904 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:27:25,914 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:27:25,980 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:27:25,981 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:27:25,982 INFO L255 TraceCheckSpWp]: Trace formula consists of 289 conjuncts, 65 conjuncts are in the unsatisfiable core [2024-11-18 13:27:25,985 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:27:26,658 INFO L134 CoverageAnalysis]: Checked inductivity of 579 backedges. 76 proven. 53 refuted. 0 times theorem prover too weak. 450 trivial. 0 not checked. [2024-11-18 13:27:26,658 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:27:28,954 INFO L134 CoverageAnalysis]: Checked inductivity of 579 backedges. 73 proven. 47 refuted. 0 times theorem prover too weak. 459 trivial. 0 not checked. [2024-11-18 13:27:28,954 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:27:28,954 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1149638909] [2024-11-18 13:27:28,954 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:27:28,954 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [10671161] [2024-11-18 13:27:28,954 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [10671161] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:27:28,954 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:27:28,954 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 15] total 30 [2024-11-18 13:27:28,954 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1336111150] [2024-11-18 13:27:28,954 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:27:28,955 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2024-11-18 13:27:28,955 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:27:28,956 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2024-11-18 13:27:28,956 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=133, Invalid=737, Unknown=0, NotChecked=0, Total=870 [2024-11-18 13:27:28,956 INFO L87 Difference]: Start difference. First operand 290 states and 402 transitions. Second operand has 30 states, 28 states have (on average 1.9642857142857142) internal successors, (55), 27 states have internal predecessors, (55), 14 states have call successors, (40), 3 states have call predecessors, (40), 3 states have return successors, (39), 13 states have call predecessors, (39), 12 states have call successors, (39) [2024-11-18 13:27:35,943 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:27:35,944 INFO L93 Difference]: Finished difference Result 367 states and 505 transitions. [2024-11-18 13:27:35,944 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2024-11-18 13:27:35,944 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 28 states have (on average 1.9642857142857142) internal successors, (55), 27 states have internal predecessors, (55), 14 states have call successors, (40), 3 states have call predecessors, (40), 3 states have return successors, (39), 13 states have call predecessors, (39), 12 states have call successors, (39) Word has length 123 [2024-11-18 13:27:35,944 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:27:35,946 INFO L225 Difference]: With dead ends: 367 [2024-11-18 13:27:35,946 INFO L226 Difference]: Without dead ends: 359 [2024-11-18 13:27:35,947 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 271 GetRequests, 216 SyntacticMatches, 0 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 557 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=589, Invalid=2603, Unknown=0, NotChecked=0, Total=3192 [2024-11-18 13:27:35,948 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 134 mSDsluCounter, 795 mSDsCounter, 0 mSdLazyCounter, 1254 mSolverCounterSat, 193 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 844 SdHoareTripleChecker+Invalid, 1447 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 193 IncrementalHoareTripleChecker+Valid, 1254 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:27:35,948 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 844 Invalid, 1447 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [193 Valid, 1254 Invalid, 0 Unknown, 0 Unchecked, 4.2s Time] [2024-11-18 13:27:35,949 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 359 states. [2024-11-18 13:27:36,119 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 359 to 316. [2024-11-18 13:27:36,119 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 316 states, 168 states have (on average 1.1428571428571428) internal successors, (192), 170 states have internal predecessors, (192), 120 states have call successors, (120), 27 states have call predecessors, (120), 27 states have return successors, (119), 118 states have call predecessors, (119), 119 states have call successors, (119) [2024-11-18 13:27:36,121 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 316 states to 316 states and 431 transitions. [2024-11-18 13:27:36,121 INFO L78 Accepts]: Start accepts. Automaton has 316 states and 431 transitions. Word has length 123 [2024-11-18 13:27:36,121 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:27:36,121 INFO L471 AbstractCegarLoop]: Abstraction has 316 states and 431 transitions. [2024-11-18 13:27:36,122 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 28 states have (on average 1.9642857142857142) internal successors, (55), 27 states have internal predecessors, (55), 14 states have call successors, (40), 3 states have call predecessors, (40), 3 states have return successors, (39), 13 states have call predecessors, (39), 12 states have call successors, (39) [2024-11-18 13:27:36,122 INFO L276 IsEmpty]: Start isEmpty. Operand 316 states and 431 transitions. [2024-11-18 13:27:36,123 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2024-11-18 13:27:36,123 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:27:36,123 INFO L215 NwaCegarLoop]: trace histogram [19, 18, 18, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:27:36,135 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:27:36,323 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-18 13:27:36,323 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:27:36,324 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:27:36,324 INFO L85 PathProgramCache]: Analyzing trace with hash -1287524986, now seen corresponding path program 6 times [2024-11-18 13:27:36,324 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:27:36,324 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [367647240] [2024-11-18 13:27:36,324 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-18 13:27:36,324 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:27:36,359 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2024-11-18 13:27:36,360 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:27:36,361 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [882839414] [2024-11-18 13:27:36,361 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-18 13:27:36,361 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:27:36,361 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:27:36,363 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:27:36,364 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:27:36,541 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2024-11-18 13:27:36,542 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:27:36,544 INFO L255 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 80 conjuncts are in the unsatisfiable core [2024-11-18 13:27:36,547 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:27:39,596 INFO L134 CoverageAnalysis]: Checked inductivity of 731 backedges. 147 proven. 86 refuted. 0 times theorem prover too weak. 498 trivial. 0 not checked. [2024-11-18 13:27:39,597 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:27:42,260 INFO L134 CoverageAnalysis]: Checked inductivity of 731 backedges. 184 proven. 38 refuted. 0 times theorem prover too weak. 509 trivial. 0 not checked. [2024-11-18 13:27:42,260 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:27:42,260 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [367647240] [2024-11-18 13:27:42,260 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:27:42,260 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [882839414] [2024-11-18 13:27:42,260 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [882839414] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:27:42,260 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:27:42,261 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 12] total 28 [2024-11-18 13:27:42,261 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1717293739] [2024-11-18 13:27:42,261 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:27:42,261 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-11-18 13:27:42,261 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:27:42,262 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-18 13:27:42,264 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=641, Unknown=0, NotChecked=0, Total=756 [2024-11-18 13:27:42,264 INFO L87 Difference]: Start difference. First operand 316 states and 431 transitions. Second operand has 28 states, 26 states have (on average 2.076923076923077) internal successors, (54), 20 states have internal predecessors, (54), 13 states have call successors, (37), 3 states have call predecessors, (37), 3 states have return successors, (36), 15 states have call predecessors, (36), 11 states have call successors, (36) [2024-11-18 13:27:50,273 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:27:50,273 INFO L93 Difference]: Finished difference Result 389 states and 539 transitions. [2024-11-18 13:27:50,273 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2024-11-18 13:27:50,274 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 26 states have (on average 2.076923076923077) internal successors, (54), 20 states have internal predecessors, (54), 13 states have call successors, (37), 3 states have call predecessors, (37), 3 states have return successors, (36), 15 states have call predecessors, (36), 11 states have call successors, (36) Word has length 134 [2024-11-18 13:27:50,274 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:27:50,276 INFO L225 Difference]: With dead ends: 389 [2024-11-18 13:27:50,276 INFO L226 Difference]: Without dead ends: 387 [2024-11-18 13:27:50,277 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 288 GetRequests, 240 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 503 ImplicationChecksByTransitivity, 7.1s TimeCoverageRelationStatistics Valid=443, Invalid=2007, Unknown=0, NotChecked=0, Total=2450 [2024-11-18 13:27:50,278 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 45 mSDsluCounter, 571 mSDsCounter, 0 mSdLazyCounter, 667 mSolverCounterSat, 101 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 617 SdHoareTripleChecker+Invalid, 768 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 101 IncrementalHoareTripleChecker+Valid, 667 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.4s IncrementalHoareTripleChecker+Time [2024-11-18 13:27:50,278 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 617 Invalid, 768 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [101 Valid, 667 Invalid, 0 Unknown, 0 Unchecked, 3.4s Time] [2024-11-18 13:27:50,278 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 387 states. [2024-11-18 13:27:50,539 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 387 to 382. [2024-11-18 13:27:50,540 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 382 states, 199 states have (on average 1.150753768844221) internal successors, (229), 201 states have internal predecessors, (229), 152 states have call successors, (152), 30 states have call predecessors, (152), 30 states have return successors, (151), 150 states have call predecessors, (151), 151 states have call successors, (151) [2024-11-18 13:27:50,542 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 382 states to 382 states and 532 transitions. [2024-11-18 13:27:50,543 INFO L78 Accepts]: Start accepts. Automaton has 382 states and 532 transitions. Word has length 134 [2024-11-18 13:27:50,543 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:27:50,543 INFO L471 AbstractCegarLoop]: Abstraction has 382 states and 532 transitions. [2024-11-18 13:27:50,543 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 26 states have (on average 2.076923076923077) internal successors, (54), 20 states have internal predecessors, (54), 13 states have call successors, (37), 3 states have call predecessors, (37), 3 states have return successors, (36), 15 states have call predecessors, (36), 11 states have call successors, (36) [2024-11-18 13:27:50,543 INFO L276 IsEmpty]: Start isEmpty. Operand 382 states and 532 transitions. [2024-11-18 13:27:50,545 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 140 [2024-11-18 13:27:50,545 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:27:50,545 INFO L215 NwaCegarLoop]: trace histogram [20, 19, 19, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:27:50,552 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2024-11-18 13:27:50,747 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:27:50,747 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:27:50,748 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:27:50,748 INFO L85 PathProgramCache]: Analyzing trace with hash 1501327478, now seen corresponding path program 7 times [2024-11-18 13:27:50,748 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:27:50,748 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1692238923] [2024-11-18 13:27:50,748 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-18 13:27:50,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:27:50,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:27:50,781 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [397662794] [2024-11-18 13:27:50,781 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-18 13:27:50,781 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:27:50,781 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:27:50,789 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:27:50,790 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:27:50,889 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:27:50,891 INFO L255 TraceCheckSpWp]: Trace formula consists of 320 conjuncts, 80 conjuncts are in the unsatisfiable core [2024-11-18 13:27:50,895 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:27:52,929 INFO L134 CoverageAnalysis]: Checked inductivity of 809 backedges. 166 proven. 124 refuted. 0 times theorem prover too weak. 519 trivial. 0 not checked. [2024-11-18 13:27:52,929 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:27:54,823 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:27:54,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1692238923] [2024-11-18 13:27:54,823 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:27:54,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [397662794] [2024-11-18 13:27:54,824 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [397662794] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:27:54,824 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:27:54,824 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2024-11-18 13:27:54,824 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1032413748] [2024-11-18 13:27:54,824 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:27:54,824 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-18 13:27:54,824 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:27:54,825 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-18 13:27:54,825 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=842, Unknown=0, NotChecked=0, Total=992 [2024-11-18 13:27:54,825 INFO L87 Difference]: Start difference. First operand 382 states and 532 transitions. Second operand has 24 states, 21 states have (on average 1.6666666666666667) internal successors, (35), 18 states have internal predecessors, (35), 10 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (23), 11 states have call predecessors, (23), 9 states have call successors, (23) [2024-11-18 13:27:56,483 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:27:56,484 INFO L93 Difference]: Finished difference Result 416 states and 580 transitions. [2024-11-18 13:27:56,484 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-18 13:27:56,484 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 21 states have (on average 1.6666666666666667) internal successors, (35), 18 states have internal predecessors, (35), 10 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (23), 11 states have call predecessors, (23), 9 states have call successors, (23) Word has length 139 [2024-11-18 13:27:56,484 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:27:56,486 INFO L225 Difference]: With dead ends: 416 [2024-11-18 13:27:56,486 INFO L226 Difference]: Without dead ends: 414 [2024-11-18 13:27:56,487 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 133 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 333 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=254, Invalid=1468, Unknown=0, NotChecked=0, Total=1722 [2024-11-18 13:27:56,487 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 49 mSDsluCounter, 504 mSDsCounter, 0 mSdLazyCounter, 767 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 548 SdHoareTripleChecker+Invalid, 802 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 767 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-18 13:27:56,487 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 548 Invalid, 802 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 767 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-18 13:27:56,488 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 414 states. [2024-11-18 13:27:56,860 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 414 to 410. [2024-11-18 13:27:56,861 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 410 states, 212 states have (on average 1.1556603773584906) internal successors, (245), 213 states have internal predecessors, (245), 165 states have call successors, (165), 32 states have call predecessors, (165), 32 states have return successors, (164), 164 states have call predecessors, (164), 164 states have call successors, (164) [2024-11-18 13:27:56,863 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 410 states to 410 states and 574 transitions. [2024-11-18 13:27:56,863 INFO L78 Accepts]: Start accepts. Automaton has 410 states and 574 transitions. Word has length 139 [2024-11-18 13:27:56,864 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:27:56,864 INFO L471 AbstractCegarLoop]: Abstraction has 410 states and 574 transitions. [2024-11-18 13:27:56,864 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 21 states have (on average 1.6666666666666667) internal successors, (35), 18 states have internal predecessors, (35), 10 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (23), 11 states have call predecessors, (23), 9 states have call successors, (23) [2024-11-18 13:27:56,864 INFO L276 IsEmpty]: Start isEmpty. Operand 410 states and 574 transitions. [2024-11-18 13:27:56,866 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 140 [2024-11-18 13:27:56,866 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:27:56,866 INFO L215 NwaCegarLoop]: trace histogram [20, 19, 19, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:27:56,883 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2024-11-18 13:27:57,066 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:27:57,067 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:27:57,067 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:27:57,067 INFO L85 PathProgramCache]: Analyzing trace with hash -1804546984, now seen corresponding path program 8 times [2024-11-18 13:27:57,067 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:27:57,067 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [863350082] [2024-11-18 13:27:57,067 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:27:57,067 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:27:57,093 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:27:57,093 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:27:57,097 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [105943954] [2024-11-18 13:27:57,097 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:27:57,097 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:27:57,097 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:27:57,098 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:27:57,100 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:27:57,187 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:27:57,188 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:27:57,190 INFO L255 TraceCheckSpWp]: Trace formula consists of 320 conjuncts, 52 conjuncts are in the unsatisfiable core [2024-11-18 13:27:57,193 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:28:03,624 INFO L134 CoverageAnalysis]: Checked inductivity of 809 backedges. 166 proven. 115 refuted. 0 times theorem prover too weak. 528 trivial. 0 not checked. [2024-11-18 13:28:03,624 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:28:04,263 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:28:04,263 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [863350082] [2024-11-18 13:28:04,263 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:28:04,263 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [105943954] [2024-11-18 13:28:04,263 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [105943954] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:28:04,263 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:28:04,264 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2024-11-18 13:28:04,264 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1573027986] [2024-11-18 13:28:04,264 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:28:04,264 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-18 13:28:04,264 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:28:04,264 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-18 13:28:04,265 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=408, Unknown=0, NotChecked=0, Total=462 [2024-11-18 13:28:04,265 INFO L87 Difference]: Start difference. First operand 410 states and 574 transitions. Second operand has 20 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (23), 12 states have call predecessors, (23), 8 states have call successors, (23)