./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version a046e57d Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.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 ac7d6bbeae1af74610eb5ea0ec9cc56676532539c7535ebfdf72e0c17174815d --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-mul-div-a046e57-m [2024-10-12 18:52:35,658 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-12 18:52:35,722 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-12 18:52:35,727 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-12 18:52:35,728 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-12 18:52:35,760 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-12 18:52:35,761 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-12 18:52:35,761 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-12 18:52:35,762 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-12 18:52:35,762 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-12 18:52:35,763 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-12 18:52:35,763 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-12 18:52:35,764 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-12 18:52:35,768 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-12 18:52:35,768 INFO L153 SettingsManager]: * Use SBE=true [2024-10-12 18:52:35,768 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-12 18:52:35,769 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-12 18:52:35,769 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-12 18:52:35,769 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-12 18:52:35,769 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-12 18:52:35,769 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-12 18:52:35,772 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-12 18:52:35,772 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-12 18:52:35,773 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-12 18:52:35,773 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-12 18:52:35,773 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-12 18:52:35,773 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-12 18:52:35,774 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-12 18:52:35,774 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-12 18:52:35,774 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-12 18:52:35,774 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-12 18:52:35,775 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-12 18:52:35,775 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-12 18:52:35,775 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-12 18:52:35,775 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-12 18:52:35,776 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-12 18:52:35,776 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-12 18:52:35,776 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-12 18:52:35,777 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-12 18:52:35,778 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-12 18:52:35,778 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-12 18:52:35,778 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-12 18:52:35,778 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 -> ac7d6bbeae1af74610eb5ea0ec9cc56676532539c7535ebfdf72e0c17174815d [2024-10-12 18:52:36,080 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-12 18:52:36,104 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-12 18:52:36,108 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-12 18:52:36,109 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-12 18:52:36,110 INFO L274 PluginConnector]: CDTParser initialized [2024-10-12 18:52:36,111 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c [2024-10-12 18:52:37,465 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-12 18:52:37,690 INFO L384 CDTParser]: Found 1 translation units. [2024-10-12 18:52:37,691 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c [2024-10-12 18:52:37,703 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/04c5e9d2c/c0fa7f8e332643ec86d3899fdd9a1e16/FLAG798e569f9 [2024-10-12 18:52:37,717 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/04c5e9d2c/c0fa7f8e332643ec86d3899fdd9a1e16 [2024-10-12 18:52:37,720 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-12 18:52:37,721 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-12 18:52:37,723 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-12 18:52:37,724 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-12 18:52:37,729 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-12 18:52:37,730 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.10 06:52:37" (1/1) ... [2024-10-12 18:52:37,731 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6563dc26 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:37, skipping insertion in model container [2024-10-12 18:52:37,731 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.10 06:52:37" (1/1) ... [2024-10-12 18:52:37,752 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-12 18:52:37,931 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c[535,548] [2024-10-12 18:52:37,961 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-12 18:52:37,972 INFO L200 MainTranslator]: Completed pre-run [2024-10-12 18:52:37,985 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/fermat1-ll_unwindbound100.c[535,548] [2024-10-12 18:52:37,995 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-12 18:52:38,012 INFO L204 MainTranslator]: Completed translation [2024-10-12 18:52:38,016 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38 WrapperNode [2024-10-12 18:52:38,016 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-12 18:52:38,017 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-12 18:52:38,018 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-12 18:52:38,018 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-12 18:52:38,025 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38" (1/1) ... [2024-10-12 18:52:38,036 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38" (1/1) ... [2024-10-12 18:52:38,062 INFO L138 Inliner]: procedures = 14, calls = 13, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 68 [2024-10-12 18:52:38,063 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-12 18:52:38,063 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-12 18:52:38,063 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-12 18:52:38,064 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-12 18:52:38,074 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38" (1/1) ... [2024-10-12 18:52:38,074 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38" (1/1) ... [2024-10-12 18:52:38,076 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38" (1/1) ... [2024-10-12 18:52:38,091 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-10-12 18:52:38,091 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38" (1/1) ... [2024-10-12 18:52:38,095 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38" (1/1) ... [2024-10-12 18:52:38,098 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38" (1/1) ... [2024-10-12 18:52:38,105 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38" (1/1) ... [2024-10-12 18:52:38,107 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38" (1/1) ... [2024-10-12 18:52:38,112 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38" (1/1) ... [2024-10-12 18:52:38,114 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-12 18:52:38,115 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-12 18:52:38,115 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-12 18:52:38,115 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-12 18:52:38,117 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38" (1/1) ... [2024-10-12 18:52:38,121 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-12 18:52:38,132 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:38,147 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-10-12 18:52:38,152 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-10-12 18:52:38,187 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-12 18:52:38,187 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-10-12 18:52:38,187 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-10-12 18:52:38,187 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-12 18:52:38,187 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-12 18:52:38,188 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-12 18:52:38,188 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-12 18:52:38,188 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-12 18:52:38,244 INFO L238 CfgBuilder]: Building ICFG [2024-10-12 18:52:38,246 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-12 18:52:38,419 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-10-12 18:52:38,420 INFO L287 CfgBuilder]: Performing block encoding [2024-10-12 18:52:38,447 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-12 18:52:38,447 INFO L314 CfgBuilder]: Removed 3 assume(true) statements. [2024-10-12 18:52:38,448 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 06:52:38 BoogieIcfgContainer [2024-10-12 18:52:38,448 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-12 18:52:38,450 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-12 18:52:38,450 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-12 18:52:38,453 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-12 18:52:38,454 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.10 06:52:37" (1/3) ... [2024-10-12 18:52:38,454 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2f909e0a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.10 06:52:38, skipping insertion in model container [2024-10-12 18:52:38,454 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 06:52:38" (2/3) ... [2024-10-12 18:52:38,455 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2f909e0a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.10 06:52:38, skipping insertion in model container [2024-10-12 18:52:38,455 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 06:52:38" (3/3) ... [2024-10-12 18:52:38,456 INFO L112 eAbstractionObserver]: Analyzing ICFG fermat1-ll_unwindbound100.c [2024-10-12 18:52:38,473 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-12 18:52:38,473 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-12 18:52:38,541 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-12 18:52:38,552 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;@1248da2a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-12 18:52:38,553 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-12 18:52:38,557 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 19 states have (on average 1.631578947368421) internal successors, (31), 20 states have internal predecessors, (31), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-12 18:52:38,563 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-10-12 18:52:38,563 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:38,563 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:38,564 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:38,568 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:38,568 INFO L85 PathProgramCache]: Analyzing trace with hash -1287337846, now seen corresponding path program 1 times [2024-10-12 18:52:38,576 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:38,577 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [668405239] [2024-10-12 18:52:38,578 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:38,579 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:38,688 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:38,744 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:38,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:38,754 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:38,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:38,777 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 18:52:38,777 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:38,778 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [668405239] [2024-10-12 18:52:38,779 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [668405239] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:52:38,779 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:52:38,779 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-12 18:52:38,781 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [349345697] [2024-10-12 18:52:38,782 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:52:38,787 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-12 18:52:38,788 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:38,806 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-12 18:52:38,807 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-12 18:52:38,809 INFO L87 Difference]: Start difference. First operand has 29 states, 19 states have (on average 1.631578947368421) internal successors, (31), 20 states have internal predecessors, (31), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-12 18:52:38,830 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:38,830 INFO L93 Difference]: Finished difference Result 56 states and 89 transitions. [2024-10-12 18:52:38,831 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-12 18:52:38,832 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2024-10-12 18:52:38,833 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:38,837 INFO L225 Difference]: With dead ends: 56 [2024-10-12 18:52:38,837 INFO L226 Difference]: Without dead ends: 27 [2024-10-12 18:52:38,840 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-12 18:52:38,843 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 36 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:38,843 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 36 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:52:38,855 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2024-10-12 18:52:38,874 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2024-10-12 18:52:38,876 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 18 states have (on average 1.3888888888888888) internal successors, (25), 19 states have internal predecessors, (25), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-10-12 18:52:38,877 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 36 transitions. [2024-10-12 18:52:38,879 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 36 transitions. Word has length 17 [2024-10-12 18:52:38,880 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:38,881 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 36 transitions. [2024-10-12 18:52:38,881 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-12 18:52:38,881 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 36 transitions. [2024-10-12 18:52:38,882 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-10-12 18:52:38,882 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:38,882 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:38,883 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-12 18:52:38,883 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:38,883 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:38,883 INFO L85 PathProgramCache]: Analyzing trace with hash -138178001, now seen corresponding path program 1 times [2024-10-12 18:52:38,884 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:38,884 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1617763488] [2024-10-12 18:52:38,884 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:38,885 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:38,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:39,035 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:39,042 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:39,056 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:39,061 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:39,079 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 18:52:39,080 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:39,080 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1617763488] [2024-10-12 18:52:39,080 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1617763488] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:52:39,080 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:52:39,080 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-10-12 18:52:39,082 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [85468291] [2024-10-12 18:52:39,083 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:52:39,084 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-12 18:52:39,084 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:39,085 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-12 18:52:39,085 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-12 18:52:39,086 INFO L87 Difference]: Start difference. First operand 27 states and 36 transitions. Second operand has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-12 18:52:39,131 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:39,131 INFO L93 Difference]: Finished difference Result 36 states and 45 transitions. [2024-10-12 18:52:39,134 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-12 18:52:39,134 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2024-10-12 18:52:39,135 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:39,136 INFO L225 Difference]: With dead ends: 36 [2024-10-12 18:52:39,136 INFO L226 Difference]: Without dead ends: 29 [2024-10-12 18:52:39,137 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-12 18:52:39,138 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 5 mSDsluCounter, 55 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 88 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:39,140 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 88 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:52:39,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2024-10-12 18:52:39,147 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2024-10-12 18:52:39,148 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 20 states have (on average 1.35) internal successors, (27), 21 states have internal predecessors, (27), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-10-12 18:52:39,149 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 38 transitions. [2024-10-12 18:52:39,149 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 38 transitions. Word has length 18 [2024-10-12 18:52:39,150 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:39,151 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 38 transitions. [2024-10-12 18:52:39,151 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-12 18:52:39,151 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 38 transitions. [2024-10-12 18:52:39,152 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-10-12 18:52:39,152 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:39,152 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:39,153 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-12 18:52:39,153 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:39,154 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:39,154 INFO L85 PathProgramCache]: Analyzing trace with hash -136509705, now seen corresponding path program 1 times [2024-10-12 18:52:39,154 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:39,154 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1253024160] [2024-10-12 18:52:39,154 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:39,155 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:39,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 18:52:39,212 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [600970328] [2024-10-12 18:52:39,212 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:39,212 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:39,213 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:39,215 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:39,217 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-10-12 18:52:39,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:39,290 INFO L255 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-12 18:52:39,297 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:39,561 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 18:52:39,561 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-12 18:52:39,562 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:39,562 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1253024160] [2024-10-12 18:52:39,562 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 18:52:39,565 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [600970328] [2024-10-12 18:52:39,565 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [600970328] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:52:39,566 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:52:39,566 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-12 18:52:39,566 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1012582873] [2024-10-12 18:52:39,566 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:52:39,567 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 18:52:39,567 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:39,567 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 18:52:39,567 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-12 18:52:39,568 INFO L87 Difference]: Start difference. First operand 29 states and 38 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-12 18:52:40,829 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.01s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-12 18:52:42,069 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.19s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-12 18:52:42,090 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:42,091 INFO L93 Difference]: Finished difference Result 48 states and 65 transitions. [2024-10-12 18:52:42,091 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-12 18:52:42,091 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2024-10-12 18:52:42,091 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:42,092 INFO L225 Difference]: With dead ends: 48 [2024-10-12 18:52:42,092 INFO L226 Difference]: Without dead ends: 46 [2024-10-12 18:52:42,093 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-12 18:52:42,094 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 13 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 53 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.5s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:42,094 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 97 Invalid, 53 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 2.5s Time] [2024-10-12 18:52:42,095 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-10-12 18:52:42,105 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 45. [2024-10-12 18:52:42,106 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 32 states have (on average 1.40625) internal successors, (45), 33 states have internal predecessors, (45), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-10-12 18:52:42,111 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 62 transitions. [2024-10-12 18:52:42,112 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 62 transitions. Word has length 18 [2024-10-12 18:52:42,112 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:42,112 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 62 transitions. [2024-10-12 18:52:42,112 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-10-12 18:52:42,112 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 62 transitions. [2024-10-12 18:52:42,113 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-10-12 18:52:42,113 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:42,113 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:42,132 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-12 18:52:42,314 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:42,314 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:42,315 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:42,315 INFO L85 PathProgramCache]: Analyzing trace with hash -99991460, now seen corresponding path program 1 times [2024-10-12 18:52:42,315 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:42,315 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1614431681] [2024-10-12 18:52:42,315 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:42,316 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:42,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:42,604 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:42,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:42,610 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:42,612 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:42,618 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 18:52:42,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:42,655 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 18:52:42,656 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:42,656 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1614431681] [2024-10-12 18:52:42,656 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1614431681] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:52:42,657 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [820919931] [2024-10-12 18:52:42,657 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:42,658 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:42,658 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:42,660 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:42,661 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-10-12 18:52:42,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:42,711 INFO L255 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-12 18:52:42,713 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:42,800 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 18:52:42,800 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:42,937 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 18:52:42,940 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [820919931] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:42,940 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:52:42,940 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8, 8] total 12 [2024-10-12 18:52:42,940 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1859752942] [2024-10-12 18:52:42,940 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:42,941 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-10-12 18:52:42,941 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:42,942 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-12 18:52:42,942 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2024-10-12 18:52:42,943 INFO L87 Difference]: Start difference. First operand 45 states and 62 transitions. Second operand has 12 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (5), 4 states have call predecessors, (5), 1 states have call successors, (5) [2024-10-12 18:52:43,053 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:43,053 INFO L93 Difference]: Finished difference Result 52 states and 68 transitions. [2024-10-12 18:52:43,054 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-12 18:52:43,054 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (5), 4 states have call predecessors, (5), 1 states have call successors, (5) Word has length 24 [2024-10-12 18:52:43,054 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:43,055 INFO L225 Difference]: With dead ends: 52 [2024-10-12 18:52:43,055 INFO L226 Difference]: Without dead ends: 47 [2024-10-12 18:52:43,056 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 48 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2024-10-12 18:52:43,056 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 28 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 76 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:43,057 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 91 Invalid, 76 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:52:43,058 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-10-12 18:52:43,067 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 31. [2024-10-12 18:52:43,068 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 22 states have internal predecessors, (27), 6 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-10-12 18:52:43,070 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 38 transitions. [2024-10-12 18:52:43,071 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 38 transitions. Word has length 24 [2024-10-12 18:52:43,072 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:43,072 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 38 transitions. [2024-10-12 18:52:43,072 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 1.8181818181818181) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (5), 4 states have call predecessors, (5), 1 states have call successors, (5) [2024-10-12 18:52:43,072 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 38 transitions. [2024-10-12 18:52:43,073 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-10-12 18:52:43,075 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:43,075 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:43,092 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-10-12 18:52:43,277 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,SelfDestructingSolverStorable3 [2024-10-12 18:52:43,278 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:43,278 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:43,278 INFO L85 PathProgramCache]: Analyzing trace with hash -1981880857, now seen corresponding path program 1 times [2024-10-12 18:52:43,279 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:43,279 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1366477406] [2024-10-12 18:52:43,279 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:43,279 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:43,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,378 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:43,380 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,383 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:43,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,387 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 18:52:43,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,391 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 18:52:43,391 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:43,391 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1366477406] [2024-10-12 18:52:43,391 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1366477406] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:52:43,391 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:52:43,391 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-12 18:52:43,392 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [589718375] [2024-10-12 18:52:43,392 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:52:43,392 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-12 18:52:43,392 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:43,393 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-12 18:52:43,393 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-12 18:52:43,393 INFO L87 Difference]: Start difference. First operand 31 states and 38 transitions. Second operand has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 6 states have internal predecessors, (20), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-12 18:52:43,448 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:43,450 INFO L93 Difference]: Finished difference Result 60 states and 74 transitions. [2024-10-12 18:52:43,450 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-12 18:52:43,450 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 6 states have internal predecessors, (20), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 30 [2024-10-12 18:52:43,451 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:43,451 INFO L225 Difference]: With dead ends: 60 [2024-10-12 18:52:43,451 INFO L226 Difference]: Without dead ends: 39 [2024-10-12 18:52:43,452 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-12 18:52:43,452 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 9 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:43,452 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 122 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:52:43,453 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2024-10-12 18:52:43,469 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2024-10-12 18:52:43,470 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 28 states have internal predecessors, (33), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-12 18:52:43,471 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 46 transitions. [2024-10-12 18:52:43,473 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 46 transitions. Word has length 30 [2024-10-12 18:52:43,473 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:43,473 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 46 transitions. [2024-10-12 18:52:43,473 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 6 states have internal predecessors, (20), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-12 18:52:43,473 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 46 transitions. [2024-10-12 18:52:43,474 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-10-12 18:52:43,475 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:43,475 INFO L215 NwaCegarLoop]: trace histogram [3, 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-10-12 18:52:43,475 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-10-12 18:52:43,475 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:43,476 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:43,476 INFO L85 PathProgramCache]: Analyzing trace with hash 2089520544, now seen corresponding path program 1 times [2024-10-12 18:52:43,477 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:43,477 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [357238729] [2024-10-12 18:52:43,477 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:43,477 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:43,491 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,573 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:43,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,577 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:43,579 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,582 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 18:52:43,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,587 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-12 18:52:43,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,598 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-10-12 18:52:43,599 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:43,599 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [357238729] [2024-10-12 18:52:43,599 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [357238729] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:52:43,599 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:52:43,600 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-10-12 18:52:43,600 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [214200317] [2024-10-12 18:52:43,600 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:52:43,600 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-12 18:52:43,601 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:43,601 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-12 18:52:43,601 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2024-10-12 18:52:43,602 INFO L87 Difference]: Start difference. First operand 39 states and 46 transitions. Second operand has 7 states, 7 states have (on average 3.0) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-12 18:52:43,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:43,684 INFO L93 Difference]: Finished difference Result 69 states and 84 transitions. [2024-10-12 18:52:43,685 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-12 18:52:43,685 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.0) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 36 [2024-10-12 18:52:43,686 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:43,686 INFO L225 Difference]: With dead ends: 69 [2024-10-12 18:52:43,686 INFO L226 Difference]: Without dead ends: 48 [2024-10-12 18:52:43,687 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2024-10-12 18:52:43,688 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 14 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:43,688 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 136 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:52:43,691 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2024-10-12 18:52:43,712 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 47. [2024-10-12 18:52:43,713 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 34 states have (on average 1.1764705882352942) internal successors, (40), 34 states have internal predecessors, (40), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-12 18:52:43,713 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 55 transitions. [2024-10-12 18:52:43,714 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 55 transitions. Word has length 36 [2024-10-12 18:52:43,714 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:43,714 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 55 transitions. [2024-10-12 18:52:43,714 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.0) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-12 18:52:43,715 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 55 transitions. [2024-10-12 18:52:43,718 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-10-12 18:52:43,719 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:43,719 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:43,719 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-10-12 18:52:43,719 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:43,719 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:43,720 INFO L85 PathProgramCache]: Analyzing trace with hash 1409797157, now seen corresponding path program 1 times [2024-10-12 18:52:43,720 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:43,720 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1656500460] [2024-10-12 18:52:43,720 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:43,720 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:43,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,832 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:43,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,839 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:43,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,848 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 18:52:43,850 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,853 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-12 18:52:43,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,858 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-10-12 18:52:43,858 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:43,858 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1656500460] [2024-10-12 18:52:43,858 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1656500460] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:52:43,859 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1639823882] [2024-10-12 18:52:43,859 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:43,859 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:43,859 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:43,861 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:43,862 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-10-12 18:52:43,911 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:43,912 INFO L255 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 18:52:43,914 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:44,002 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 18:52:44,003 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:44,074 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-10-12 18:52:44,074 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1639823882] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:44,075 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:52:44,075 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 12 [2024-10-12 18:52:44,075 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [310654873] [2024-10-12 18:52:44,075 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:44,076 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-10-12 18:52:44,076 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:44,076 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-12 18:52:44,076 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2024-10-12 18:52:44,077 INFO L87 Difference]: Start difference. First operand 47 states and 55 transitions. Second operand has 12 states, 12 states have (on average 3.8333333333333335) internal successors, (46), 12 states have internal predecessors, (46), 8 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (12), 7 states have call predecessors, (12), 7 states have call successors, (12) [2024-10-12 18:52:44,256 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:44,257 INFO L93 Difference]: Finished difference Result 124 states and 155 transitions. [2024-10-12 18:52:44,257 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-12 18:52:44,257 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.8333333333333335) internal successors, (46), 12 states have internal predecessors, (46), 8 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (12), 7 states have call predecessors, (12), 7 states have call successors, (12) Word has length 38 [2024-10-12 18:52:44,258 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:44,259 INFO L225 Difference]: With dead ends: 124 [2024-10-12 18:52:44,259 INFO L226 Difference]: Without dead ends: 103 [2024-10-12 18:52:44,259 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2024-10-12 18:52:44,260 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 66 mSDsluCounter, 150 mSDsCounter, 0 mSdLazyCounter, 86 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 66 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 98 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 86 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:44,260 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [66 Valid, 179 Invalid, 98 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 86 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:52:44,261 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2024-10-12 18:52:44,299 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 90. [2024-10-12 18:52:44,299 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 66 states have (on average 1.2272727272727273) internal successors, (81), 67 states have internal predecessors, (81), 16 states have call successors, (16), 8 states have call predecessors, (16), 7 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2024-10-12 18:52:44,300 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 112 transitions. [2024-10-12 18:52:44,301 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 112 transitions. Word has length 38 [2024-10-12 18:52:44,301 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:44,301 INFO L471 AbstractCegarLoop]: Abstraction has 90 states and 112 transitions. [2024-10-12 18:52:44,301 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.8333333333333335) internal successors, (46), 12 states have internal predecessors, (46), 8 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (12), 7 states have call predecessors, (12), 7 states have call successors, (12) [2024-10-12 18:52:44,302 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 112 transitions. [2024-10-12 18:52:44,302 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-10-12 18:52:44,303 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:44,303 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:44,319 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-10-12 18:52:44,506 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:44,507 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:44,507 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:44,507 INFO L85 PathProgramCache]: Analyzing trace with hash -1072156249, now seen corresponding path program 1 times [2024-10-12 18:52:44,507 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:44,507 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [283790756] [2024-10-12 18:52:44,508 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:44,508 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:44,515 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:44,542 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:44,544 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:44,545 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:44,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:44,548 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 18:52:44,548 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:44,550 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-12 18:52:44,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:44,553 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-12 18:52:44,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:44,556 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-10-12 18:52:44,556 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:44,557 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [283790756] [2024-10-12 18:52:44,557 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [283790756] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:52:44,557 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:52:44,557 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-10-12 18:52:44,557 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [585873972] [2024-10-12 18:52:44,557 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:52:44,558 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-12 18:52:44,558 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:44,559 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-12 18:52:44,559 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-10-12 18:52:44,559 INFO L87 Difference]: Start difference. First operand 90 states and 112 transitions. Second operand has 4 states, 4 states have (on average 5.5) internal successors, (22), 4 states have internal predecessors, (22), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-10-12 18:52:44,615 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:44,616 INFO L93 Difference]: Finished difference Result 153 states and 197 transitions. [2024-10-12 18:52:44,616 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-12 18:52:44,616 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 5.5) internal successors, (22), 4 states have internal predecessors, (22), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 42 [2024-10-12 18:52:44,616 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:44,619 INFO L225 Difference]: With dead ends: 153 [2024-10-12 18:52:44,619 INFO L226 Difference]: Without dead ends: 114 [2024-10-12 18:52:44,619 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-10-12 18:52:44,620 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 20 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:44,621 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 85 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:52:44,621 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2024-10-12 18:52:44,665 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 104. [2024-10-12 18:52:44,666 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 77 states have (on average 1.2337662337662338) internal successors, (95), 78 states have internal predecessors, (95), 19 states have call successors, (19), 8 states have call predecessors, (19), 7 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2024-10-12 18:52:44,668 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 132 transitions. [2024-10-12 18:52:44,668 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 132 transitions. Word has length 42 [2024-10-12 18:52:44,668 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:44,669 INFO L471 AbstractCegarLoop]: Abstraction has 104 states and 132 transitions. [2024-10-12 18:52:44,669 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 5.5) internal successors, (22), 4 states have internal predecessors, (22), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-10-12 18:52:44,669 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 132 transitions. [2024-10-12 18:52:44,671 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-10-12 18:52:44,673 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:44,673 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:44,673 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-10-12 18:52:44,673 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:44,674 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:44,674 INFO L85 PathProgramCache]: Analyzing trace with hash 2142553388, now seen corresponding path program 1 times [2024-10-12 18:52:44,674 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:44,674 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [259696044] [2024-10-12 18:52:44,674 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:44,674 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:44,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:44,804 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:44,805 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:44,807 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:44,810 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:44,812 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 18:52:44,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:44,816 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-12 18:52:44,820 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:44,822 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-12 18:52:44,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:44,824 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-10-12 18:52:44,825 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:44,825 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [259696044] [2024-10-12 18:52:44,825 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [259696044] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:52:44,825 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2038387339] [2024-10-12 18:52:44,825 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:44,829 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:44,829 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:44,831 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:44,832 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-10-12 18:52:44,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:44,884 INFO L255 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-12 18:52:44,886 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:44,950 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 8 proven. 14 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 18:52:44,950 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:45,044 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-10-12 18:52:45,044 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2038387339] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:45,044 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:52:45,044 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 7] total 14 [2024-10-12 18:52:45,045 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1781213654] [2024-10-12 18:52:45,045 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:45,046 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-10-12 18:52:45,046 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:45,046 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-10-12 18:52:45,047 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=113, Unknown=0, NotChecked=0, Total=182 [2024-10-12 18:52:45,047 INFO L87 Difference]: Start difference. First operand 104 states and 132 transitions. Second operand has 14 states, 14 states have (on average 3.7857142857142856) internal successors, (53), 14 states have internal predecessors, (53), 10 states have call successors, (16), 6 states have call predecessors, (16), 5 states have return successors, (15), 9 states have call predecessors, (15), 9 states have call successors, (15) [2024-10-12 18:52:45,281 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:45,281 INFO L93 Difference]: Finished difference Result 214 states and 278 transitions. [2024-10-12 18:52:45,282 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-10-12 18:52:45,282 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.7857142857142856) internal successors, (53), 14 states have internal predecessors, (53), 10 states have call successors, (16), 6 states have call predecessors, (16), 5 states have return successors, (15), 9 states have call predecessors, (15), 9 states have call successors, (15) Word has length 44 [2024-10-12 18:52:45,282 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:45,284 INFO L225 Difference]: With dead ends: 214 [2024-10-12 18:52:45,284 INFO L226 Difference]: Without dead ends: 167 [2024-10-12 18:52:45,286 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=111, Invalid=231, Unknown=0, NotChecked=0, Total=342 [2024-10-12 18:52:45,287 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 83 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 83 SdHoareTripleChecker+Valid, 170 SdHoareTripleChecker+Invalid, 110 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:45,288 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [83 Valid, 170 Invalid, 110 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 18:52:45,289 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 167 states. [2024-10-12 18:52:45,332 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 167 to 148. [2024-10-12 18:52:45,332 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 110 states have (on average 1.2454545454545454) internal successors, (137), 111 states have internal predecessors, (137), 28 states have call successors, (28), 10 states have call predecessors, (28), 9 states have return successors, (27), 26 states have call predecessors, (27), 27 states have call successors, (27) [2024-10-12 18:52:45,333 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 192 transitions. [2024-10-12 18:52:45,334 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 192 transitions. Word has length 44 [2024-10-12 18:52:45,334 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:45,334 INFO L471 AbstractCegarLoop]: Abstraction has 148 states and 192 transitions. [2024-10-12 18:52:45,335 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.7857142857142856) internal successors, (53), 14 states have internal predecessors, (53), 10 states have call successors, (16), 6 states have call predecessors, (16), 5 states have return successors, (15), 9 states have call predecessors, (15), 9 states have call successors, (15) [2024-10-12 18:52:45,335 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 192 transitions. [2024-10-12 18:52:45,336 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-10-12 18:52:45,336 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:45,336 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:45,352 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-12 18:52:45,536 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:45,537 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:45,537 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:45,538 INFO L85 PathProgramCache]: Analyzing trace with hash 1696895027, now seen corresponding path program 1 times [2024-10-12 18:52:45,538 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:45,538 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [309918585] [2024-10-12 18:52:45,538 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:45,538 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:45,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:45,692 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:45,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:45,697 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:45,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:45,701 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 18:52:45,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:45,705 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-12 18:52:45,707 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:45,709 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-12 18:52:45,711 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:45,713 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-12 18:52:45,714 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:45,719 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 8 proven. 6 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-12 18:52:45,721 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:45,721 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [309918585] [2024-10-12 18:52:45,721 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [309918585] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:52:45,722 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1174597764] [2024-10-12 18:52:45,722 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:45,722 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:45,722 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:45,724 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:45,726 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-10-12 18:52:45,772 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:45,773 INFO L255 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-12 18:52:45,775 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:45,854 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 8 proven. 30 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 18:52:45,855 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:45,989 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 8 proven. 6 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-12 18:52:45,990 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1174597764] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:45,990 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:52:45,990 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-10-12 18:52:45,990 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [116023376] [2024-10-12 18:52:45,990 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:45,990 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-12 18:52:45,991 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:45,991 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-12 18:52:45,991 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=144, Unknown=0, NotChecked=0, Total=240 [2024-10-12 18:52:45,992 INFO L87 Difference]: Start difference. First operand 148 states and 192 transitions. Second operand has 16 states, 16 states have (on average 3.75) internal successors, (60), 16 states have internal predecessors, (60), 12 states have call successors, (19), 7 states have call predecessors, (19), 6 states have return successors, (18), 11 states have call predecessors, (18), 11 states have call successors, (18) [2024-10-12 18:52:46,274 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:46,274 INFO L93 Difference]: Finished difference Result 206 states and 273 transitions. [2024-10-12 18:52:46,275 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-12 18:52:46,275 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.75) internal successors, (60), 16 states have internal predecessors, (60), 12 states have call successors, (19), 7 states have call predecessors, (19), 6 states have return successors, (18), 11 states have call predecessors, (18), 11 states have call successors, (18) Word has length 50 [2024-10-12 18:52:46,276 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:46,277 INFO L225 Difference]: With dead ends: 206 [2024-10-12 18:52:46,277 INFO L226 Difference]: Without dead ends: 201 [2024-10-12 18:52:46,278 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 104 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=142, Invalid=278, Unknown=0, NotChecked=0, Total=420 [2024-10-12 18:52:46,278 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 115 mSDsluCounter, 166 mSDsCounter, 0 mSdLazyCounter, 94 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 115 SdHoareTripleChecker+Valid, 196 SdHoareTripleChecker+Invalid, 123 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 94 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:46,279 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [115 Valid, 196 Invalid, 123 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 94 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-12 18:52:46,279 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 201 states. [2024-10-12 18:52:46,332 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 201 to 193. [2024-10-12 18:52:46,333 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 193 states, 143 states have (on average 1.2377622377622377) internal successors, (177), 147 states have internal predecessors, (177), 38 states have call successors, (38), 12 states have call predecessors, (38), 11 states have return successors, (37), 33 states have call predecessors, (37), 37 states have call successors, (37) [2024-10-12 18:52:46,335 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 193 states to 193 states and 252 transitions. [2024-10-12 18:52:46,335 INFO L78 Accepts]: Start accepts. Automaton has 193 states and 252 transitions. Word has length 50 [2024-10-12 18:52:46,335 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:46,336 INFO L471 AbstractCegarLoop]: Abstraction has 193 states and 252 transitions. [2024-10-12 18:52:46,336 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.75) internal successors, (60), 16 states have internal predecessors, (60), 12 states have call successors, (19), 7 states have call predecessors, (19), 6 states have return successors, (18), 11 states have call predecessors, (18), 11 states have call successors, (18) [2024-10-12 18:52:46,336 INFO L276 IsEmpty]: Start isEmpty. Operand 193 states and 252 transitions. [2024-10-12 18:52:46,338 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2024-10-12 18:52:46,341 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:46,341 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:46,358 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-10-12 18:52:46,542 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-10-12 18:52:46,542 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:46,542 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:46,543 INFO L85 PathProgramCache]: Analyzing trace with hash -1904373439, now seen corresponding path program 1 times [2024-10-12 18:52:46,543 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:46,543 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1652336571] [2024-10-12 18:52:46,543 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:46,543 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:46,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:46,675 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:46,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:46,678 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:46,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:46,681 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 18:52:46,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:46,688 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-12 18:52:46,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:46,696 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-12 18:52:46,701 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:46,704 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-12 18:52:46,707 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:46,709 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-12 18:52:46,711 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:46,714 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-10-12 18:52:46,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:46,718 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-10-12 18:52:46,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:46,722 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 72 [2024-10-12 18:52:46,723 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:46,724 INFO L134 CoverageAnalysis]: Checked inductivity of 180 backedges. 46 proven. 12 refuted. 0 times theorem prover too weak. 122 trivial. 0 not checked. [2024-10-12 18:52:46,724 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:46,724 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1652336571] [2024-10-12 18:52:46,725 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1652336571] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:52:46,725 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [923001936] [2024-10-12 18:52:46,725 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:46,725 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:46,725 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:46,727 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:46,728 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-10-12 18:52:46,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:46,791 INFO L255 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-12 18:52:46,794 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:46,849 INFO L134 CoverageAnalysis]: Checked inductivity of 180 backedges. 64 proven. 12 refuted. 0 times theorem prover too weak. 104 trivial. 0 not checked. [2024-10-12 18:52:46,850 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:46,929 INFO L134 CoverageAnalysis]: Checked inductivity of 180 backedges. 38 proven. 12 refuted. 0 times theorem prover too weak. 130 trivial. 0 not checked. [2024-10-12 18:52:46,929 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [923001936] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:46,929 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:52:46,930 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 4] total 7 [2024-10-12 18:52:46,930 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1787070785] [2024-10-12 18:52:46,930 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:46,930 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-12 18:52:46,930 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:46,931 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-12 18:52:46,931 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=23, Unknown=0, NotChecked=0, Total=42 [2024-10-12 18:52:46,931 INFO L87 Difference]: Start difference. First operand 193 states and 252 transitions. Second operand has 7 states, 7 states have (on average 7.428571428571429) internal successors, (52), 7 states have internal predecessors, (52), 7 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 7 states have call predecessors, (13), 7 states have call successors, (13) [2024-10-12 18:52:47,067 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:47,068 INFO L93 Difference]: Finished difference Result 486 states and 675 transitions. [2024-10-12 18:52:47,068 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-12 18:52:47,068 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 7.428571428571429) internal successors, (52), 7 states have internal predecessors, (52), 7 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 7 states have call predecessors, (13), 7 states have call successors, (13) Word has length 86 [2024-10-12 18:52:47,069 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:47,073 INFO L225 Difference]: With dead ends: 486 [2024-10-12 18:52:47,073 INFO L226 Difference]: Without dead ends: 350 [2024-10-12 18:52:47,074 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 196 GetRequests, 190 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=23, Unknown=0, NotChecked=0, Total=42 [2024-10-12 18:52:47,075 INFO L432 NwaCegarLoop]: 65 mSDtfsCounter, 29 mSDsluCounter, 120 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 185 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:47,076 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 185 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:52:47,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 350 states. [2024-10-12 18:52:47,177 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 350 to 337. [2024-10-12 18:52:47,178 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 337 states, 253 states have (on average 1.2608695652173914) internal successors, (319), 259 states have internal predecessors, (319), 72 states have call successors, (72), 12 states have call predecessors, (72), 11 states have return successors, (71), 65 states have call predecessors, (71), 71 states have call successors, (71) [2024-10-12 18:52:47,180 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 337 states to 337 states and 462 transitions. [2024-10-12 18:52:47,181 INFO L78 Accepts]: Start accepts. Automaton has 337 states and 462 transitions. Word has length 86 [2024-10-12 18:52:47,181 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:47,181 INFO L471 AbstractCegarLoop]: Abstraction has 337 states and 462 transitions. [2024-10-12 18:52:47,181 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 7.428571428571429) internal successors, (52), 7 states have internal predecessors, (52), 7 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 7 states have call predecessors, (13), 7 states have call successors, (13) [2024-10-12 18:52:47,181 INFO L276 IsEmpty]: Start isEmpty. Operand 337 states and 462 transitions. [2024-10-12 18:52:47,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2024-10-12 18:52:47,183 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:47,183 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:47,200 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-10-12 18:52:47,384 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:47,384 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:47,385 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:47,385 INFO L85 PathProgramCache]: Analyzing trace with hash 1715119347, now seen corresponding path program 2 times [2024-10-12 18:52:47,385 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:47,385 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1266288421] [2024-10-12 18:52:47,385 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:47,385 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:47,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:47,599 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:47,600 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:47,603 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:47,604 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:47,607 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 18:52:47,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:47,611 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-12 18:52:47,612 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:47,614 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-12 18:52:47,616 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:47,618 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-12 18:52:47,619 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:47,621 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-12 18:52:47,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:47,624 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-10-12 18:52:47,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:47,627 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 62 [2024-10-12 18:52:47,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:47,631 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 72 [2024-10-12 18:52:47,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:47,634 INFO L134 CoverageAnalysis]: Checked inductivity of 176 backedges. 32 proven. 26 refuted. 0 times theorem prover too weak. 118 trivial. 0 not checked. [2024-10-12 18:52:47,634 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:47,634 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1266288421] [2024-10-12 18:52:47,634 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1266288421] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:52:47,634 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1666788139] [2024-10-12 18:52:47,635 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-12 18:52:47,635 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:47,635 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:47,636 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:47,638 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-10-12 18:52:47,713 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-12 18:52:47,713 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-12 18:52:47,715 INFO L255 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-12 18:52:47,717 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:47,826 INFO L134 CoverageAnalysis]: Checked inductivity of 176 backedges. 58 proven. 110 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-10-12 18:52:47,827 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:48,074 INFO L134 CoverageAnalysis]: Checked inductivity of 176 backedges. 32 proven. 26 refuted. 0 times theorem prover too weak. 118 trivial. 0 not checked. [2024-10-12 18:52:48,074 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1666788139] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:48,074 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:52:48,074 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10, 11] total 22 [2024-10-12 18:52:48,074 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1200378709] [2024-10-12 18:52:48,074 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:48,075 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-10-12 18:52:48,075 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:48,076 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-10-12 18:52:48,076 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=193, Invalid=269, Unknown=0, NotChecked=0, Total=462 [2024-10-12 18:52:48,076 INFO L87 Difference]: Start difference. First operand 337 states and 462 transitions. Second operand has 22 states, 22 states have (on average 4.318181818181818) internal successors, (95), 22 states have internal predecessors, (95), 18 states have call successors, (30), 10 states have call predecessors, (30), 10 states have return successors, (29), 18 states have call predecessors, (29), 18 states have call successors, (29) [2024-10-12 18:52:48,779 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:48,779 INFO L93 Difference]: Finished difference Result 980 states and 1408 transitions. [2024-10-12 18:52:48,779 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2024-10-12 18:52:48,780 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 4.318181818181818) internal successors, (95), 22 states have internal predecessors, (95), 18 states have call successors, (30), 10 states have call predecessors, (30), 10 states have return successors, (29), 18 states have call predecessors, (29), 18 states have call successors, (29) Word has length 86 [2024-10-12 18:52:48,780 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:48,785 INFO L225 Difference]: With dead ends: 980 [2024-10-12 18:52:48,785 INFO L226 Difference]: Without dead ends: 837 [2024-10-12 18:52:48,786 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 215 GetRequests, 181 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=438, Invalid=822, Unknown=0, NotChecked=0, Total=1260 [2024-10-12 18:52:48,786 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 258 mSDsluCounter, 254 mSDsCounter, 0 mSdLazyCounter, 186 mSolverCounterSat, 75 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 258 SdHoareTripleChecker+Valid, 283 SdHoareTripleChecker+Invalid, 261 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 75 IncrementalHoareTripleChecker+Valid, 186 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:48,787 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [258 Valid, 283 Invalid, 261 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [75 Valid, 186 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-12 18:52:48,788 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 837 states. [2024-10-12 18:52:48,972 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 837 to 788. [2024-10-12 18:52:48,974 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 788 states, 595 states have (on average 1.253781512605042) internal successors, (746), 604 states have internal predecessors, (746), 175 states have call successors, (175), 18 states have call predecessors, (175), 17 states have return successors, (174), 165 states have call predecessors, (174), 174 states have call successors, (174) [2024-10-12 18:52:48,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 788 states to 788 states and 1095 transitions. [2024-10-12 18:52:48,978 INFO L78 Accepts]: Start accepts. Automaton has 788 states and 1095 transitions. Word has length 86 [2024-10-12 18:52:48,979 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:48,979 INFO L471 AbstractCegarLoop]: Abstraction has 788 states and 1095 transitions. [2024-10-12 18:52:48,981 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 4.318181818181818) internal successors, (95), 22 states have internal predecessors, (95), 18 states have call successors, (30), 10 states have call predecessors, (30), 10 states have return successors, (29), 18 states have call predecessors, (29), 18 states have call successors, (29) [2024-10-12 18:52:48,982 INFO L276 IsEmpty]: Start isEmpty. Operand 788 states and 1095 transitions. [2024-10-12 18:52:48,983 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2024-10-12 18:52:48,983 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:48,983 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:49,003 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-10-12 18:52:49,184 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:49,184 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:49,185 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:49,185 INFO L85 PathProgramCache]: Analyzing trace with hash 1117496236, now seen corresponding path program 1 times [2024-10-12 18:52:49,185 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:49,185 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1385505494] [2024-10-12 18:52:49,185 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:49,185 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:49,200 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:49,489 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:49,491 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:49,494 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:49,497 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:49,501 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 18:52:49,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:49,505 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-12 18:52:49,508 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:49,512 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-12 18:52:49,514 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:49,521 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-12 18:52:49,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:49,527 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-12 18:52:49,529 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:49,532 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-10-12 18:52:49,534 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:49,537 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 62 [2024-10-12 18:52:49,541 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:49,543 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-10-12 18:52:49,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:49,549 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-10-12 18:52:49,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:49,556 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 22 proven. 46 refuted. 0 times theorem prover too weak. 148 trivial. 0 not checked. [2024-10-12 18:52:49,556 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:49,556 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1385505494] [2024-10-12 18:52:49,557 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1385505494] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:52:49,557 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1087706003] [2024-10-12 18:52:49,557 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:49,557 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:49,557 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:49,559 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:49,561 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-10-12 18:52:49,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:49,631 INFO L255 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-10-12 18:52:49,637 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:49,774 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 22 proven. 190 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 18:52:49,774 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:50,067 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 22 proven. 46 refuted. 0 times theorem prover too weak. 148 trivial. 0 not checked. [2024-10-12 18:52:50,067 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1087706003] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:50,068 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:52:50,068 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12, 13] total 26 [2024-10-12 18:52:50,068 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1195248538] [2024-10-12 18:52:50,068 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:50,069 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-10-12 18:52:50,069 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:50,070 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-10-12 18:52:50,070 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=279, Invalid=371, Unknown=0, NotChecked=0, Total=650 [2024-10-12 18:52:50,071 INFO L87 Difference]: Start difference. First operand 788 states and 1095 transitions. Second operand has 26 states, 26 states have (on average 4.115384615384615) internal successors, (107), 26 states have internal predecessors, (107), 22 states have call successors, (34), 12 states have call predecessors, (34), 11 states have return successors, (33), 21 states have call predecessors, (33), 21 states have call successors, (33) [2024-10-12 18:52:50,933 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:50,933 INFO L93 Difference]: Finished difference Result 1280 states and 1779 transitions. [2024-10-12 18:52:50,934 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2024-10-12 18:52:50,934 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 4.115384615384615) internal successors, (107), 26 states have internal predecessors, (107), 22 states have call successors, (34), 12 states have call predecessors, (34), 11 states have return successors, (33), 21 states have call predecessors, (33), 21 states have call successors, (33) Word has length 92 [2024-10-12 18:52:50,934 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:50,939 INFO L225 Difference]: With dead ends: 1280 [2024-10-12 18:52:50,939 INFO L226 Difference]: Without dead ends: 790 [2024-10-12 18:52:50,941 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 234 GetRequests, 193 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 256 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=627, Invalid=1179, Unknown=0, NotChecked=0, Total=1806 [2024-10-12 18:52:50,943 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 340 mSDsluCounter, 300 mSDsCounter, 0 mSdLazyCounter, 229 mSolverCounterSat, 99 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 340 SdHoareTripleChecker+Valid, 329 SdHoareTripleChecker+Invalid, 328 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 99 IncrementalHoareTripleChecker+Valid, 229 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:50,943 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [340 Valid, 329 Invalid, 328 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [99 Valid, 229 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-10-12 18:52:50,945 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 790 states. [2024-10-12 18:52:51,099 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 790 to 734. [2024-10-12 18:52:51,101 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 734 states, 550 states have (on average 1.22) internal successors, (671), 555 states have internal predecessors, (671), 162 states have call successors, (162), 22 states have call predecessors, (162), 21 states have return successors, (161), 156 states have call predecessors, (161), 161 states have call successors, (161) [2024-10-12 18:52:51,104 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 734 states to 734 states and 994 transitions. [2024-10-12 18:52:51,105 INFO L78 Accepts]: Start accepts. Automaton has 734 states and 994 transitions. Word has length 92 [2024-10-12 18:52:51,105 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:51,105 INFO L471 AbstractCegarLoop]: Abstraction has 734 states and 994 transitions. [2024-10-12 18:52:51,106 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 4.115384615384615) internal successors, (107), 26 states have internal predecessors, (107), 22 states have call successors, (34), 12 states have call predecessors, (34), 11 states have return successors, (33), 21 states have call predecessors, (33), 21 states have call successors, (33) [2024-10-12 18:52:51,106 INFO L276 IsEmpty]: Start isEmpty. Operand 734 states and 994 transitions. [2024-10-12 18:52:51,108 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2024-10-12 18:52:51,109 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:51,109 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:51,127 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-10-12 18:52:51,313 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-10-12 18:52:51,314 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:51,314 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:51,314 INFO L85 PathProgramCache]: Analyzing trace with hash -32862541, now seen corresponding path program 1 times [2024-10-12 18:52:51,314 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:51,314 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [690707019] [2024-10-12 18:52:51,314 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:51,314 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:51,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,628 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:51,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,631 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:51,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,634 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 18:52:51,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,637 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-12 18:52:51,638 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,640 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-12 18:52:51,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,645 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-12 18:52:51,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,649 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-12 18:52:51,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,652 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-10-12 18:52:51,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,659 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 62 [2024-10-12 18:52:51,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,662 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-10-12 18:52:51,664 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,665 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-10-12 18:52:51,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,669 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 86 [2024-10-12 18:52:51,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,702 INFO L134 CoverageAnalysis]: Checked inductivity of 260 backedges. 20 proven. 56 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2024-10-12 18:52:51,703 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:51,703 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [690707019] [2024-10-12 18:52:51,703 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [690707019] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:52:51,703 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [632498351] [2024-10-12 18:52:51,703 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:51,703 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:51,704 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:51,705 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:51,707 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-10-12 18:52:51,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:51,772 INFO L255 TraceCheckSpWp]: Trace formula consists of 231 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-10-12 18:52:51,775 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:52:51,891 INFO L134 CoverageAnalysis]: Checked inductivity of 260 backedges. 20 proven. 236 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 18:52:51,891 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:52:52,209 INFO L134 CoverageAnalysis]: Checked inductivity of 260 backedges. 20 proven. 56 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2024-10-12 18:52:52,210 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [632498351] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:52:52,210 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:52:52,210 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13, 14] total 28 [2024-10-12 18:52:52,210 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [639925888] [2024-10-12 18:52:52,210 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:52:52,211 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-10-12 18:52:52,211 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:52,212 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-10-12 18:52:52,212 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=330, Invalid=426, Unknown=0, NotChecked=0, Total=756 [2024-10-12 18:52:52,212 INFO L87 Difference]: Start difference. First operand 734 states and 994 transitions. Second operand has 28 states, 28 states have (on average 4.071428571428571) internal successors, (114), 28 states have internal predecessors, (114), 24 states have call successors, (37), 13 states have call predecessors, (37), 12 states have return successors, (36), 23 states have call predecessors, (36), 23 states have call successors, (36) [2024-10-12 18:52:53,099 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:53,099 INFO L93 Difference]: Finished difference Result 845 states and 1153 transitions. [2024-10-12 18:52:53,099 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2024-10-12 18:52:53,100 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 4.071428571428571) internal successors, (114), 28 states have internal predecessors, (114), 24 states have call successors, (37), 13 states have call predecessors, (37), 12 states have return successors, (36), 23 states have call predecessors, (36), 23 states have call successors, (36) Word has length 98 [2024-10-12 18:52:53,100 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:53,104 INFO L225 Difference]: With dead ends: 845 [2024-10-12 18:52:53,105 INFO L226 Difference]: Without dead ends: 840 [2024-10-12 18:52:53,106 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 249 GetRequests, 206 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 273 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=694, Invalid=1286, Unknown=0, NotChecked=0, Total=1980 [2024-10-12 18:52:53,107 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 379 mSDsluCounter, 297 mSDsCounter, 0 mSdLazyCounter, 218 mSolverCounterSat, 163 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 379 SdHoareTripleChecker+Valid, 327 SdHoareTripleChecker+Invalid, 381 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 163 IncrementalHoareTripleChecker+Valid, 218 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:53,107 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [379 Valid, 327 Invalid, 381 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [163 Valid, 218 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-10-12 18:52:53,108 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 840 states. [2024-10-12 18:52:53,303 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 840 to 825. [2024-10-12 18:52:53,305 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 825 states, 619 states have (on average 1.197092084006462) internal successors, (741), 625 states have internal predecessors, (741), 182 states have call successors, (182), 24 states have call predecessors, (182), 23 states have return successors, (181), 175 states have call predecessors, (181), 181 states have call successors, (181) [2024-10-12 18:52:53,309 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 825 states to 825 states and 1104 transitions. [2024-10-12 18:52:53,310 INFO L78 Accepts]: Start accepts. Automaton has 825 states and 1104 transitions. Word has length 98 [2024-10-12 18:52:53,311 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:53,311 INFO L471 AbstractCegarLoop]: Abstraction has 825 states and 1104 transitions. [2024-10-12 18:52:53,311 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 4.071428571428571) internal successors, (114), 28 states have internal predecessors, (114), 24 states have call successors, (37), 13 states have call predecessors, (37), 12 states have return successors, (36), 23 states have call predecessors, (36), 23 states have call successors, (36) [2024-10-12 18:52:53,311 INFO L276 IsEmpty]: Start isEmpty. Operand 825 states and 1104 transitions. [2024-10-12 18:52:53,315 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 177 [2024-10-12 18:52:53,316 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:53,316 INFO L215 NwaCegarLoop]: trace histogram [20, 19, 19, 9, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:53,333 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-10-12 18:52:53,517 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-10-12 18:52:53,518 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:53,518 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:53,518 INFO L85 PathProgramCache]: Analyzing trace with hash -1211281524, now seen corresponding path program 3 times [2024-10-12 18:52:53,518 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:53,518 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [286968585] [2024-10-12 18:52:53,519 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:53,519 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:53,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,588 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:53,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,590 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:53,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,593 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 18:52:53,594 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,595 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-12 18:52:53,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,597 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-12 18:52:53,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,599 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-12 18:52:53,600 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,601 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-12 18:52:53,602 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,603 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-10-12 18:52:53,604 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,605 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 62 [2024-10-12 18:52:53,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,607 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-10-12 18:52:53,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,610 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-10-12 18:52:53,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,613 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 86 [2024-10-12 18:52:53,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,615 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 94 [2024-10-12 18:52:53,616 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,617 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 102 [2024-10-12 18:52:53,618 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,619 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 110 [2024-10-12 18:52:53,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,621 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 118 [2024-10-12 18:52:53,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,623 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 126 [2024-10-12 18:52:53,624 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,625 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 134 [2024-10-12 18:52:53,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,627 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 142 [2024-10-12 18:52:53,628 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,629 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 152 [2024-10-12 18:52:53,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,632 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 160 [2024-10-12 18:52:53,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:53,634 INFO L134 CoverageAnalysis]: Checked inductivity of 984 backedges. 198 proven. 0 refuted. 0 times theorem prover too weak. 786 trivial. 0 not checked. [2024-10-12 18:52:53,634 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:53,635 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [286968585] [2024-10-12 18:52:53,635 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [286968585] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 18:52:53,635 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 18:52:53,635 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-10-12 18:52:53,635 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [594931166] [2024-10-12 18:52:53,635 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 18:52:53,636 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-12 18:52:53,636 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:52:53,636 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-12 18:52:53,636 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-10-12 18:52:53,637 INFO L87 Difference]: Start difference. First operand 825 states and 1104 transitions. Second operand has 4 states, 4 states have (on average 10.5) internal successors, (42), 4 states have internal predecessors, (42), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2024-10-12 18:52:53,846 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 18:52:53,846 INFO L93 Difference]: Finished difference Result 1368 states and 1828 transitions. [2024-10-12 18:52:53,846 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-12 18:52:53,847 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 10.5) internal successors, (42), 4 states have internal predecessors, (42), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) Word has length 176 [2024-10-12 18:52:53,847 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 18:52:53,851 INFO L225 Difference]: With dead ends: 1368 [2024-10-12 18:52:53,852 INFO L226 Difference]: Without dead ends: 863 [2024-10-12 18:52:53,854 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-10-12 18:52:53,855 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 9 mSDsluCounter, 41 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 88 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 18:52:53,855 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 88 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 18:52:53,856 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 863 states. [2024-10-12 18:52:53,978 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 863 to 808. [2024-10-12 18:52:53,980 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 808 states, 609 states have (on average 1.1839080459770115) internal successors, (721), 616 states have internal predecessors, (721), 175 states have call successors, (175), 24 states have call predecessors, (175), 23 states have return successors, (174), 167 states have call predecessors, (174), 174 states have call successors, (174) [2024-10-12 18:52:53,983 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 808 states to 808 states and 1070 transitions. [2024-10-12 18:52:53,985 INFO L78 Accepts]: Start accepts. Automaton has 808 states and 1070 transitions. Word has length 176 [2024-10-12 18:52:53,985 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 18:52:53,985 INFO L471 AbstractCegarLoop]: Abstraction has 808 states and 1070 transitions. [2024-10-12 18:52:53,985 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 10.5) internal successors, (42), 4 states have internal predecessors, (42), 4 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 4 states have call predecessors, (10), 4 states have call successors, (10) [2024-10-12 18:52:53,986 INFO L276 IsEmpty]: Start isEmpty. Operand 808 states and 1070 transitions. [2024-10-12 18:52:53,989 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 177 [2024-10-12 18:52:53,989 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 18:52:53,989 INFO L215 NwaCegarLoop]: trace histogram [20, 19, 19, 9, 8, 7, 7, 7, 7, 7, 7, 6, 5, 5, 5, 5, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 18:52:53,990 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14 [2024-10-12 18:52:53,990 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 18:52:53,990 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 18:52:53,990 INFO L85 PathProgramCache]: Analyzing trace with hash 231275114, now seen corresponding path program 4 times [2024-10-12 18:52:53,990 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 18:52:53,991 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [33585742] [2024-10-12 18:52:53,991 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 18:52:53,991 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 18:52:54,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,550 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-12 18:52:54,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,555 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 18:52:54,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,558 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 18:52:54,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,561 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-12 18:52:54,562 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,563 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-12 18:52:54,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,568 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-10-12 18:52:54,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,574 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-10-12 18:52:54,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,578 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-10-12 18:52:54,580 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,581 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 62 [2024-10-12 18:52:54,583 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,585 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-10-12 18:52:54,586 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,588 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-10-12 18:52:54,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,591 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 86 [2024-10-12 18:52:54,592 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,594 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 94 [2024-10-12 18:52:54,595 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,597 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 102 [2024-10-12 18:52:54,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,600 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 110 [2024-10-12 18:52:54,601 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,603 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 118 [2024-10-12 18:52:54,604 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,606 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 126 [2024-10-12 18:52:54,607 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,608 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 134 [2024-10-12 18:52:54,609 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,611 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 144 [2024-10-12 18:52:54,612 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,613 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 152 [2024-10-12 18:52:54,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,615 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 160 [2024-10-12 18:52:54,616 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 18:52:54,617 INFO L134 CoverageAnalysis]: Checked inductivity of 988 backedges. 138 proven. 156 refuted. 0 times theorem prover too weak. 694 trivial. 0 not checked. [2024-10-12 18:52:54,617 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 18:52:54,618 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [33585742] [2024-10-12 18:52:54,618 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [33585742] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 18:52:54,618 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2064338925] [2024-10-12 18:52:54,618 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-10-12 18:52:54,618 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 18:52:54,618 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 18:52:54,620 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 18:52:54,621 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-10-12 18:52:54,712 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-10-12 18:52:54,712 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-12 18:52:54,714 INFO L255 TraceCheckSpWp]: Trace formula consists of 345 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-10-12 18:52:54,717 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 18:53:00,333 INFO L134 CoverageAnalysis]: Checked inductivity of 988 backedges. 439 proven. 112 refuted. 0 times theorem prover too weak. 437 trivial. 0 not checked. [2024-10-12 18:53:00,333 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 18:53:01,026 INFO L134 CoverageAnalysis]: Checked inductivity of 988 backedges. 189 proven. 92 refuted. 0 times theorem prover too weak. 707 trivial. 0 not checked. [2024-10-12 18:53:01,026 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2064338925] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 18:53:01,026 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 18:53:01,026 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 11, 11] total 38 [2024-10-12 18:53:01,027 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [166334072] [2024-10-12 18:53:01,027 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 18:53:01,028 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 38 states [2024-10-12 18:53:01,028 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 18:53:01,030 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2024-10-12 18:53:01,030 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=246, Invalid=1159, Unknown=1, NotChecked=0, Total=1406 [2024-10-12 18:53:01,031 INFO L87 Difference]: Start difference. First operand 808 states and 1070 transitions. Second operand has 38 states, 38 states have (on average 4.394736842105263) internal successors, (167), 36 states have internal predecessors, (167), 31 states have call successors, (55), 2 states have call predecessors, (55), 3 states have return successors, (55), 33 states have call predecessors, (55), 31 states have call successors, (55) [2024-10-12 18:53:05,043 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-10-12 18:53:09,115 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-10-12 18:53:13,179 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-10-12 18:53:14,191 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.01s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-12 18:53:18,265 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-10-12 18:53:26,390 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-10-12 18:53:34,597 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-10-12 18:53:35,766 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.17s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-12 18:53:40,410 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-10-12 18:53:41,541 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.13s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-12 18:53:45,885 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-10-12 18:53:49,989 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-10-12 18:53:59,131 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.08s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-10-12 18:54:05,567 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.41s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-10-12 18:54:07,729 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.05s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-10-12 18:54:10,697 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.57s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0]