./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3061b6dc Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound2.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 ebdf8b0d6633d593d56778eaf5218135ab2be92cae14e75cdda2462494f96410 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-18 13:35:43,363 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-18 13:35:43,427 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-18 13:35:43,431 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-18 13:35:43,431 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-18 13:35:43,451 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-18 13:35:43,452 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-18 13:35:43,452 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-18 13:35:43,453 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-18 13:35:43,453 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-18 13:35:43,454 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-18 13:35:43,454 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-18 13:35:43,455 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-18 13:35:43,455 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-18 13:35:43,455 INFO L153 SettingsManager]: * Use SBE=true [2024-11-18 13:35:43,456 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-18 13:35:43,456 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-18 13:35:43,456 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-18 13:35:43,457 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-18 13:35:43,457 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-18 13:35:43,458 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-18 13:35:43,462 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-18 13:35:43,462 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-18 13:35:43,462 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-18 13:35:43,463 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-18 13:35:43,463 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-18 13:35:43,463 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-18 13:35:43,464 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-18 13:35:43,464 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-18 13:35:43,464 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-18 13:35:43,465 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-18 13:35:43,465 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-18 13:35:43,466 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:35:43,466 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-18 13:35:43,466 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-18 13:35:43,467 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-18 13:35:43,467 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-18 13:35:43,467 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-18 13:35:43,467 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-18 13:35:43,467 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-18 13:35:43,468 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-18 13:35:43,468 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-18 13:35:43,468 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 -> ebdf8b0d6633d593d56778eaf5218135ab2be92cae14e75cdda2462494f96410 [2024-11-18 13:35:43,704 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-18 13:35:43,732 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-18 13:35:43,735 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-18 13:35:43,736 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-18 13:35:43,736 INFO L274 PluginConnector]: CDTParser initialized [2024-11-18 13:35:43,737 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound2.c [2024-11-18 13:35:45,181 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-18 13:35:45,372 INFO L384 CDTParser]: Found 1 translation units. [2024-11-18 13:35:45,373 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound2.c [2024-11-18 13:35:45,381 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/959de7220/9c7a2418ae3c488f805ef9dc4f03b5c5/FLAG27f4faff3 [2024-11-18 13:35:45,397 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/959de7220/9c7a2418ae3c488f805ef9dc4f03b5c5 [2024-11-18 13:35:45,401 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-18 13:35:45,403 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-18 13:35:45,406 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-18 13:35:45,406 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-18 13:35:45,410 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-18 13:35:45,411 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,412 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@578a9b32 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45, skipping insertion in model container [2024-11-18 13:35:45,412 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,432 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-18 13:35:45,598 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound2.c[490,503] [2024-11-18 13:35:45,620 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:35:45,631 INFO L200 MainTranslator]: Completed pre-run [2024-11-18 13:35:45,640 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound2.c[490,503] [2024-11-18 13:35:45,654 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:35:45,670 INFO L204 MainTranslator]: Completed translation [2024-11-18 13:35:45,670 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45 WrapperNode [2024-11-18 13:35:45,671 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-18 13:35:45,672 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-18 13:35:45,672 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-18 13:35:45,672 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-18 13:35:45,679 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,685 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,701 INFO L138 Inliner]: procedures = 14, calls = 19, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 79 [2024-11-18 13:35:45,701 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-18 13:35:45,702 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-18 13:35:45,702 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-18 13:35:45,702 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-18 13:35:45,711 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,712 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,713 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,725 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-18 13:35:45,725 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,726 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,729 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,732 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,733 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,734 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,735 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-18 13:35:45,736 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-18 13:35:45,736 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-18 13:35:45,737 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-18 13:35:45,737 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45" (1/1) ... [2024-11-18 13:35:45,742 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:35:45,752 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:45,773 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-18 13:35:45,776 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-18 13:35:45,836 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-18 13:35:45,836 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-18 13:35:45,836 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-18 13:35:45,836 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-18 13:35:45,837 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-18 13:35:45,837 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-18 13:35:45,837 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-18 13:35:45,839 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-18 13:35:45,921 INFO L238 CfgBuilder]: Building ICFG [2024-11-18 13:35:45,924 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-18 13:35:46,145 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-11-18 13:35:46,146 INFO L287 CfgBuilder]: Performing block encoding [2024-11-18 13:35:46,163 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-18 13:35:46,164 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-18 13:35:46,164 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:35:46 BoogieIcfgContainer [2024-11-18 13:35:46,164 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-18 13:35:46,168 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-18 13:35:46,169 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-18 13:35:46,173 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-18 13:35:46,174 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.11 01:35:45" (1/3) ... [2024-11-18 13:35:46,175 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f21efad and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:35:46, skipping insertion in model container [2024-11-18 13:35:46,175 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:35:45" (2/3) ... [2024-11-18 13:35:46,175 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f21efad and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:35:46, skipping insertion in model container [2024-11-18 13:35:46,175 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:35:46" (3/3) ... [2024-11-18 13:35:46,177 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll_valuebound2.c [2024-11-18 13:35:46,196 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-18 13:35:46,196 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-18 13:35:46,248 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-18 13:35:46,254 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;@1aa92ef0, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-18 13:35:46,255 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-18 13:35:46,259 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 21 states have internal predecessors, (28), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-18 13:35:46,265 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-18 13:35:46,265 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:46,266 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:46,266 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:46,270 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:46,270 INFO L85 PathProgramCache]: Analyzing trace with hash -1146169762, now seen corresponding path program 1 times [2024-11-18 13:35:46,277 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:46,277 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [490289442] [2024-11-18 13:35:46,277 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:46,278 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:46,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:46,475 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-11-18 13:35:46,475 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:46,475 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [490289442] [2024-11-18 13:35:46,476 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [490289442] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:46,476 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1117130621] [2024-11-18 13:35:46,476 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:46,477 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:46,477 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:46,481 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:46,483 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-18 13:35:46,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:46,562 INFO L255 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-18 13:35:46,568 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:46,584 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-11-18 13:35:46,585 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:35:46,585 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1117130621] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:35:46,585 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:35:46,586 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-11-18 13:35:46,588 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1611829902] [2024-11-18 13:35:46,589 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:35:46,592 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-18 13:35:46,593 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:46,610 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-18 13:35:46,611 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 13:35:46,612 INFO L87 Difference]: Start difference. First operand has 35 states, 19 states have (on average 1.4736842105263157) internal successors, (28), 21 states have internal predecessors, (28), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-18 13:35:46,635 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:46,636 INFO L93 Difference]: Finished difference Result 67 states and 112 transitions. [2024-11-18 13:35:46,637 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-18 13:35:46,639 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) Word has length 39 [2024-11-18 13:35:46,639 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:46,645 INFO L225 Difference]: With dead ends: 67 [2024-11-18 13:35:46,645 INFO L226 Difference]: Without dead ends: 31 [2024-11-18 13:35:46,649 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 13:35:46,652 INFO L432 NwaCegarLoop]: 46 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, 46 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:46,653 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:35:46,667 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-18 13:35:46,686 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2024-11-18 13:35:46,687 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-18 13:35:46,688 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 42 transitions. [2024-11-18 13:35:46,690 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 42 transitions. Word has length 39 [2024-11-18 13:35:46,690 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:46,690 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 42 transitions. [2024-11-18 13:35:46,691 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-18 13:35:46,691 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 42 transitions. [2024-11-18 13:35:46,692 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-18 13:35:46,692 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:46,693 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:46,705 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:35:46,894 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2024-11-18 13:35:46,895 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:46,896 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:46,896 INFO L85 PathProgramCache]: Analyzing trace with hash 846808023, now seen corresponding path program 1 times [2024-11-18 13:35:46,896 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:46,896 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1136346942] [2024-11-18 13:35:46,897 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:46,897 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:46,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:47,247 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-18 13:35:47,248 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:47,248 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1136346942] [2024-11-18 13:35:47,248 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1136346942] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:47,248 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1193814131] [2024-11-18 13:35:47,248 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:47,248 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:47,249 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:47,251 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:47,252 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-18 13:35:47,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:47,333 INFO L255 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-18 13:35:47,339 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:47,657 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 3 proven. 12 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-18 13:35:47,659 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:47,807 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1193814131] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:47,809 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:35:47,809 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 9] total 11 [2024-11-18 13:35:47,810 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1311532725] [2024-11-18 13:35:47,810 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:35:47,811 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-18 13:35:47,811 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:47,812 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-18 13:35:47,814 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=173, Unknown=0, NotChecked=0, Total=210 [2024-11-18 13:35:47,814 INFO L87 Difference]: Start difference. First operand 31 states and 42 transitions. Second operand has 11 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-18 13:35:48,039 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:48,039 INFO L93 Difference]: Finished difference Result 52 states and 69 transitions. [2024-11-18 13:35:48,039 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-18 13:35:48,040 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 40 [2024-11-18 13:35:48,040 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:48,041 INFO L225 Difference]: With dead ends: 52 [2024-11-18 13:35:48,041 INFO L226 Difference]: Without dead ends: 44 [2024-11-18 13:35:48,042 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=251, Unknown=0, NotChecked=0, Total=306 [2024-11-18 13:35:48,043 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 31 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 155 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 178 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 155 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:48,044 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 194 Invalid, 178 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 155 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:35:48,045 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2024-11-18 13:35:48,056 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 43. [2024-11-18 13:35:48,056 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 16 states have call successors, (16), 3 states have call predecessors, (16), 3 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-18 13:35:48,060 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 58 transitions. [2024-11-18 13:35:48,061 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 58 transitions. Word has length 40 [2024-11-18 13:35:48,062 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:48,062 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 58 transitions. [2024-11-18 13:35:48,063 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-18 13:35:48,064 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 58 transitions. [2024-11-18 13:35:48,065 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-18 13:35:48,065 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:48,065 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:48,079 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:35:48,265 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:35:48,266 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:48,267 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:48,267 INFO L85 PathProgramCache]: Analyzing trace with hash 481927254, now seen corresponding path program 1 times [2024-11-18 13:35:48,267 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:48,268 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2125396707] [2024-11-18 13:35:48,268 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:48,268 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:48,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:35:48,313 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1395857116] [2024-11-18 13:35:48,313 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:48,313 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:48,313 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:48,318 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:48,320 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-18 13:35:48,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:48,372 INFO L255 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-18 13:35:48,374 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:48,403 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-18 13:35:48,404 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:35:48,404 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:48,404 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2125396707] [2024-11-18 13:35:48,405 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:35:48,405 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1395857116] [2024-11-18 13:35:48,405 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1395857116] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:35:48,405 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:35:48,405 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:35:48,406 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [233424240] [2024-11-18 13:35:48,406 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:35:48,406 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:35:48,406 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:48,407 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:35:48,407 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:35:48,407 INFO L87 Difference]: Start difference. First operand 43 states and 58 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-18 13:35:48,452 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:48,452 INFO L93 Difference]: Finished difference Result 62 states and 86 transitions. [2024-11-18 13:35:48,453 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:35:48,453 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 41 [2024-11-18 13:35:48,453 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:48,454 INFO L225 Difference]: With dead ends: 62 [2024-11-18 13:35:48,455 INFO L226 Difference]: Without dead ends: 60 [2024-11-18 13:35:48,455 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-18 13:35:48,456 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 4 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:48,456 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 136 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:35:48,457 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-11-18 13:35:48,467 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 51. [2024-11-18 13:35:48,467 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 28 states have (on average 1.1428571428571428) internal successors, (32), 31 states have internal predecessors, (32), 18 states have call successors, (18), 4 states have call predecessors, (18), 4 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-18 13:35:48,468 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 67 transitions. [2024-11-18 13:35:48,468 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 67 transitions. Word has length 41 [2024-11-18 13:35:48,469 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:48,469 INFO L471 AbstractCegarLoop]: Abstraction has 51 states and 67 transitions. [2024-11-18 13:35:48,469 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-18 13:35:48,469 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 67 transitions. [2024-11-18 13:35:48,470 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-11-18 13:35:48,470 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:48,470 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:48,487 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:35:48,671 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:35:48,672 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:48,672 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:48,672 INFO L85 PathProgramCache]: Analyzing trace with hash -1626076469, now seen corresponding path program 1 times [2024-11-18 13:35:48,672 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:48,673 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2141785102] [2024-11-18 13:35:48,673 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:48,673 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:48,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:35:48,691 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1923125295] [2024-11-18 13:35:48,692 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:48,692 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:48,692 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:48,693 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:48,695 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-18 13:35:48,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:48,749 INFO L255 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-18 13:35:48,751 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:48,831 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-18 13:35:48,831 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:35:48,831 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:48,831 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2141785102] [2024-11-18 13:35:48,832 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:35:48,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1923125295] [2024-11-18 13:35:48,832 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1923125295] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:35:48,832 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:35:48,832 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:35:48,832 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [351837883] [2024-11-18 13:35:48,832 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:35:48,833 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:35:48,833 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:48,833 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:35:48,833 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:35:48,833 INFO L87 Difference]: Start difference. First operand 51 states and 67 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-18 13:35:48,879 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:48,880 INFO L93 Difference]: Finished difference Result 58 states and 73 transitions. [2024-11-18 13:35:48,880 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:35:48,880 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (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 46 [2024-11-18 13:35:48,881 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:48,884 INFO L225 Difference]: With dead ends: 58 [2024-11-18 13:35:48,884 INFO L226 Difference]: Without dead ends: 56 [2024-11-18 13:35:48,885 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-18 13:35:48,885 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 5 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:48,886 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 146 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:35:48,886 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2024-11-18 13:35:48,903 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2024-11-18 13:35:48,903 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 34 states have internal predecessors, (35), 18 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-18 13:35:48,904 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 70 transitions. [2024-11-18 13:35:48,905 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 70 transitions. Word has length 46 [2024-11-18 13:35:48,905 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:48,905 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 70 transitions. [2024-11-18 13:35:48,905 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-18 13:35:48,905 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 70 transitions. [2024-11-18 13:35:48,906 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-11-18 13:35:48,906 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:48,906 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:48,923 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-18 13:35:49,109 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:35:49,109 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:49,109 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:49,110 INFO L85 PathProgramCache]: Analyzing trace with hash -670274197, now seen corresponding path program 1 times [2024-11-18 13:35:49,110 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:49,110 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [912673164] [2024-11-18 13:35:49,110 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:49,110 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:49,133 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:35:49,134 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [715900894] [2024-11-18 13:35:49,134 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:49,134 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:49,135 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:49,136 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:49,137 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-18 13:35:49,202 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:49,209 INFO L255 TraceCheckSpWp]: Trace formula consists of 142 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-18 13:35:49,211 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:49,483 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-18 13:35:49,483 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:49,538 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:49,538 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [912673164] [2024-11-18 13:35:49,538 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:35:49,539 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [715900894] [2024-11-18 13:35:49,539 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [715900894] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:49,539 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:35:49,542 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2024-11-18 13:35:49,542 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [293731182] [2024-11-18 13:35:49,542 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:35:49,543 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-18 13:35:49,543 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:49,543 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-18 13:35:49,544 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2024-11-18 13:35:49,544 INFO L87 Difference]: Start difference. First operand 55 states and 70 transitions. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2024-11-18 13:35:49,638 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:49,638 INFO L93 Difference]: Finished difference Result 62 states and 76 transitions. [2024-11-18 13:35:49,639 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-18 13:35:49,639 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 56 [2024-11-18 13:35:49,639 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:49,640 INFO L225 Difference]: With dead ends: 62 [2024-11-18 13:35:49,640 INFO L226 Difference]: Without dead ends: 60 [2024-11-18 13:35:49,641 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 52 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2024-11-18 13:35:49,641 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 8 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 78 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 83 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 78 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:49,642 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 138 Invalid, 83 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 78 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:35:49,642 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-11-18 13:35:49,653 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2024-11-18 13:35:49,654 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 34 states have (on average 1.1176470588235294) internal successors, (38), 37 states have internal predecessors, (38), 18 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-18 13:35:49,656 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 73 transitions. [2024-11-18 13:35:49,656 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 73 transitions. Word has length 56 [2024-11-18 13:35:49,657 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:49,657 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 73 transitions. [2024-11-18 13:35:49,657 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2024-11-18 13:35:49,657 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 73 transitions. [2024-11-18 13:35:49,658 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2024-11-18 13:35:49,658 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:49,658 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:49,676 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-18 13:35:49,862 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:35:49,863 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:49,863 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:49,863 INFO L85 PathProgramCache]: Analyzing trace with hash 815241237, now seen corresponding path program 1 times [2024-11-18 13:35:49,863 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:49,867 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [862404605] [2024-11-18 13:35:49,867 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:49,867 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:49,901 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:35:49,906 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1886004180] [2024-11-18 13:35:49,906 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:49,906 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:49,907 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:49,908 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:49,910 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-18 13:35:49,967 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:49,968 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-18 13:35:49,971 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:50,045 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-18 13:35:50,045 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:50,132 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-18 13:35:50,132 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:50,132 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [862404605] [2024-11-18 13:35:50,132 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:35:50,133 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1886004180] [2024-11-18 13:35:50,133 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1886004180] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:35:50,133 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:35:50,133 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2024-11-18 13:35:50,133 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [17558707] [2024-11-18 13:35:50,133 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:35:50,134 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-18 13:35:50,134 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:50,135 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-18 13:35:50,135 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-18 13:35:50,135 INFO L87 Difference]: Start difference. First operand 59 states and 73 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, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-11-18 13:35:50,224 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:50,224 INFO L93 Difference]: Finished difference Result 87 states and 118 transitions. [2024-11-18 13:35:50,225 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-18 13:35:50,225 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, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 63 [2024-11-18 13:35:50,226 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:50,226 INFO L225 Difference]: With dead ends: 87 [2024-11-18 13:35:50,226 INFO L226 Difference]: Without dead ends: 85 [2024-11-18 13:35:50,227 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 116 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:35:50,227 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 8 mSDsluCounter, 112 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 156 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:50,228 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 156 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:35:50,229 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2024-11-18 13:35:50,239 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 55. [2024-11-18 13:35:50,240 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 32 states have (on average 1.125) internal successors, (36), 33 states have internal predecessors, (36), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-18 13:35:50,240 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 67 transitions. [2024-11-18 13:35:50,241 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 67 transitions. Word has length 63 [2024-11-18 13:35:50,241 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:50,241 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 67 transitions. [2024-11-18 13:35:50,242 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, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-11-18 13:35:50,242 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 67 transitions. [2024-11-18 13:35:50,242 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2024-11-18 13:35:50,243 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:50,243 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:50,259 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-18 13:35:50,443 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:35:50,444 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:50,444 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:50,444 INFO L85 PathProgramCache]: Analyzing trace with hash -759965185, now seen corresponding path program 1 times [2024-11-18 13:35:50,444 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:50,444 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [877812416] [2024-11-18 13:35:50,445 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:50,445 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:50,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:50,669 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-11-18 13:35:50,669 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:50,669 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [877812416] [2024-11-18 13:35:50,669 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [877812416] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:50,669 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1733876888] [2024-11-18 13:35:50,670 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:50,670 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:50,670 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:50,671 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:50,673 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-18 13:35:50,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:50,737 INFO L255 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-18 13:35:50,739 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:50,788 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-11-18 13:35:50,788 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:50,890 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-11-18 13:35:50,891 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1733876888] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:35:50,891 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:35:50,891 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 12 [2024-11-18 13:35:50,892 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [518649837] [2024-11-18 13:35:50,892 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:35:50,892 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-18 13:35:50,892 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:50,893 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-18 13:35:50,893 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2024-11-18 13:35:50,893 INFO L87 Difference]: Start difference. First operand 55 states and 67 transitions. Second operand has 12 states, 12 states have (on average 2.75) internal successors, (33), 11 states have internal predecessors, (33), 7 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-18 13:35:51,091 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:51,092 INFO L93 Difference]: Finished difference Result 102 states and 142 transitions. [2024-11-18 13:35:51,092 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-18 13:35:51,092 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.75) internal successors, (33), 11 states have internal predecessors, (33), 7 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 65 [2024-11-18 13:35:51,093 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:51,094 INFO L225 Difference]: With dead ends: 102 [2024-11-18 13:35:51,094 INFO L226 Difference]: Without dead ends: 94 [2024-11-18 13:35:51,094 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 122 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=54, Invalid=156, Unknown=0, NotChecked=0, Total=210 [2024-11-18 13:35:51,095 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 34 mSDsluCounter, 259 mSDsCounter, 0 mSdLazyCounter, 159 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 303 SdHoareTripleChecker+Invalid, 189 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 159 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:51,095 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 303 Invalid, 189 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 159 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:35:51,096 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2024-11-18 13:35:51,117 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 85. [2024-11-18 13:35:51,118 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 46 states have (on average 1.1956521739130435) internal successors, (55), 47 states have internal predecessors, (55), 32 states have call successors, (32), 6 states have call predecessors, (32), 6 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2024-11-18 13:35:51,120 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 118 transitions. [2024-11-18 13:35:51,120 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 118 transitions. Word has length 65 [2024-11-18 13:35:51,121 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:51,121 INFO L471 AbstractCegarLoop]: Abstraction has 85 states and 118 transitions. [2024-11-18 13:35:51,121 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.75) internal successors, (33), 11 states have internal predecessors, (33), 7 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-18 13:35:51,123 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 118 transitions. [2024-11-18 13:35:51,124 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2024-11-18 13:35:51,124 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:51,124 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:51,144 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:35:51,325 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:35:51,325 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:51,326 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:51,326 INFO L85 PathProgramCache]: Analyzing trace with hash -696294669, now seen corresponding path program 1 times [2024-11-18 13:35:51,326 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:51,326 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2024895209] [2024-11-18 13:35:51,326 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:51,326 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:51,353 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:35:51,355 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [81556745] [2024-11-18 13:35:51,355 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:51,355 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:51,355 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:51,357 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:51,358 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-18 13:35:51,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:51,421 INFO L255 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-18 13:35:51,423 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:51,553 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 100 trivial. 0 not checked. [2024-11-18 13:35:51,554 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:51,593 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:51,593 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2024895209] [2024-11-18 13:35:51,593 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:35:51,593 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [81556745] [2024-11-18 13:35:51,593 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [81556745] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:51,593 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:35:51,593 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2024-11-18 13:35:51,594 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2050490156] [2024-11-18 13:35:51,594 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:35:51,595 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-18 13:35:51,595 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:51,595 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-18 13:35:51,595 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2024-11-18 13:35:51,596 INFO L87 Difference]: Start difference. First operand 85 states and 118 transitions. Second operand has 6 states, 6 states have (on average 3.5) internal successors, (21), 5 states have internal predecessors, (21), 3 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-18 13:35:51,710 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:51,710 INFO L93 Difference]: Finished difference Result 120 states and 169 transitions. [2024-11-18 13:35:51,710 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-18 13:35:51,711 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.5) internal successors, (21), 5 states have internal predecessors, (21), 3 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 71 [2024-11-18 13:35:51,711 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:51,714 INFO L225 Difference]: With dead ends: 120 [2024-11-18 13:35:51,714 INFO L226 Difference]: Without dead ends: 117 [2024-11-18 13:35:51,714 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 68 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-11-18 13:35:51,716 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 7 mSDsluCounter, 149 mSDsCounter, 0 mSdLazyCounter, 69 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 198 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 69 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:51,716 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 198 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 69 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:35:51,717 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2024-11-18 13:35:51,746 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 114. [2024-11-18 13:35:51,746 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 114 states, 61 states have (on average 1.2131147540983607) internal successors, (74), 63 states have internal predecessors, (74), 45 states have call successors, (45), 7 states have call predecessors, (45), 7 states have return successors, (43), 43 states have call predecessors, (43), 43 states have call successors, (43) [2024-11-18 13:35:51,747 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 162 transitions. [2024-11-18 13:35:51,747 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 162 transitions. Word has length 71 [2024-11-18 13:35:51,748 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:51,748 INFO L471 AbstractCegarLoop]: Abstraction has 114 states and 162 transitions. [2024-11-18 13:35:51,748 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.5) internal successors, (21), 5 states have internal predecessors, (21), 3 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-18 13:35:51,748 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 162 transitions. [2024-11-18 13:35:51,749 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-18 13:35:51,758 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:51,758 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:51,776 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:35:51,962 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:35:51,963 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:51,963 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:51,963 INFO L85 PathProgramCache]: Analyzing trace with hash 1352497678, now seen corresponding path program 2 times [2024-11-18 13:35:51,964 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:51,964 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [228612065] [2024-11-18 13:35:51,964 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:35:51,964 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:51,997 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:35:52,001 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:35:52,002 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2139433290] [2024-11-18 13:35:52,002 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:35:52,002 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:52,002 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:52,007 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:52,009 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-18 13:35:52,070 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:35:52,070 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:35:52,076 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-18 13:35:52,078 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:52,265 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-18 13:35:52,265 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:52,306 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:52,306 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [228612065] [2024-11-18 13:35:52,306 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:35:52,306 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2139433290] [2024-11-18 13:35:52,306 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2139433290] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:52,307 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:35:52,307 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2024-11-18 13:35:52,307 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1116761611] [2024-11-18 13:35:52,307 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:35:52,307 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-18 13:35:52,307 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:52,308 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-18 13:35:52,308 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-18 13:35:52,308 INFO L87 Difference]: Start difference. First operand 114 states and 162 transitions. Second operand has 7 states, 7 states have (on average 3.0) internal successors, (21), 6 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-18 13:35:52,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:52,472 INFO L93 Difference]: Finished difference Result 126 states and 172 transitions. [2024-11-18 13:35:52,472 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-18 13:35:52,472 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.0) internal successors, (21), 6 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 76 [2024-11-18 13:35:52,473 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:52,474 INFO L225 Difference]: With dead ends: 126 [2024-11-18 13:35:52,474 INFO L226 Difference]: Without dead ends: 124 [2024-11-18 13:35:52,474 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 72 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2024-11-18 13:35:52,475 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 12 mSDsluCounter, 173 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 216 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:52,475 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 216 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:35:52,476 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2024-11-18 13:35:52,514 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 122. [2024-11-18 13:35:52,515 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 67 states have (on average 1.1940298507462686) internal successors, (80), 69 states have internal predecessors, (80), 45 states have call successors, (45), 9 states have call predecessors, (45), 9 states have return successors, (43), 43 states have call predecessors, (43), 43 states have call successors, (43) [2024-11-18 13:35:52,516 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 168 transitions. [2024-11-18 13:35:52,517 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 168 transitions. Word has length 76 [2024-11-18 13:35:52,517 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:52,517 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 168 transitions. [2024-11-18 13:35:52,517 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.0) internal successors, (21), 6 states have internal predecessors, (21), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-18 13:35:52,517 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 168 transitions. [2024-11-18 13:35:52,521 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2024-11-18 13:35:52,521 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:52,521 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:52,538 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-18 13:35:52,721 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:35:52,722 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:52,722 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:52,722 INFO L85 PathProgramCache]: Analyzing trace with hash -421153901, now seen corresponding path program 3 times [2024-11-18 13:35:52,722 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:52,722 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1534716490] [2024-11-18 13:35:52,723 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:35:52,723 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:52,754 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-18 13:35:52,754 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:35:52,755 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1427336363] [2024-11-18 13:35:52,755 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:35:52,756 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:52,756 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:52,757 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:52,760 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-18 13:35:52,827 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-18 13:35:52,827 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:35:52,829 INFO L255 TraceCheckSpWp]: Trace formula consists of 142 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-11-18 13:35:52,831 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:53,835 INFO L134 CoverageAnalysis]: Checked inductivity of 165 backedges. 43 proven. 20 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2024-11-18 13:35:53,835 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:54,140 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:54,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1534716490] [2024-11-18 13:35:54,140 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:35:54,140 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1427336363] [2024-11-18 13:35:54,140 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1427336363] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:35:54,140 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:35:54,140 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-11-18 13:35:54,141 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [784428577] [2024-11-18 13:35:54,141 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-18 13:35:54,141 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-18 13:35:54,141 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:54,142 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-18 13:35:54,144 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=286, Unknown=0, NotChecked=0, Total=342 [2024-11-18 13:35:54,145 INFO L87 Difference]: Start difference. First operand 122 states and 168 transitions. Second operand has 16 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 14 states have internal predecessors, (27), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) [2024-11-18 13:35:54,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:54,684 INFO L93 Difference]: Finished difference Result 134 states and 178 transitions. [2024-11-18 13:35:54,685 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-18 13:35:54,685 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 14 states have internal predecessors, (27), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) Word has length 81 [2024-11-18 13:35:54,685 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:54,686 INFO L225 Difference]: With dead ends: 134 [2024-11-18 13:35:54,686 INFO L226 Difference]: Without dead ends: 132 [2024-11-18 13:35:54,687 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 68 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 76 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=79, Invalid=383, Unknown=0, NotChecked=0, Total=462 [2024-11-18 13:35:54,687 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 32 mSDsluCounter, 165 mSDsCounter, 0 mSdLazyCounter, 346 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 197 SdHoareTripleChecker+Invalid, 360 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 346 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:54,687 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 197 Invalid, 360 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 346 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-18 13:35:54,688 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2024-11-18 13:35:54,721 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 130. [2024-11-18 13:35:54,721 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 73 states have (on average 1.178082191780822) internal successors, (86), 75 states have internal predecessors, (86), 45 states have call successors, (45), 11 states have call predecessors, (45), 11 states have return successors, (43), 43 states have call predecessors, (43), 43 states have call successors, (43) [2024-11-18 13:35:54,722 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 174 transitions. [2024-11-18 13:35:54,723 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 174 transitions. Word has length 81 [2024-11-18 13:35:54,723 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:54,723 INFO L471 AbstractCegarLoop]: Abstraction has 130 states and 174 transitions. [2024-11-18 13:35:54,723 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 1.9285714285714286) internal successors, (27), 14 states have internal predecessors, (27), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) [2024-11-18 13:35:54,723 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 174 transitions. [2024-11-18 13:35:54,724 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-18 13:35:54,724 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:54,724 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:54,741 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-18 13:35:54,928 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:35:54,929 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:54,929 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:54,929 INFO L85 PathProgramCache]: Analyzing trace with hash -1712962370, now seen corresponding path program 1 times [2024-11-18 13:35:54,929 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:54,929 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [894326993] [2024-11-18 13:35:54,929 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:54,929 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:54,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:35:54,950 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1259877817] [2024-11-18 13:35:54,950 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:35:54,950 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:35:54,950 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:35:54,953 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:35:54,954 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-18 13:35:55,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:35:55,022 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-18 13:35:55,024 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:35:55,577 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 22 proven. 17 refuted. 0 times theorem prover too weak. 157 trivial. 0 not checked. [2024-11-18 13:35:55,577 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:35:56,429 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2024-11-18 13:35:56,429 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:56,430 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [894326993] [2024-11-18 13:35:56,430 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:35:56,430 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1259877817] [2024-11-18 13:35:56,430 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1259877817] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:35:56,430 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:35:56,430 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-11-18 13:35:56,430 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1187605788] [2024-11-18 13:35:56,431 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:35:56,431 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-18 13:35:56,431 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:56,432 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-18 13:35:56,432 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2024-11-18 13:35:56,432 INFO L87 Difference]: Start difference. First operand 130 states and 174 transitions. Second operand has 21 states, 19 states have (on average 1.9473684210526316) internal successors, (37), 18 states have internal predecessors, (37), 10 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-18 13:35:59,453 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:59,453 INFO L93 Difference]: Finished difference Result 230 states and 337 transitions. [2024-11-18 13:35:59,453 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-18 13:35:59,454 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 1.9473684210526316) internal successors, (37), 18 states have internal predecessors, (37), 10 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 87 [2024-11-18 13:35:59,454 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:59,456 INFO L225 Difference]: With dead ends: 230 [2024-11-18 13:35:59,456 INFO L226 Difference]: Without dead ends: 226 [2024-11-18 13:35:59,457 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 189 GetRequests, 153 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=255, Invalid=1151, Unknown=0, NotChecked=0, Total=1406 [2024-11-18 13:35:59,458 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 74 mSDsluCounter, 546 mSDsCounter, 0 mSdLazyCounter, 608 mSolverCounterSat, 108 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 592 SdHoareTripleChecker+Invalid, 716 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 108 IncrementalHoareTripleChecker+Valid, 608 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2024-11-18 13:35:59,458 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 592 Invalid, 716 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [108 Valid, 608 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2024-11-18 13:35:59,459 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 226 states. [2024-11-18 13:35:59,538 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 226 to 223. [2024-11-18 13:35:59,539 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 223 states, 115 states have (on average 1.2347826086956522) internal successors, (142), 118 states have internal predecessors, (142), 94 states have call successors, (94), 13 states have call predecessors, (94), 13 states have return successors, (92), 91 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-18 13:35:59,540 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 223 states to 223 states and 328 transitions. [2024-11-18 13:35:59,541 INFO L78 Accepts]: Start accepts. Automaton has 223 states and 328 transitions. Word has length 87 [2024-11-18 13:35:59,541 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:35:59,541 INFO L471 AbstractCegarLoop]: Abstraction has 223 states and 328 transitions. [2024-11-18 13:35:59,541 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 1.9473684210526316) internal successors, (37), 18 states have internal predecessors, (37), 10 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-18 13:35:59,542 INFO L276 IsEmpty]: Start isEmpty. Operand 223 states and 328 transitions. [2024-11-18 13:35:59,543 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2024-11-18 13:35:59,543 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:35:59,543 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 6, 6, 6, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:35:59,562 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:35:59,744 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:35:59,744 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:35:59,746 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:35:59,746 INFO L85 PathProgramCache]: Analyzing trace with hash 1006372811, now seen corresponding path program 4 times [2024-11-18 13:35:59,747 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:35:59,747 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1001993384] [2024-11-18 13:35:59,747 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:35:59,747 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:35:59,768 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:35:59,769 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:35:59,847 INFO L134 CoverageAnalysis]: Checked inductivity of 241 backedges. 37 proven. 0 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2024-11-18 13:35:59,847 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:35:59,847 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1001993384] [2024-11-18 13:35:59,847 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1001993384] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:35:59,847 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:35:59,848 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:35:59,848 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [594641816] [2024-11-18 13:35:59,848 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:35:59,848 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:35:59,848 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:35:59,849 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:35:59,849 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:35:59,849 INFO L87 Difference]: Start difference. First operand 223 states and 328 transitions. Second operand has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-11-18 13:35:59,973 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:35:59,974 INFO L93 Difference]: Finished difference Result 276 states and 404 transitions. [2024-11-18 13:35:59,974 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-18 13:35:59,974 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) Word has length 96 [2024-11-18 13:35:59,974 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:35:59,976 INFO L225 Difference]: With dead ends: 276 [2024-11-18 13:35:59,976 INFO L226 Difference]: Without dead ends: 202 [2024-11-18 13:35:59,977 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:35:59,977 INFO L432 NwaCegarLoop]: 50 mSDtfsCounter, 6 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 171 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:35:59,978 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 171 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:35:59,978 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 202 states. [2024-11-18 13:36:00,036 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 202 to 190. [2024-11-18 13:36:00,036 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 190 states, 98 states have (on average 1.1734693877551021) internal successors, (115), 101 states have internal predecessors, (115), 78 states have call successors, (78), 13 states have call predecessors, (78), 13 states have return successors, (76), 75 states have call predecessors, (76), 76 states have call successors, (76) [2024-11-18 13:36:00,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 269 transitions. [2024-11-18 13:36:00,040 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 269 transitions. Word has length 96 [2024-11-18 13:36:00,040 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:00,040 INFO L471 AbstractCegarLoop]: Abstraction has 190 states and 269 transitions. [2024-11-18 13:36:00,040 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-11-18 13:36:00,040 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 269 transitions. [2024-11-18 13:36:00,041 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2024-11-18 13:36:00,041 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:00,041 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:00,042 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11 [2024-11-18 13:36:00,042 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:00,042 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:00,042 INFO L85 PathProgramCache]: Analyzing trace with hash -1899970478, now seen corresponding path program 1 times [2024-11-18 13:36:00,042 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:00,042 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [30421629] [2024-11-18 13:36:00,042 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:00,042 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:00,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:00,275 INFO L134 CoverageAnalysis]: Checked inductivity of 320 backedges. 32 proven. 23 refuted. 0 times theorem prover too weak. 265 trivial. 0 not checked. [2024-11-18 13:36:00,276 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:00,276 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [30421629] [2024-11-18 13:36:00,276 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [30421629] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:00,276 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1289417594] [2024-11-18 13:36:00,276 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:00,276 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:00,276 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:00,278 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:00,279 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-18 13:36:00,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:00,343 INFO L255 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-18 13:36:00,345 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:00,424 INFO L134 CoverageAnalysis]: Checked inductivity of 320 backedges. 122 proven. 23 refuted. 0 times theorem prover too weak. 175 trivial. 0 not checked. [2024-11-18 13:36:00,424 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:00,589 INFO L134 CoverageAnalysis]: Checked inductivity of 320 backedges. 32 proven. 23 refuted. 0 times theorem prover too weak. 265 trivial. 0 not checked. [2024-11-18 13:36:00,589 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1289417594] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:00,589 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:36:00,589 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 13 [2024-11-18 13:36:00,589 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [90310676] [2024-11-18 13:36:00,589 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:00,590 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-18 13:36:00,590 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:00,591 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-18 13:36:00,591 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2024-11-18 13:36:00,592 INFO L87 Difference]: Start difference. First operand 190 states and 269 transitions. Second operand has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 13 states have internal predecessors, (35), 8 states have call successors, (28), 2 states have call predecessors, (28), 3 states have return successors, (28), 7 states have call predecessors, (28), 8 states have call successors, (28) [2024-11-18 13:36:00,897 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:00,898 INFO L93 Difference]: Finished difference Result 256 states and 363 transitions. [2024-11-18 13:36:00,898 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-18 13:36:00,898 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 13 states have internal predecessors, (35), 8 states have call successors, (28), 2 states have call predecessors, (28), 3 states have return successors, (28), 7 states have call predecessors, (28), 8 states have call successors, (28) Word has length 103 [2024-11-18 13:36:00,899 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:00,900 INFO L225 Difference]: With dead ends: 256 [2024-11-18 13:36:00,900 INFO L226 Difference]: Without dead ends: 169 [2024-11-18 13:36:00,901 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 223 GetRequests, 201 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=95, Invalid=325, Unknown=0, NotChecked=0, Total=420 [2024-11-18 13:36:00,901 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 47 mSDsluCounter, 251 mSDsCounter, 0 mSdLazyCounter, 159 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 291 SdHoareTripleChecker+Invalid, 196 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 159 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:00,902 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 291 Invalid, 196 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 159 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:36:00,902 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2024-11-18 13:36:00,956 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 169. [2024-11-18 13:36:00,956 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 169 states, 89 states have (on average 1.146067415730337) internal successors, (102), 92 states have internal predecessors, (102), 66 states have call successors, (66), 13 states have call predecessors, (66), 13 states have return successors, (64), 63 states have call predecessors, (64), 64 states have call successors, (64) [2024-11-18 13:36:00,958 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 232 transitions. [2024-11-18 13:36:00,958 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 232 transitions. Word has length 103 [2024-11-18 13:36:00,958 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:00,959 INFO L471 AbstractCegarLoop]: Abstraction has 169 states and 232 transitions. [2024-11-18 13:36:00,959 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.6923076923076925) internal successors, (35), 13 states have internal predecessors, (35), 8 states have call successors, (28), 2 states have call predecessors, (28), 3 states have return successors, (28), 7 states have call predecessors, (28), 8 states have call successors, (28) [2024-11-18 13:36:00,959 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 232 transitions. [2024-11-18 13:36:00,960 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2024-11-18 13:36:00,960 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:00,960 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:00,978 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:01,161 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:36:01,161 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:01,161 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:01,161 INFO L85 PathProgramCache]: Analyzing trace with hash 1451333771, now seen corresponding path program 1 times [2024-11-18 13:36:01,161 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:01,162 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [591348070] [2024-11-18 13:36:01,162 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:01,162 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:01,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:01,299 INFO L134 CoverageAnalysis]: Checked inductivity of 423 backedges. 42 proven. 9 refuted. 0 times theorem prover too weak. 372 trivial. 0 not checked. [2024-11-18 13:36:01,300 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:01,300 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [591348070] [2024-11-18 13:36:01,300 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [591348070] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:01,300 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1515229848] [2024-11-18 13:36:01,300 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:36:01,301 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:01,301 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:01,303 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:01,304 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-18 13:36:01,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:36:01,374 INFO L255 TraceCheckSpWp]: Trace formula consists of 274 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-18 13:36:01,376 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:01,405 INFO L134 CoverageAnalysis]: Checked inductivity of 423 backedges. 88 proven. 9 refuted. 0 times theorem prover too weak. 326 trivial. 0 not checked. [2024-11-18 13:36:01,405 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:01,500 INFO L134 CoverageAnalysis]: Checked inductivity of 423 backedges. 42 proven. 9 refuted. 0 times theorem prover too weak. 372 trivial. 0 not checked. [2024-11-18 13:36:01,500 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1515229848] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:01,500 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:36:01,501 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 7 [2024-11-18 13:36:01,501 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1948038320] [2024-11-18 13:36:01,501 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:01,501 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-18 13:36:01,501 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:01,502 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-18 13:36:01,502 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-11-18 13:36:01,502 INFO L87 Difference]: Start difference. First operand 169 states and 232 transitions. Second operand has 7 states, 7 states have (on average 4.142857142857143) internal successors, (29), 7 states have internal predecessors, (29), 4 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) [2024-11-18 13:36:01,719 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:01,719 INFO L93 Difference]: Finished difference Result 195 states and 271 transitions. [2024-11-18 13:36:01,720 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-18 13:36:01,720 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 4.142857142857143) internal successors, (29), 7 states have internal predecessors, (29), 4 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) Word has length 117 [2024-11-18 13:36:01,720 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:01,722 INFO L225 Difference]: With dead ends: 195 [2024-11-18 13:36:01,722 INFO L226 Difference]: Without dead ends: 183 [2024-11-18 13:36:01,722 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 250 GetRequests, 231 SyntacticMatches, 6 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=62, Invalid=148, Unknown=0, NotChecked=0, Total=210 [2024-11-18 13:36:01,722 INFO L432 NwaCegarLoop]: 69 mSDtfsCounter, 17 mSDsluCounter, 256 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 325 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:01,723 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 325 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:36:01,723 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2024-11-18 13:36:01,769 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 164. [2024-11-18 13:36:01,770 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 164 states, 86 states have (on average 1.1395348837209303) internal successors, (98), 88 states have internal predecessors, (98), 65 states have call successors, (65), 12 states have call predecessors, (65), 12 states have return successors, (63), 63 states have call predecessors, (63), 63 states have call successors, (63) [2024-11-18 13:36:01,770 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 164 states to 164 states and 226 transitions. [2024-11-18 13:36:01,771 INFO L78 Accepts]: Start accepts. Automaton has 164 states and 226 transitions. Word has length 117 [2024-11-18 13:36:01,771 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:01,771 INFO L471 AbstractCegarLoop]: Abstraction has 164 states and 226 transitions. [2024-11-18 13:36:01,771 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 4.142857142857143) internal successors, (29), 7 states have internal predecessors, (29), 4 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) [2024-11-18 13:36:01,772 INFO L276 IsEmpty]: Start isEmpty. Operand 164 states and 226 transitions. [2024-11-18 13:36:01,773 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2024-11-18 13:36:01,773 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:01,773 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 6, 6, 6, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:01,790 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-18 13:36:01,973 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:36:01,973 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:01,974 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:01,974 INFO L85 PathProgramCache]: Analyzing trace with hash -50105014, now seen corresponding path program 2 times [2024-11-18 13:36:01,974 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:01,974 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [682507557] [2024-11-18 13:36:01,974 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:36:01,974 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:01,997 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:36:01,997 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:02,220 INFO L134 CoverageAnalysis]: Checked inductivity of 432 backedges. 43 proven. 32 refuted. 0 times theorem prover too weak. 357 trivial. 0 not checked. [2024-11-18 13:36:02,220 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:02,220 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [682507557] [2024-11-18 13:36:02,220 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [682507557] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:02,220 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [814292655] [2024-11-18 13:36:02,220 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:36:02,221 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:02,221 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:02,223 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:02,224 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-18 13:36:02,298 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:36:02,298 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:02,299 INFO L255 TraceCheckSpWp]: Trace formula consists of 278 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-18 13:36:02,301 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:02,453 INFO L134 CoverageAnalysis]: Checked inductivity of 432 backedges. 103 proven. 18 refuted. 0 times theorem prover too weak. 311 trivial. 0 not checked. [2024-11-18 13:36:02,453 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:02,607 INFO L134 CoverageAnalysis]: Checked inductivity of 432 backedges. 43 proven. 32 refuted. 0 times theorem prover too weak. 357 trivial. 0 not checked. [2024-11-18 13:36:02,607 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [814292655] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:02,607 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:36:02,607 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 16 [2024-11-18 13:36:02,607 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [157728362] [2024-11-18 13:36:02,607 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:02,608 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-18 13:36:02,608 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:02,608 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-18 13:36:02,609 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2024-11-18 13:36:02,609 INFO L87 Difference]: Start difference. First operand 164 states and 226 transitions. Second operand has 16 states, 16 states have (on average 2.75) internal successors, (44), 14 states have internal predecessors, (44), 9 states have call successors, (31), 2 states have call predecessors, (31), 3 states have return successors, (31), 9 states have call predecessors, (31), 9 states have call successors, (31) [2024-11-18 13:36:02,921 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:02,922 INFO L93 Difference]: Finished difference Result 197 states and 273 transitions. [2024-11-18 13:36:02,922 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-18 13:36:02,923 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.75) internal successors, (44), 14 states have internal predecessors, (44), 9 states have call successors, (31), 2 states have call predecessors, (31), 3 states have return successors, (31), 9 states have call predecessors, (31), 9 states have call successors, (31) Word has length 118 [2024-11-18 13:36:02,923 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:02,924 INFO L225 Difference]: With dead ends: 197 [2024-11-18 13:36:02,924 INFO L226 Difference]: Without dead ends: 161 [2024-11-18 13:36:02,925 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 250 GetRequests, 225 SyntacticMatches, 5 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=97, Invalid=365, Unknown=0, NotChecked=0, Total=462 [2024-11-18 13:36:02,925 INFO L432 NwaCegarLoop]: 48 mSDtfsCounter, 17 mSDsluCounter, 442 mSDsCounter, 0 mSdLazyCounter, 270 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 490 SdHoareTripleChecker+Invalid, 288 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 270 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:02,926 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 490 Invalid, 288 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 270 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:36:02,926 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2024-11-18 13:36:02,976 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 161. [2024-11-18 13:36:02,977 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 161 states, 83 states have (on average 1.108433734939759) internal successors, (92), 85 states have internal predecessors, (92), 65 states have call successors, (65), 12 states have call predecessors, (65), 12 states have return successors, (63), 63 states have call predecessors, (63), 63 states have call successors, (63) [2024-11-18 13:36:02,978 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 161 states to 161 states and 220 transitions. [2024-11-18 13:36:02,978 INFO L78 Accepts]: Start accepts. Automaton has 161 states and 220 transitions. Word has length 118 [2024-11-18 13:36:02,979 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:02,979 INFO L471 AbstractCegarLoop]: Abstraction has 161 states and 220 transitions. [2024-11-18 13:36:02,979 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.75) internal successors, (44), 14 states have internal predecessors, (44), 9 states have call successors, (31), 2 states have call predecessors, (31), 3 states have return successors, (31), 9 states have call predecessors, (31), 9 states have call successors, (31) [2024-11-18 13:36:02,979 INFO L276 IsEmpty]: Start isEmpty. Operand 161 states and 220 transitions. [2024-11-18 13:36:02,980 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2024-11-18 13:36:02,981 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:02,981 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 6, 6, 6, 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, 1, 1, 1, 1, 1] [2024-11-18 13:36:02,998 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:03,181 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:36:03,182 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:03,182 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:03,182 INFO L85 PathProgramCache]: Analyzing trace with hash -1816082155, now seen corresponding path program 2 times [2024-11-18 13:36:03,182 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:03,182 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1517197197] [2024-11-18 13:36:03,182 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:36:03,182 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:03,205 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:36:03,205 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:36:03,208 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [514844656] [2024-11-18 13:36:03,208 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:36:03,208 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:03,208 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:03,210 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:03,211 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-18 13:36:03,299 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:36:03,299 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:03,301 INFO L255 TraceCheckSpWp]: Trace formula consists of 307 conjuncts, 58 conjuncts are in the unsatisfiable core [2024-11-18 13:36:03,304 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:04,190 INFO L134 CoverageAnalysis]: Checked inductivity of 615 backedges. 35 proven. 55 refuted. 0 times theorem prover too weak. 525 trivial. 0 not checked. [2024-11-18 13:36:04,190 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:06,007 INFO L134 CoverageAnalysis]: Checked inductivity of 615 backedges. 32 proven. 43 refuted. 0 times theorem prover too weak. 540 trivial. 0 not checked. [2024-11-18 13:36:06,007 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:06,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1517197197] [2024-11-18 13:36:06,007 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:06,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [514844656] [2024-11-18 13:36:06,007 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [514844656] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:06,007 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:36:06,008 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 13] total 26 [2024-11-18 13:36:06,008 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1599927732] [2024-11-18 13:36:06,008 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:06,008 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-11-18 13:36:06,008 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:06,009 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-11-18 13:36:06,009 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=528, Unknown=0, NotChecked=0, Total=650 [2024-11-18 13:36:06,009 INFO L87 Difference]: Start difference. First operand 161 states and 220 transitions. Second operand has 26 states, 24 states have (on average 2.0416666666666665) internal successors, (49), 24 states have internal predecessors, (49), 14 states have call successors, (44), 2 states have call predecessors, (44), 2 states have return successors, (43), 12 states have call predecessors, (43), 12 states have call successors, (43) [2024-11-18 13:36:08,965 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:08,966 INFO L93 Difference]: Finished difference Result 271 states and 385 transitions. [2024-11-18 13:36:08,966 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2024-11-18 13:36:08,966 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 24 states have (on average 2.0416666666666665) internal successors, (49), 24 states have internal predecessors, (49), 14 states have call successors, (44), 2 states have call predecessors, (44), 2 states have return successors, (43), 12 states have call predecessors, (43), 12 states have call successors, (43) Word has length 134 [2024-11-18 13:36:08,966 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:08,968 INFO L225 Difference]: With dead ends: 271 [2024-11-18 13:36:08,968 INFO L226 Difference]: Without dead ends: 238 [2024-11-18 13:36:08,969 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 294 GetRequests, 240 SyntacticMatches, 2 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 656 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=643, Invalid=2219, Unknown=0, NotChecked=0, Total=2862 [2024-11-18 13:36:08,970 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 91 mSDsluCounter, 637 mSDsCounter, 0 mSdLazyCounter, 688 mSolverCounterSat, 153 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 680 SdHoareTripleChecker+Invalid, 841 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 153 IncrementalHoareTripleChecker+Valid, 688 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:08,970 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [101 Valid, 680 Invalid, 841 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [153 Valid, 688 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2024-11-18 13:36:08,971 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 238 states. [2024-11-18 13:36:09,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 238 to 228. [2024-11-18 13:36:09,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 228 states, 118 states have (on average 1.1440677966101696) internal successors, (135), 121 states have internal predecessors, (135), 94 states have call successors, (94), 15 states have call predecessors, (94), 15 states have return successors, (92), 91 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-18 13:36:09,059 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 228 states to 228 states and 321 transitions. [2024-11-18 13:36:09,059 INFO L78 Accepts]: Start accepts. Automaton has 228 states and 321 transitions. Word has length 134 [2024-11-18 13:36:09,060 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:09,060 INFO L471 AbstractCegarLoop]: Abstraction has 228 states and 321 transitions. [2024-11-18 13:36:09,060 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 24 states have (on average 2.0416666666666665) internal successors, (49), 24 states have internal predecessors, (49), 14 states have call successors, (44), 2 states have call predecessors, (44), 2 states have return successors, (43), 12 states have call predecessors, (43), 12 states have call successors, (43) [2024-11-18 13:36:09,060 INFO L276 IsEmpty]: Start isEmpty. Operand 228 states and 321 transitions. [2024-11-18 13:36:09,061 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 140 [2024-11-18 13:36:09,061 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:09,061 INFO L215 NwaCegarLoop]: trace histogram [18, 17, 17, 6, 6, 6, 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, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:09,082 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:09,262 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:36:09,262 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:09,262 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:09,263 INFO L85 PathProgramCache]: Analyzing trace with hash -56106900, now seen corresponding path program 2 times [2024-11-18 13:36:09,263 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:09,263 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1041343079] [2024-11-18 13:36:09,263 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:36:09,263 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:09,291 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:36:09,291 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:36:09,294 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1487653635] [2024-11-18 13:36:09,294 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:36:09,294 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:09,294 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:09,296 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:09,298 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-18 13:36:09,385 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:36:09,385 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:09,387 INFO L255 TraceCheckSpWp]: Trace formula consists of 316 conjuncts, 56 conjuncts are in the unsatisfiable core [2024-11-18 13:36:09,390 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:09,952 INFO L134 CoverageAnalysis]: Checked inductivity of 681 backedges. 84 proven. 56 refuted. 0 times theorem prover too weak. 541 trivial. 0 not checked. [2024-11-18 13:36:09,952 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:10,265 INFO L134 CoverageAnalysis]: Checked inductivity of 681 backedges. 86 proven. 7 refuted. 0 times theorem prover too weak. 588 trivial. 0 not checked. [2024-11-18 13:36:10,265 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:10,265 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1041343079] [2024-11-18 13:36:10,265 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:36:10,266 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1487653635] [2024-11-18 13:36:10,266 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1487653635] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:10,266 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:36:10,266 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 9] total 25 [2024-11-18 13:36:10,266 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1699870130] [2024-11-18 13:36:10,266 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:10,266 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-18 13:36:10,266 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:10,267 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-18 13:36:10,267 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=515, Unknown=0, NotChecked=0, Total=600 [2024-11-18 13:36:10,268 INFO L87 Difference]: Start difference. First operand 228 states and 321 transitions. Second operand has 25 states, 23 states have (on average 2.1739130434782608) internal successors, (50), 22 states have internal predecessors, (50), 9 states have call successors, (33), 3 states have call predecessors, (33), 3 states have return successors, (33), 10 states have call predecessors, (33), 9 states have call successors, (33) [2024-11-18 13:36:12,187 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:12,187 INFO L93 Difference]: Finished difference Result 244 states and 335 transitions. [2024-11-18 13:36:12,188 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-18 13:36:12,188 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 23 states have (on average 2.1739130434782608) internal successors, (50), 22 states have internal predecessors, (50), 9 states have call successors, (33), 3 states have call predecessors, (33), 3 states have return successors, (33), 10 states have call predecessors, (33), 9 states have call successors, (33) Word has length 139 [2024-11-18 13:36:12,188 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:12,190 INFO L225 Difference]: With dead ends: 244 [2024-11-18 13:36:12,190 INFO L226 Difference]: Without dead ends: 231 [2024-11-18 13:36:12,191 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 292 GetRequests, 254 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 283 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=260, Invalid=1300, Unknown=0, NotChecked=0, Total=1560 [2024-11-18 13:36:12,192 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 56 mSDsluCounter, 450 mSDsCounter, 0 mSdLazyCounter, 666 mSolverCounterSat, 78 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 488 SdHoareTripleChecker+Invalid, 744 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 78 IncrementalHoareTripleChecker+Valid, 666 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:12,192 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 488 Invalid, 744 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [78 Valid, 666 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-18 13:36:12,193 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 231 states. [2024-11-18 13:36:12,282 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 231 to 230. [2024-11-18 13:36:12,283 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 230 states, 121 states have (on average 1.115702479338843) internal successors, (135), 122 states have internal predecessors, (135), 91 states have call successors, (91), 17 states have call predecessors, (91), 17 states have return successors, (90), 90 states have call predecessors, (90), 90 states have call successors, (90) [2024-11-18 13:36:12,285 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 230 states to 230 states and 316 transitions. [2024-11-18 13:36:12,285 INFO L78 Accepts]: Start accepts. Automaton has 230 states and 316 transitions. Word has length 139 [2024-11-18 13:36:12,285 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:12,285 INFO L471 AbstractCegarLoop]: Abstraction has 230 states and 316 transitions. [2024-11-18 13:36:12,286 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 23 states have (on average 2.1739130434782608) internal successors, (50), 22 states have internal predecessors, (50), 9 states have call successors, (33), 3 states have call predecessors, (33), 3 states have return successors, (33), 10 states have call predecessors, (33), 9 states have call successors, (33) [2024-11-18 13:36:12,286 INFO L276 IsEmpty]: Start isEmpty. Operand 230 states and 316 transitions. [2024-11-18 13:36:12,287 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 143 [2024-11-18 13:36:12,287 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:12,287 INFO L215 NwaCegarLoop]: trace histogram [19, 18, 18, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:12,304 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2024-11-18 13:36:12,488 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:36:12,488 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:12,488 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:12,488 INFO L85 PathProgramCache]: Analyzing trace with hash -645167759, now seen corresponding path program 3 times [2024-11-18 13:36:12,489 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:12,489 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [953320951] [2024-11-18 13:36:12,489 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:36:12,489 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:12,522 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2024-11-18 13:36:12,522 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:12,753 INFO L134 CoverageAnalysis]: Checked inductivity of 762 backedges. 54 proven. 51 refuted. 0 times theorem prover too weak. 657 trivial. 0 not checked. [2024-11-18 13:36:12,753 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:12,753 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [953320951] [2024-11-18 13:36:12,753 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [953320951] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:12,753 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1382795534] [2024-11-18 13:36:12,754 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:36:12,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:12,754 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:12,755 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:12,758 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-18 13:36:12,830 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-18 13:36:12,830 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:12,832 INFO L255 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-11-18 13:36:12,835 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:13,428 INFO L134 CoverageAnalysis]: Checked inductivity of 762 backedges. 86 proven. 52 refuted. 0 times theorem prover too weak. 624 trivial. 0 not checked. [2024-11-18 13:36:13,428 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:18,114 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1382795534] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:18,114 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:36:18,115 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 14] total 20 [2024-11-18 13:36:18,115 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1980632455] [2024-11-18 13:36:18,115 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:18,115 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-18 13:36:18,115 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:18,116 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-18 13:36:18,116 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=617, Unknown=1, NotChecked=0, Total=702 [2024-11-18 13:36:18,116 INFO L87 Difference]: Start difference. First operand 230 states and 316 transitions. Second operand has 20 states, 20 states have (on average 2.4) internal successors, (48), 17 states have internal predecessors, (48), 12 states have call successors, (41), 3 states have call predecessors, (41), 3 states have return successors, (40), 12 states have call predecessors, (40), 12 states have call successors, (40) [2024-11-18 13:36:18,596 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:18,596 INFO L93 Difference]: Finished difference Result 282 states and 375 transitions. [2024-11-18 13:36:18,596 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-18 13:36:18,597 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 2.4) internal successors, (48), 17 states have internal predecessors, (48), 12 states have call successors, (41), 3 states have call predecessors, (41), 3 states have return successors, (40), 12 states have call predecessors, (40), 12 states have call successors, (40) Word has length 142 [2024-11-18 13:36:18,597 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:18,598 INFO L225 Difference]: With dead ends: 282 [2024-11-18 13:36:18,599 INFO L226 Difference]: Without dead ends: 170 [2024-11-18 13:36:18,606 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 201 GetRequests, 169 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 145 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=168, Invalid=953, Unknown=1, NotChecked=0, Total=1122 [2024-11-18 13:36:18,607 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 33 mSDsluCounter, 392 mSDsCounter, 0 mSdLazyCounter, 443 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 425 SdHoareTripleChecker+Invalid, 482 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 443 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:18,607 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 425 Invalid, 482 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 443 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:36:18,608 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 170 states. [2024-11-18 13:36:18,672 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 170 to 170. [2024-11-18 13:36:18,673 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 170 states, 92 states have (on average 1.0978260869565217) internal successors, (101), 93 states have internal predecessors, (101), 63 states have call successors, (63), 14 states have call predecessors, (63), 14 states have return successors, (62), 62 states have call predecessors, (62), 62 states have call successors, (62) [2024-11-18 13:36:18,674 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 226 transitions. [2024-11-18 13:36:18,674 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 226 transitions. Word has length 142 [2024-11-18 13:36:18,674 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:18,674 INFO L471 AbstractCegarLoop]: Abstraction has 170 states and 226 transitions. [2024-11-18 13:36:18,675 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 2.4) internal successors, (48), 17 states have internal predecessors, (48), 12 states have call successors, (41), 3 states have call predecessors, (41), 3 states have return successors, (40), 12 states have call predecessors, (40), 12 states have call successors, (40) [2024-11-18 13:36:18,675 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 226 transitions. [2024-11-18 13:36:18,676 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 168 [2024-11-18 13:36:18,676 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:36:18,677 INFO L215 NwaCegarLoop]: trace histogram [23, 22, 22, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:18,693 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:18,880 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:36:18,881 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:36:18,881 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:36:18,881 INFO L85 PathProgramCache]: Analyzing trace with hash 997653913, now seen corresponding path program 4 times [2024-11-18 13:36:18,881 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:36:18,881 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [466862464] [2024-11-18 13:36:18,881 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:36:18,881 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:36:18,909 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:36:18,913 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:19,209 INFO L134 CoverageAnalysis]: Checked inductivity of 1115 backedges. 72 proven. 74 refuted. 0 times theorem prover too weak. 969 trivial. 0 not checked. [2024-11-18 13:36:19,209 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:36:19,209 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [466862464] [2024-11-18 13:36:19,210 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [466862464] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:36:19,210 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [688299093] [2024-11-18 13:36:19,210 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-18 13:36:19,210 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:36:19,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:36:19,212 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:36:19,213 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-18 13:36:19,298 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-18 13:36:19,298 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:36:19,300 INFO L255 TraceCheckSpWp]: Trace formula consists of 340 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-18 13:36:19,303 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:36:19,428 INFO L134 CoverageAnalysis]: Checked inductivity of 1115 backedges. 234 proven. 68 refuted. 0 times theorem prover too weak. 813 trivial. 0 not checked. [2024-11-18 13:36:19,429 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:36:19,631 INFO L134 CoverageAnalysis]: Checked inductivity of 1115 backedges. 72 proven. 74 refuted. 0 times theorem prover too weak. 969 trivial. 0 not checked. [2024-11-18 13:36:19,631 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [688299093] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:36:19,631 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:36:19,631 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 22 [2024-11-18 13:36:19,632 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [32043021] [2024-11-18 13:36:19,632 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:36:19,632 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-18 13:36:19,632 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:36:19,633 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-18 13:36:19,633 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=390, Unknown=0, NotChecked=0, Total=462 [2024-11-18 13:36:19,633 INFO L87 Difference]: Start difference. First operand 170 states and 226 transitions. Second operand has 22 states, 22 states have (on average 2.8636363636363638) internal successors, (63), 20 states have internal predecessors, (63), 17 states have call successors, (67), 2 states have call predecessors, (67), 3 states have return successors, (67), 17 states have call predecessors, (67), 17 states have call successors, (67) [2024-11-18 13:36:19,970 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:36:19,970 INFO L93 Difference]: Finished difference Result 174 states and 229 transitions. [2024-11-18 13:36:19,971 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-18 13:36:19,971 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.8636363636363638) internal successors, (63), 20 states have internal predecessors, (63), 17 states have call successors, (67), 2 states have call predecessors, (67), 3 states have return successors, (67), 17 states have call predecessors, (67), 17 states have call successors, (67) Word has length 167 [2024-11-18 13:36:19,982 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:36:19,983 INFO L225 Difference]: With dead ends: 174 [2024-11-18 13:36:19,983 INFO L226 Difference]: Without dead ends: 0 [2024-11-18 13:36:19,984 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 349 GetRequests, 320 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 171 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=140, Invalid=616, Unknown=0, NotChecked=0, Total=756 [2024-11-18 13:36:19,984 INFO L432 NwaCegarLoop]: 61 mSDtfsCounter, 16 mSDsluCounter, 653 mSDsCounter, 0 mSdLazyCounter, 408 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 714 SdHoareTripleChecker+Invalid, 432 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 408 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:36:19,984 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 714 Invalid, 432 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 408 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:36:19,985 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-18 13:36:19,985 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-18 13:36:19,985 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-18 13:36:19,985 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-18 13:36:19,985 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 167 [2024-11-18 13:36:19,985 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:36:19,985 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-18 13:36:19,986 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.8636363636363638) internal successors, (63), 20 states have internal predecessors, (63), 17 states have call successors, (67), 2 states have call predecessors, (67), 3 states have return successors, (67), 17 states have call predecessors, (67), 17 states have call successors, (67) [2024-11-18 13:36:19,986 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-18 13:36:19,986 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-18 13:36:19,990 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-18 13:36:20,004 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2024-11-18 13:36:20,190 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:36:20,193 INFO L407 BasicCegarLoop]: Path program histogram: [4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:36:20,195 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-11-18 13:36:24,051 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-18 13:36:24,080 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.11 01:36:24 BoogieIcfgContainer [2024-11-18 13:36:24,080 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-18 13:36:24,081 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-18 13:36:24,081 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-18 13:36:24,081 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-18 13:36:24,081 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:35:46" (3/4) ... [2024-11-18 13:36:24,085 INFO L142 WitnessPrinter]: Generating witness for correct program [2024-11-18 13:36:24,089 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure assume_abort_if_not [2024-11-18 13:36:24,090 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-11-18 13:36:24,093 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 13 nodes and edges [2024-11-18 13:36:24,094 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2024-11-18 13:36:24,094 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-11-18 13:36:24,095 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-18 13:36:24,183 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-18 13:36:24,183 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.yml [2024-11-18 13:36:24,183 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-18 13:36:24,184 INFO L158 Benchmark]: Toolchain (without parser) took 38781.38ms. Allocated memory was 136.3MB in the beginning and 245.4MB in the end (delta: 109.1MB). Free memory was 82.7MB in the beginning and 131.5MB in the end (delta: -48.8MB). Peak memory consumption was 60.6MB. Max. memory is 16.1GB. [2024-11-18 13:36:24,184 INFO L158 Benchmark]: CDTParser took 0.18ms. Allocated memory is still 136.3MB. Free memory is still 70.5MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-18 13:36:24,184 INFO L158 Benchmark]: CACSL2BoogieTranslator took 265.16ms. Allocated memory is still 136.3MB. Free memory was 82.3MB in the beginning and 69.6MB in the end (delta: 12.7MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-18 13:36:24,185 INFO L158 Benchmark]: Boogie Procedure Inliner took 29.77ms. Allocated memory is still 136.3MB. Free memory was 69.6MB in the beginning and 67.6MB in the end (delta: 2.0MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-18 13:36:24,185 INFO L158 Benchmark]: Boogie Preprocessor took 33.56ms. Allocated memory is still 136.3MB. Free memory was 67.6MB in the beginning and 65.9MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-18 13:36:24,185 INFO L158 Benchmark]: RCFGBuilder took 428.16ms. Allocated memory was 136.3MB in the beginning and 203.4MB in the end (delta: 67.1MB). Free memory was 65.9MB in the beginning and 169.1MB in the end (delta: -103.2MB). Peak memory consumption was 11.5MB. Max. memory is 16.1GB. [2024-11-18 13:36:24,185 INFO L158 Benchmark]: TraceAbstraction took 37911.75ms. Allocated memory was 203.4MB in the beginning and 245.4MB in the end (delta: 41.9MB). Free memory was 168.1MB in the beginning and 136.7MB in the end (delta: 31.4MB). Peak memory consumption was 145.9MB. Max. memory is 16.1GB. [2024-11-18 13:36:24,186 INFO L158 Benchmark]: Witness Printer took 102.63ms. Allocated memory is still 245.4MB. Free memory was 135.7MB in the beginning and 131.5MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-11-18 13:36:24,187 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.18ms. Allocated memory is still 136.3MB. Free memory is still 70.5MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 265.16ms. Allocated memory is still 136.3MB. Free memory was 82.3MB in the beginning and 69.6MB in the end (delta: 12.7MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 29.77ms. Allocated memory is still 136.3MB. Free memory was 69.6MB in the beginning and 67.6MB in the end (delta: 2.0MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 33.56ms. Allocated memory is still 136.3MB. Free memory was 67.6MB in the beginning and 65.9MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 428.16ms. Allocated memory was 136.3MB in the beginning and 203.4MB in the end (delta: 67.1MB). Free memory was 65.9MB in the beginning and 169.1MB in the end (delta: -103.2MB). Peak memory consumption was 11.5MB. Max. memory is 16.1GB. * TraceAbstraction took 37911.75ms. Allocated memory was 203.4MB in the beginning and 245.4MB in the end (delta: 41.9MB). Free memory was 168.1MB in the beginning and 136.7MB in the end (delta: 31.4MB). Peak memory consumption was 145.9MB. Max. memory is 16.1GB. * Witness Printer took 102.63ms. Allocated memory is still 245.4MB. Free memory was 135.7MB in the beginning and 131.5MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 13]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 35 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 34.0s, OverallIterations: 19, TraceHistogramMax: 23, PathProgramHistogramMax: 4, EmptinessCheckTime: 0.0s, AutomataDifference: 11.4s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 580 SdHoareTripleChecker+Valid, 6.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 498 mSDsluCounter, 5906 SdHoareTripleChecker+Invalid, 5.6s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 5082 mSDsCounter, 570 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 4399 IncrementalHoareTripleChecker+Invalid, 4969 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 570 mSolverCounterUnsat, 824 mSDtfsCounter, 4399 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 2808 GetRequests, 2451 SyntacticMatches, 30 SemanticMatches, 327 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1731 ImplicationChecksByTransitivity, 12.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=230occurred in iteration=17, InterpolantAutomatonStates: 231, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.8s AutomataMinimizationTime, 19 MinimizatonAttempts, 103 StatesRemovedByMinimization, 14 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.2s SsaConstructionTime, 0.9s SatisfiabilityAnalysisTime, 16.0s InterpolantComputationTime, 3266 NumberOfCodeBlocks, 3147 NumberOfCodeBlocksAsserted, 63 NumberOfCheckSat, 3429 ConstructedInterpolants, 0 QuantifiedInterpolants, 11679 SizeOfPredicates, 51 NumberOfNonLiveVariables, 3599 ConjunctsInSsa, 406 ConjunctsInUnsatCore, 36 InterpolantComputations, 4 PerfectInterpolantSequences, 12164/12947 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 47]: Loop Invariant Derived loop invariant: (((((((((((((((((((yy == ((long long) y * y)) && (p == 1)) && (1 <= y)) && (a == c)) && (b == y)) && (b <= 2)) && (r == 0)) && (q == 0)) && (k == 0)) && (1 <= x)) && (xy == ((long long) x * y))) && (a == x)) && (x <= 2)) && (s == 1)) || ((((((((((((b == 1) && (2 == xy)) && (p == 0)) && (2 == y)) && (x == 1)) && (q == 1)) && (k == 0)) && (s == 0)) && (r == 1)) && (2 == a)) && (yy == 4)) && (2 == c))) || (((((((((((((k == 1) && (yy == ((long long) y * y))) && (p == 1)) && (1 <= y)) && (b == y)) && (0 <= c)) && (r == 0)) && (q == 0)) && (xy == ((long long) x * y))) && (a == x)) && (x <= 2)) && (s == 1)) && (((__int128) b + c) == x))) || ((((((((((((c == 0) && (b == 1)) && (2 == xy)) && (p == 0)) && (2 == y)) && (x == 1)) && (q == 1)) && (s == 0)) && (r == 1)) && (2 == a)) && (yy == 4)) && (2 == k))) || (((((((((((((c == 0) && (a == (c + ((__int128) b * k)))) && (yy == ((long long) y * y))) && (p == 1)) && (1 <= y)) && (b == y)) && (r == 0)) && (q == 0)) && (1 <= x)) && (xy == ((long long) x * y))) && (a == x)) && (x <= 2)) && (s == 1))) || ((((((((((((k == 1) && (b == 1)) && (2 == xy)) && (p == 0)) && (c == 1)) && (2 == y)) && (x == 1)) && (q == 1)) && (s == 0)) && (r == 1)) && (2 == a)) && (yy == 4))) - InvariantResult [Line: 41]: Loop Invariant Derived loop invariant: (((((((((((((b == 1) && (yy == ((long long) y * y))) && (p == 0)) && (2 == y)) && (x == 1)) && (q == 1)) && (s == 0)) && (r == 1)) && (2 == a)) && (xy == y)) || ((((((((((((yy == ((long long) y * y)) && (p == 1)) && (1 <= y)) && (b == y)) && (b <= 2)) && (r == 0)) && (q == 0)) && (1 <= x)) && (xy == ((long long) x * y))) && (a == x)) && (x <= 2)) && (s == 1))) || (((((((((((long long) x + 1) <= y) && (p == 1)) && (y <= 2)) && (((__int128) b + 1) <= x)) && (r == 0)) && (((__int128) 2 + q) == 0)) && (a == x)) && (y == ((__int128) ((long long) 2 * x) + b))) && (s == 1))) || (((((((((p == 0) && (y <= 2)) && (a == y)) && (b == 0)) && (1 <= a)) && (1 <= x)) && (r == 1)) && (x <= 2)) && ((((__int128) s * y) + ((__int128) q * x)) == 0))) - ProcedureContractResult [Line: 7]: Procedure Contract for assume_abort_if_not Derived contract for procedure assume_abort_if_not. Ensures: (cond != 0) - ProcedureContractResult [Line: 10]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert. Requires: (1 <= cond) Ensures: (1 <= cond) RESULT: Ultimate proved your program to be correct! [2024-11-18 13:36:24,225 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE