./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/ps4-ll_unwindbound50.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 84cfde4a Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound50.c -s /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-clean/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 870f3f117c59e986b23526e49a2d44ed8c8e543941d3d310e77e3939c7927e70 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-84cfde4 [2024-10-11 02:27:34,013 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-11 02:27:34,095 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-11 02:27:34,101 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-11 02:27:34,102 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-11 02:27:34,137 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-11 02:27:34,139 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-11 02:27:34,140 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-11 02:27:34,140 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-11 02:27:34,142 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-11 02:27:34,142 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-11 02:27:34,142 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-11 02:27:34,143 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-11 02:27:34,143 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-11 02:27:34,145 INFO L153 SettingsManager]: * Use SBE=true [2024-10-11 02:27:34,146 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-11 02:27:34,146 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-11 02:27:34,146 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-11 02:27:34,146 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-11 02:27:34,147 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-11 02:27:34,147 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-11 02:27:34,151 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-11 02:27:34,151 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-11 02:27:34,151 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-11 02:27:34,151 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-11 02:27:34,152 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-11 02:27:34,152 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-11 02:27:34,152 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-11 02:27:34,152 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-11 02:27:34,153 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-11 02:27:34,153 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-11 02:27:34,153 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-11 02:27:34,153 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-11 02:27:34,153 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-11 02:27:34,154 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-11 02:27:34,154 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-11 02:27:34,155 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-11 02:27:34,156 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-11 02:27:34,156 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-11 02:27:34,156 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-11 02:27:34,156 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-11 02:27:34,157 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-11 02:27:34,157 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-clean/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-clean/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 -> 870f3f117c59e986b23526e49a2d44ed8c8e543941d3d310e77e3939c7927e70 [2024-10-11 02:27:34,406 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-11 02:27:34,427 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-11 02:27:34,431 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-11 02:27:34,432 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-11 02:27:34,433 INFO L274 PluginConnector]: CDTParser initialized [2024-10-11 02:27:34,434 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound50.c [2024-10-11 02:27:35,891 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-11 02:27:36,073 INFO L384 CDTParser]: Found 1 translation units. [2024-10-11 02:27:36,074 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_unwindbound50.c [2024-10-11 02:27:36,081 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/2519a4a69/ceed0c620e3e44f4a9172179e6c6e476/FLAGf70cb1bcf [2024-10-11 02:27:36,456 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/2519a4a69/ceed0c620e3e44f4a9172179e6c6e476 [2024-10-11 02:27:36,458 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-11 02:27:36,459 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-11 02:27:36,461 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-11 02:27:36,461 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-11 02:27:36,468 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-11 02:27:36,469 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,470 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@28e4dc3c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36, skipping insertion in model container [2024-10-11 02:27:36,471 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,489 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-11 02:27:36,677 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/ps4-ll_unwindbound50.c[458,471] [2024-10-11 02:27:36,698 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-11 02:27:36,710 INFO L200 MainTranslator]: Completed pre-run [2024-10-11 02:27:36,724 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/ps4-ll_unwindbound50.c[458,471] [2024-10-11 02:27:36,731 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-11 02:27:36,750 INFO L204 MainTranslator]: Completed translation [2024-10-11 02:27:36,750 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36 WrapperNode [2024-10-11 02:27:36,751 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-11 02:27:36,752 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-11 02:27:36,752 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-11 02:27:36,752 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-11 02:27:36,760 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,766 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,784 INFO L138 Inliner]: procedures = 14, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 39 [2024-10-11 02:27:36,784 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-11 02:27:36,785 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-11 02:27:36,785 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-11 02:27:36,785 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-11 02:27:36,796 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,796 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,797 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,807 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-11 02:27:36,807 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,808 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,810 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,814 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,816 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,817 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,818 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-11 02:27:36,819 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-11 02:27:36,820 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-11 02:27:36,820 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-11 02:27:36,821 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36" (1/1) ... [2024-10-11 02:27:36,827 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-11 02:27:36,838 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:36,858 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-10-11 02:27:36,861 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-10-11 02:27:36,924 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-11 02:27:36,924 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-11 02:27:36,924 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-11 02:27:36,925 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-11 02:27:36,925 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-11 02:27:36,925 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-11 02:27:36,995 INFO L238 CfgBuilder]: Building ICFG [2024-10-11 02:27:36,998 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-11 02:27:37,155 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-10-11 02:27:37,157 INFO L287 CfgBuilder]: Performing block encoding [2024-10-11 02:27:37,192 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-11 02:27:37,192 INFO L314 CfgBuilder]: Removed 1 assume(true) statements. [2024-10-11 02:27:37,193 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.10 02:27:37 BoogieIcfgContainer [2024-10-11 02:27:37,193 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-11 02:27:37,196 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-11 02:27:37,197 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-11 02:27:37,200 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-11 02:27:37,201 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.10 02:27:36" (1/3) ... [2024-10-11 02:27:37,202 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@928d21c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.10 02:27:37, skipping insertion in model container [2024-10-11 02:27:37,202 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:27:36" (2/3) ... [2024-10-11 02:27:37,204 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@928d21c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.10 02:27:37, skipping insertion in model container [2024-10-11 02:27:37,204 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.10 02:27:37" (3/3) ... [2024-10-11 02:27:37,205 INFO L112 eAbstractionObserver]: Analyzing ICFG ps4-ll_unwindbound50.c [2024-10-11 02:27:37,222 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-11 02:27:37,222 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-11 02:27:37,279 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-11 02:27:37,286 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;@6159471c, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-11 02:27:37,286 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-11 02:27:37,291 INFO L276 IsEmpty]: Start isEmpty. Operand has 15 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-11 02:27:37,300 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2024-10-11 02:27:37,301 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:37,301 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2024-10-11 02:27:37,302 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:37,306 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:37,306 INFO L85 PathProgramCache]: Analyzing trace with hash -2070802916, now seen corresponding path program 1 times [2024-10-11 02:27:37,313 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:37,314 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [169363453] [2024-10-11 02:27:37,314 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:37,314 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:37,412 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:37,467 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:37,467 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:37,467 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [169363453] [2024-10-11 02:27:37,470 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [169363453] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:27:37,470 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:27:37,470 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-11 02:27:37,472 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1521745503] [2024-10-11 02:27:37,473 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:27:37,478 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-11 02:27:37,479 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:37,505 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-11 02:27:37,506 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-11 02:27:37,508 INFO L87 Difference]: Start difference. First operand has 15 states, 9 states have (on average 1.5555555555555556) internal successors, (14), 10 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:27:37,533 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:37,533 INFO L93 Difference]: Finished difference Result 29 states and 42 transitions. [2024-10-11 02:27:37,534 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-11 02:27:37,536 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2024-10-11 02:27:37,536 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:37,541 INFO L225 Difference]: With dead ends: 29 [2024-10-11 02:27:37,541 INFO L226 Difference]: Without dead ends: 13 [2024-10-11 02:27:37,543 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 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-11 02:27:37,548 INFO L432 NwaCegarLoop]: 16 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, 16 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-11 02:27:37,550 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 16 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:27:37,565 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13 states. [2024-10-11 02:27:37,593 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13 to 13. [2024-10-11 02:27:37,595 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 13 states, 8 states have (on average 1.375) internal successors, (11), 9 states have internal predecessors, (11), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:27:37,596 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 16 transitions. [2024-10-11 02:27:37,598 INFO L78 Accepts]: Start accepts. Automaton has 13 states and 16 transitions. Word has length 6 [2024-10-11 02:27:37,599 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:37,600 INFO L471 AbstractCegarLoop]: Abstraction has 13 states and 16 transitions. [2024-10-11 02:27:37,600 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 2.5) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:27:37,600 INFO L276 IsEmpty]: Start isEmpty. Operand 13 states and 16 transitions. [2024-10-11 02:27:37,602 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-10-11 02:27:37,602 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:37,602 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:37,603 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-11 02:27:37,603 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:37,604 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:37,604 INFO L85 PathProgramCache]: Analyzing trace with hash -170804699, now seen corresponding path program 1 times [2024-10-11 02:27:37,604 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:37,604 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1526701805] [2024-10-11 02:27:37,604 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:37,605 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:37,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:37,767 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:37,767 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:37,767 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1526701805] [2024-10-11 02:27:37,768 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1526701805] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:27:37,768 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:27:37,768 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-10-11 02:27:37,768 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1433192540] [2024-10-11 02:27:37,768 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:27:37,769 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-11 02:27:37,770 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:37,771 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-11 02:27:37,771 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-11 02:27:37,772 INFO L87 Difference]: Start difference. First operand 13 states and 16 transitions. Second operand has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:27:37,796 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:37,796 INFO L93 Difference]: Finished difference Result 23 states and 27 transitions. [2024-10-11 02:27:37,797 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-11 02:27:37,797 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-10-11 02:27:37,797 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:37,798 INFO L225 Difference]: With dead ends: 23 [2024-10-11 02:27:37,798 INFO L226 Difference]: Without dead ends: 15 [2024-10-11 02:27:37,798 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 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-11 02:27:37,799 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 0 mSDsluCounter, 25 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 38 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:37,800 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 38 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:27:37,804 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2024-10-11 02:27:37,808 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2024-10-11 02:27:37,808 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:27:37,810 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 18 transitions. [2024-10-11 02:27:37,810 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 18 transitions. Word has length 7 [2024-10-11 02:27:37,810 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:37,811 INFO L471 AbstractCegarLoop]: Abstraction has 15 states and 18 transitions. [2024-10-11 02:27:37,812 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:27:37,812 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 18 transitions. [2024-10-11 02:27:37,812 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-10-11 02:27:37,813 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:37,813 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:37,814 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-11 02:27:37,814 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:37,815 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:37,815 INFO L85 PathProgramCache]: Analyzing trace with hash -169017239, now seen corresponding path program 1 times [2024-10-11 02:27:37,815 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:37,815 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1507128908] [2024-10-11 02:27:37,815 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:37,816 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:37,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:27:37,845 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [634220717] [2024-10-11 02:27:37,845 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:37,846 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:37,847 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:37,848 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:37,850 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-10-11 02:27:37,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:37,917 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-11 02:27:37,924 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:38,022 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:38,022 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-11 02:27:38,022 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:38,023 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1507128908] [2024-10-11 02:27:38,023 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:27:38,023 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [634220717] [2024-10-11 02:27:38,024 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [634220717] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:27:38,024 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:27:38,024 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-10-11 02:27:38,027 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [89508290] [2024-10-11 02:27:38,028 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:27:38,028 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:27:38,029 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:38,029 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:27:38,029 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-11 02:27:38,030 INFO L87 Difference]: Start difference. First operand 15 states and 18 transitions. Second operand has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:27:38,103 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:38,103 INFO L93 Difference]: Finished difference Result 25 states and 30 transitions. [2024-10-11 02:27:38,104 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:27:38,104 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-10-11 02:27:38,104 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:38,105 INFO L225 Difference]: With dead ends: 25 [2024-10-11 02:27:38,105 INFO L226 Difference]: Without dead ends: 21 [2024-10-11 02:27:38,105 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 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-11 02:27:38,106 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 4 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:38,107 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 45 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:27:38,108 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2024-10-11 02:27:38,115 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2024-10-11 02:27:38,117 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-11 02:27:38,118 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 24 transitions. [2024-10-11 02:27:38,118 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 24 transitions. Word has length 7 [2024-10-11 02:27:38,119 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:38,119 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 24 transitions. [2024-10-11 02:27:38,119 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.2) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:27:38,119 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 24 transitions. [2024-10-11 02:27:38,120 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-10-11 02:27:38,121 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:38,121 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:38,137 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-11 02:27:38,325 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:38,326 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:38,326 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:38,327 INFO L85 PathProgramCache]: Analyzing trace with hash 867499275, now seen corresponding path program 1 times [2024-10-11 02:27:38,327 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:38,327 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [636502488] [2024-10-11 02:27:38,327 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:38,327 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:38,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:38,463 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-11 02:27:38,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:38,482 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:38,484 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:38,485 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [636502488] [2024-10-11 02:27:38,485 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [636502488] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:27:38,487 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [932075252] [2024-10-11 02:27:38,488 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:38,488 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:38,488 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:38,490 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:38,492 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-10-11 02:27:38,547 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:38,553 INFO L255 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-10-11 02:27:38,554 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:38,603 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:38,603 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:38,675 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:38,675 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [932075252] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:27:38,675 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:27:38,675 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-10-11 02:27:38,676 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [22823912] [2024-10-11 02:27:38,676 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:27:38,676 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-10-11 02:27:38,676 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:38,678 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-10-11 02:27:38,678 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-10-11 02:27:38,678 INFO L87 Difference]: Start difference. First operand 21 states and 24 transitions. Second operand has 10 states, 10 states have (on average 2.4) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-11 02:27:38,767 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:38,768 INFO L93 Difference]: Finished difference Result 55 states and 65 transitions. [2024-10-11 02:27:38,768 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-11 02:27:38,768 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 15 [2024-10-11 02:27:38,768 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:38,769 INFO L225 Difference]: With dead ends: 55 [2024-10-11 02:27:38,769 INFO L226 Difference]: Without dead ends: 47 [2024-10-11 02:27:38,770 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2024-10-11 02:27:38,771 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 23 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 61 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:38,771 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 61 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:27:38,772 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-10-11 02:27:38,779 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 43. [2024-10-11 02:27:38,780 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 28 states have (on average 1.25) internal successors, (35), 31 states have internal predecessors, (35), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-11 02:27:38,781 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 52 transitions. [2024-10-11 02:27:38,781 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 52 transitions. Word has length 15 [2024-10-11 02:27:38,781 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:38,782 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 52 transitions. [2024-10-11 02:27:38,782 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 10 states have internal predecessors, (24), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-11 02:27:38,782 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 52 transitions. [2024-10-11 02:27:38,782 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-10-11 02:27:38,782 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:38,782 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:38,795 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-10-11 02:27:38,984 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:38,984 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:38,985 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:38,985 INFO L85 PathProgramCache]: Analyzing trace with hash 869286735, now seen corresponding path program 1 times [2024-10-11 02:27:38,985 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:38,985 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [113499970] [2024-10-11 02:27:38,985 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:38,985 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:39,002 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:27:39,003 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [118574567] [2024-10-11 02:27:39,003 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:39,004 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:39,004 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:39,006 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:39,010 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-10-11 02:27:39,052 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:39,054 INFO L255 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-10-11 02:27:39,056 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:39,159 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:39,159 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:39,273 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:39,274 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:39,274 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [113499970] [2024-10-11 02:27:39,274 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:27:39,274 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [118574567] [2024-10-11 02:27:39,274 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [118574567] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:27:39,274 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:27:39,274 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6] total 11 [2024-10-11 02:27:39,275 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1978646640] [2024-10-11 02:27:39,275 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:27:39,275 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-10-11 02:27:39,275 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:39,276 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-10-11 02:27:39,276 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2024-10-11 02:27:39,276 INFO L87 Difference]: Start difference. First operand 43 states and 52 transitions. Second operand has 11 states, 11 states have (on average 2.0) internal successors, (22), 10 states have internal predecessors, (22), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:27:39,361 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:39,364 INFO L93 Difference]: Finished difference Result 57 states and 65 transitions. [2024-10-11 02:27:39,365 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-11 02:27:39,365 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.0) internal successors, (22), 10 states have internal predecessors, (22), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 15 [2024-10-11 02:27:39,366 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:39,367 INFO L225 Difference]: With dead ends: 57 [2024-10-11 02:27:39,369 INFO L226 Difference]: Without dead ends: 46 [2024-10-11 02:27:39,370 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2024-10-11 02:27:39,371 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 8 mSDsluCounter, 41 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 55 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:39,371 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 53 Invalid, 55 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:27:39,371 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-10-11 02:27:39,385 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 40. [2024-10-11 02:27:39,385 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 30 states have internal predecessors, (34), 5 states have call successors, (5), 5 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-11 02:27:39,386 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 43 transitions. [2024-10-11 02:27:39,387 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 43 transitions. Word has length 15 [2024-10-11 02:27:39,387 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:39,387 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 43 transitions. [2024-10-11 02:27:39,387 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.0) internal successors, (22), 10 states have internal predecessors, (22), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-11 02:27:39,387 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 43 transitions. [2024-10-11 02:27:39,388 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-10-11 02:27:39,388 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:39,388 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2024-10-11 02:27:39,405 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-10-11 02:27:39,592 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:39,593 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:39,593 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:39,593 INFO L85 PathProgramCache]: Analyzing trace with hash 24753612, now seen corresponding path program 1 times [2024-10-11 02:27:39,593 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:39,594 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [18392859] [2024-10-11 02:27:39,594 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:39,594 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:39,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:27:39,618 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [857477529] [2024-10-11 02:27:39,618 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:39,618 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:39,618 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:39,620 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:39,624 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-10-11 02:27:39,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:39,664 INFO L255 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-10-11 02:27:39,666 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:39,803 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 3 proven. 8 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-11 02:27:39,804 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:40,055 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 3 proven. 8 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-11 02:27:40,056 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:40,056 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [18392859] [2024-10-11 02:27:40,056 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:27:40,056 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [857477529] [2024-10-11 02:27:40,056 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [857477529] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:27:40,056 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:27:40,056 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2024-10-11 02:27:40,057 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [883579985] [2024-10-11 02:27:40,057 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:27:40,057 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-10-11 02:27:40,058 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:40,058 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-10-11 02:27:40,060 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2024-10-11 02:27:40,060 INFO L87 Difference]: Start difference. First operand 40 states and 43 transitions. Second operand has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 12 states have internal predecessors, (25), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-11 02:27:40,221 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:40,221 INFO L93 Difference]: Finished difference Result 48 states and 52 transitions. [2024-10-11 02:27:40,221 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-10-11 02:27:40,222 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 12 states have internal predecessors, (25), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 21 [2024-10-11 02:27:40,222 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:40,223 INFO L225 Difference]: With dead ends: 48 [2024-10-11 02:27:40,223 INFO L226 Difference]: Without dead ends: 42 [2024-10-11 02:27:40,223 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 25 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=66, Invalid=240, Unknown=0, NotChecked=0, Total=306 [2024-10-11 02:27:40,224 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 8 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 85 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 91 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 85 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:40,224 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 82 Invalid, 91 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 85 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:27:40,225 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-10-11 02:27:40,233 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2024-10-11 02:27:40,234 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 31 states have (on average 1.064516129032258) internal successors, (33), 31 states have internal predecessors, (33), 6 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-10-11 02:27:40,234 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 44 transitions. [2024-10-11 02:27:40,235 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 44 transitions. Word has length 21 [2024-10-11 02:27:40,235 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:40,235 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 44 transitions. [2024-10-11 02:27:40,235 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 12 states have internal predecessors, (25), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-11 02:27:40,236 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 44 transitions. [2024-10-11 02:27:40,236 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-10-11 02:27:40,237 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:40,237 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1] [2024-10-11 02:27:40,255 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-11 02:27:40,437 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-10-11 02:27:40,438 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:40,438 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:40,438 INFO L85 PathProgramCache]: Analyzing trace with hash -795795011, now seen corresponding path program 2 times [2024-10-11 02:27:40,438 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:40,438 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1125507444] [2024-10-11 02:27:40,438 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:40,439 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:40,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:40,677 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-11 02:27:40,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:40,683 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-10-11 02:27:40,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:40,687 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-11 02:27:40,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:40,692 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-11 02:27:40,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:40,702 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-11 02:27:40,706 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:40,706 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1125507444] [2024-10-11 02:27:40,707 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1125507444] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:27:40,707 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1012039897] [2024-10-11 02:27:40,707 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-11 02:27:40,707 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:40,707 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:40,710 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:40,713 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-10-11 02:27:40,769 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-11 02:27:40,770 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 02:27:40,771 INFO L255 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-11 02:27:40,773 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:40,845 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:40,845 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:40,972 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-11 02:27:40,973 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1012039897] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:27:40,973 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:27:40,973 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-10-11 02:27:40,973 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1469732145] [2024-10-11 02:27:40,973 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:27:40,974 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-11 02:27:40,974 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:40,975 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-11 02:27:40,975 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=144, Unknown=0, NotChecked=0, Total=240 [2024-10-11 02:27:40,976 INFO L87 Difference]: Start difference. First operand 42 states and 44 transitions. Second operand has 16 states, 16 states have (on average 3.1875) internal successors, (51), 16 states have internal predecessors, (51), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-10-11 02:27:41,208 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:41,208 INFO L93 Difference]: Finished difference Result 118 states and 124 transitions. [2024-10-11 02:27:41,209 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-10-11 02:27:41,209 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.1875) internal successors, (51), 16 states have internal predecessors, (51), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) Word has length 39 [2024-10-11 02:27:41,210 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:41,211 INFO L225 Difference]: With dead ends: 118 [2024-10-11 02:27:41,211 INFO L226 Difference]: Without dead ends: 113 [2024-10-11 02:27:41,212 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=196, Invalid=356, Unknown=0, NotChecked=0, Total=552 [2024-10-11 02:27:41,212 INFO L432 NwaCegarLoop]: 11 mSDtfsCounter, 97 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 97 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 73 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:41,213 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [97 Valid, 94 Invalid, 73 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:27:41,216 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113 states. [2024-10-11 02:27:41,236 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113 to 88. [2024-10-11 02:27:41,237 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 66 states have (on average 1.106060606060606) internal successors, (73), 66 states have internal predecessors, (73), 11 states have call successors, (11), 11 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-10-11 02:27:41,239 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 94 transitions. [2024-10-11 02:27:41,239 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 94 transitions. Word has length 39 [2024-10-11 02:27:41,239 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:41,239 INFO L471 AbstractCegarLoop]: Abstraction has 88 states and 94 transitions. [2024-10-11 02:27:41,240 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.1875) internal successors, (51), 16 states have internal predecessors, (51), 9 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-10-11 02:27:41,240 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 94 transitions. [2024-10-11 02:27:41,241 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-10-11 02:27:41,241 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:41,241 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1] [2024-10-11 02:27:41,261 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-10-11 02:27:41,447 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:41,448 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:41,448 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:41,449 INFO L85 PathProgramCache]: Analyzing trace with hash -1312813826, now seen corresponding path program 2 times [2024-10-11 02:27:41,449 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:41,449 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [726987158] [2024-10-11 02:27:41,449 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:41,449 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:41,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:27:41,481 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1725640120] [2024-10-11 02:27:41,481 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-11 02:27:41,481 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:41,482 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:41,484 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:41,486 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-10-11 02:27:41,536 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-11 02:27:41,536 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 02:27:41,537 INFO L255 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-10-11 02:27:41,539 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:41,736 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 9 proven. 53 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-11 02:27:41,736 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:42,055 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 9 proven. 53 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-11 02:27:42,056 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:42,056 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [726987158] [2024-10-11 02:27:42,056 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:27:42,056 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1725640120] [2024-10-11 02:27:42,057 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1725640120] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:27:42,057 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:27:42,057 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 12] total 22 [2024-10-11 02:27:42,057 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1577818053] [2024-10-11 02:27:42,057 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:27:42,058 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-10-11 02:27:42,058 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:42,059 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-10-11 02:27:42,059 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=381, Unknown=0, NotChecked=0, Total=462 [2024-10-11 02:27:42,060 INFO L87 Difference]: Start difference. First operand 88 states and 94 transitions. Second operand has 22 states, 20 states have (on average 2.25) internal successors, (45), 19 states have internal predecessors, (45), 12 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-10-11 02:27:42,388 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:42,389 INFO L93 Difference]: Finished difference Result 94 states and 99 transitions. [2024-10-11 02:27:42,389 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-11 02:27:42,389 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 2.25) internal successors, (45), 19 states have internal predecessors, (45), 12 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 45 [2024-10-11 02:27:42,390 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:42,392 INFO L225 Difference]: With dead ends: 94 [2024-10-11 02:27:42,392 INFO L226 Difference]: Without dead ends: 88 [2024-10-11 02:27:42,392 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 68 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=139, Invalid=617, Unknown=0, NotChecked=0, Total=756 [2024-10-11 02:27:42,393 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 13 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 164 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 205 SdHoareTripleChecker+Invalid, 170 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 164 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:42,393 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 205 Invalid, 170 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 164 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-11 02:27:42,394 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2024-10-11 02:27:42,418 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 88. [2024-10-11 02:27:42,419 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 66 states have (on average 1.0151515151515151) internal successors, (67), 66 states have internal predecessors, (67), 11 states have call successors, (11), 11 states have call predecessors, (11), 10 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-10-11 02:27:42,419 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 88 transitions. [2024-10-11 02:27:42,420 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 88 transitions. Word has length 45 [2024-10-11 02:27:42,420 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:42,420 INFO L471 AbstractCegarLoop]: Abstraction has 88 states and 88 transitions. [2024-10-11 02:27:42,420 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 2.25) internal successors, (45), 19 states have internal predecessors, (45), 12 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-10-11 02:27:42,420 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 88 transitions. [2024-10-11 02:27:42,423 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-10-11 02:27:42,425 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:42,425 INFO L215 NwaCegarLoop]: trace histogram [11, 11, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1] [2024-10-11 02:27:42,442 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-10-11 02:27:42,625 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-10-11 02:27:42,626 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:42,626 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:42,626 INFO L85 PathProgramCache]: Analyzing trace with hash 1242040609, now seen corresponding path program 3 times [2024-10-11 02:27:42,626 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:42,626 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [38032758] [2024-10-11 02:27:42,626 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:42,627 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:42,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:43,003 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-11 02:27:43,006 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:43,010 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-10-11 02:27:43,012 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:43,016 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-11 02:27:43,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:43,020 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-11 02:27:43,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:43,024 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-10-11 02:27:43,025 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:43,027 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-10-11 02:27:43,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:43,030 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2024-10-11 02:27:43,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:43,038 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-10-11 02:27:43,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:43,043 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 67 [2024-10-11 02:27:43,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:43,046 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 75 [2024-10-11 02:27:43,048 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:43,050 INFO L134 CoverageAnalysis]: Checked inductivity of 400 backedges. 20 proven. 200 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-10-11 02:27:43,050 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:43,050 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [38032758] [2024-10-11 02:27:43,051 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [38032758] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:27:43,051 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [305279410] [2024-10-11 02:27:43,051 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-11 02:27:43,051 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:43,051 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:43,053 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:43,054 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-10-11 02:27:43,143 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2024-10-11 02:27:43,143 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 02:27:43,145 INFO L255 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-10-11 02:27:43,148 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:43,268 INFO L134 CoverageAnalysis]: Checked inductivity of 400 backedges. 20 proven. 380 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:43,269 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:43,596 INFO L134 CoverageAnalysis]: Checked inductivity of 400 backedges. 20 proven. 200 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2024-10-11 02:27:43,596 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [305279410] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:27:43,596 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:27:43,596 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13, 14] total 28 [2024-10-11 02:27:43,596 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [750257508] [2024-10-11 02:27:43,596 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:27:43,597 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-10-11 02:27:43,597 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:43,599 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-10-11 02:27:43,599 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=330, Invalid=426, Unknown=0, NotChecked=0, Total=756 [2024-10-11 02:27:43,600 INFO L87 Difference]: Start difference. First operand 88 states and 88 transitions. Second operand has 28 states, 28 states have (on average 3.75) internal successors, (105), 28 states have internal predecessors, (105), 21 states have call successors, (31), 12 states have call predecessors, (31), 11 states have return successors, (30), 20 states have call predecessors, (30), 20 states have call successors, (30) [2024-10-11 02:27:44,092 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:44,093 INFO L93 Difference]: Finished difference Result 189 states and 200 transitions. [2024-10-11 02:27:44,093 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2024-10-11 02:27:44,094 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 3.75) internal successors, (105), 28 states have internal predecessors, (105), 21 states have call successors, (31), 12 states have call predecessors, (31), 11 states have return successors, (30), 20 states have call predecessors, (30), 20 states have call successors, (30) Word has length 87 [2024-10-11 02:27:44,094 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:44,095 INFO L225 Difference]: With dead ends: 189 [2024-10-11 02:27:44,095 INFO L226 Difference]: Without dead ends: 184 [2024-10-11 02:27:44,097 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 226 GetRequests, 180 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 330 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=820, Invalid=1436, Unknown=0, NotChecked=0, Total=2256 [2024-10-11 02:27:44,098 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 77 mSDsluCounter, 128 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:44,098 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [77 Valid, 138 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:27:44,099 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2024-10-11 02:27:44,140 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 184. [2024-10-11 02:27:44,142 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 184 states, 138 states have (on average 1.0072463768115942) internal successors, (139), 138 states have internal predecessors, (139), 23 states have call successors, (23), 23 states have call predecessors, (23), 22 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2024-10-11 02:27:44,146 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 184 states to 184 states and 184 transitions. [2024-10-11 02:27:44,146 INFO L78 Accepts]: Start accepts. Automaton has 184 states and 184 transitions. Word has length 87 [2024-10-11 02:27:44,147 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:44,147 INFO L471 AbstractCegarLoop]: Abstraction has 184 states and 184 transitions. [2024-10-11 02:27:44,147 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 3.75) internal successors, (105), 28 states have internal predecessors, (105), 21 states have call successors, (31), 12 states have call predecessors, (31), 11 states have return successors, (30), 20 states have call predecessors, (30), 20 states have call successors, (30) [2024-10-11 02:27:44,147 INFO L276 IsEmpty]: Start isEmpty. Operand 184 states and 184 transitions. [2024-10-11 02:27:44,149 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 184 [2024-10-11 02:27:44,153 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:44,153 INFO L215 NwaCegarLoop]: trace histogram [23, 23, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1] [2024-10-11 02:27:44,172 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-10-11 02:27:44,357 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:44,358 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:44,359 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:44,359 INFO L85 PathProgramCache]: Analyzing trace with hash 539512809, now seen corresponding path program 4 times [2024-10-11 02:27:44,359 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:44,359 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1850377306] [2024-10-11 02:27:44,359 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:44,360 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:44,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,711 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-11 02:27:45,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,715 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-10-11 02:27:45,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,718 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-11 02:27:45,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,721 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-11 02:27:45,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,724 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-10-11 02:27:45,725 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,727 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-10-11 02:27:45,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,729 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2024-10-11 02:27:45,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,733 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-10-11 02:27:45,734 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,736 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 67 [2024-10-11 02:27:45,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,739 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 75 [2024-10-11 02:27:45,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,748 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-10-11 02:27:45,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,751 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 91 [2024-10-11 02:27:45,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,757 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 99 [2024-10-11 02:27:45,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,760 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 107 [2024-10-11 02:27:45,763 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,765 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 115 [2024-10-11 02:27:45,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,769 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 123 [2024-10-11 02:27:45,772 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,774 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 131 [2024-10-11 02:27:45,775 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,776 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 139 [2024-10-11 02:27:45,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,780 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 147 [2024-10-11 02:27:45,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,784 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 155 [2024-10-11 02:27:45,786 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,788 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 163 [2024-10-11 02:27:45,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,792 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 171 [2024-10-11 02:27:45,793 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:45,795 INFO L134 CoverageAnalysis]: Checked inductivity of 1936 backedges. 44 proven. 968 refuted. 0 times theorem prover too weak. 924 trivial. 0 not checked. [2024-10-11 02:27:45,796 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:45,796 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1850377306] [2024-10-11 02:27:45,796 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1850377306] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:27:45,796 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1106467076] [2024-10-11 02:27:45,796 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-10-11 02:27:45,796 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:45,797 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:45,798 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:45,799 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-10-11 02:27:46,421 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-10-11 02:27:46,421 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 02:27:46,425 INFO L255 TraceCheckSpWp]: Trace formula consists of 507 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-10-11 02:27:46,430 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:46,684 INFO L134 CoverageAnalysis]: Checked inductivity of 1936 backedges. 44 proven. 1892 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:46,685 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:47,601 INFO L134 CoverageAnalysis]: Checked inductivity of 1936 backedges. 44 proven. 968 refuted. 0 times theorem prover too weak. 924 trivial. 0 not checked. [2024-10-11 02:27:47,601 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1106467076] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:27:47,601 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:27:47,601 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 25, 26] total 52 [2024-10-11 02:27:47,601 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [814487926] [2024-10-11 02:27:47,602 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:27:47,603 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 52 states [2024-10-11 02:27:47,603 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:47,605 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 52 interpolants. [2024-10-11 02:27:47,606 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1230, Invalid=1422, Unknown=0, NotChecked=0, Total=2652 [2024-10-11 02:27:47,607 INFO L87 Difference]: Start difference. First operand 184 states and 184 transitions. Second operand has 52 states, 52 states have (on average 4.096153846153846) internal successors, (213), 52 states have internal predecessors, (213), 45 states have call successors, (67), 24 states have call predecessors, (67), 23 states have return successors, (66), 44 states have call predecessors, (66), 44 states have call successors, (66) [2024-10-11 02:27:48,957 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:48,957 INFO L93 Difference]: Finished difference Result 381 states and 404 transitions. [2024-10-11 02:27:48,957 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2024-10-11 02:27:48,958 INFO L78 Accepts]: Start accepts. Automaton has has 52 states, 52 states have (on average 4.096153846153846) internal successors, (213), 52 states have internal predecessors, (213), 45 states have call successors, (67), 24 states have call predecessors, (67), 23 states have return successors, (66), 44 states have call predecessors, (66), 44 states have call successors, (66) Word has length 183 [2024-10-11 02:27:48,959 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:48,962 INFO L225 Difference]: With dead ends: 381 [2024-10-11 02:27:48,962 INFO L226 Difference]: Without dead ends: 376 [2024-10-11 02:27:48,964 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 478 GetRequests, 384 SyntacticMatches, 0 SemanticMatches, 94 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1380 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=3364, Invalid=5756, Unknown=0, NotChecked=0, Total=9120 [2024-10-11 02:27:48,965 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 221 mSDsluCounter, 220 mSDsCounter, 0 mSdLazyCounter, 197 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 221 SdHoareTripleChecker+Valid, 230 SdHoareTripleChecker+Invalid, 240 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 197 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:48,966 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [221 Valid, 230 Invalid, 240 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 197 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-11 02:27:48,967 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 376 states. [2024-10-11 02:27:49,036 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 376 to 376. [2024-10-11 02:27:49,037 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 376 states, 282 states have (on average 1.00354609929078) internal successors, (283), 282 states have internal predecessors, (283), 47 states have call successors, (47), 47 states have call predecessors, (47), 46 states have return successors, (46), 46 states have call predecessors, (46), 46 states have call successors, (46) [2024-10-11 02:27:49,040 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 376 states to 376 states and 376 transitions. [2024-10-11 02:27:49,040 INFO L78 Accepts]: Start accepts. Automaton has 376 states and 376 transitions. Word has length 183 [2024-10-11 02:27:49,041 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:49,041 INFO L471 AbstractCegarLoop]: Abstraction has 376 states and 376 transitions. [2024-10-11 02:27:49,042 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 52 states, 52 states have (on average 4.096153846153846) internal successors, (213), 52 states have internal predecessors, (213), 45 states have call successors, (67), 24 states have call predecessors, (67), 23 states have return successors, (66), 44 states have call predecessors, (66), 44 states have call successors, (66) [2024-10-11 02:27:49,042 INFO L276 IsEmpty]: Start isEmpty. Operand 376 states and 376 transitions. [2024-10-11 02:27:49,056 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 376 [2024-10-11 02:27:49,057 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:49,057 INFO L215 NwaCegarLoop]: trace histogram [47, 47, 46, 46, 46, 46, 46, 46, 1, 1, 1, 1, 1] [2024-10-11 02:27:49,072 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-10-11 02:27:49,257 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-10-11 02:27:49,258 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:49,258 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:49,259 INFO L85 PathProgramCache]: Analyzing trace with hash -890061447, now seen corresponding path program 5 times [2024-10-11 02:27:49,259 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:49,259 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [289862435] [2024-10-11 02:27:49,259 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:49,259 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:49,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,643 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-11 02:27:52,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,647 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-10-11 02:27:52,648 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,650 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-11 02:27:52,651 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,653 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-11 02:27:52,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,656 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-10-11 02:27:52,657 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,659 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-10-11 02:27:52,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,662 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2024-10-11 02:27:52,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,665 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-10-11 02:27:52,666 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,668 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 67 [2024-10-11 02:27:52,669 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,671 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 75 [2024-10-11 02:27:52,672 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,674 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-10-11 02:27:52,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,676 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 91 [2024-10-11 02:27:52,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,679 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 99 [2024-10-11 02:27:52,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,682 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 107 [2024-10-11 02:27:52,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,685 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 115 [2024-10-11 02:27:52,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,688 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 123 [2024-10-11 02:27:52,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,691 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 131 [2024-10-11 02:27:52,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,694 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 139 [2024-10-11 02:27:52,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,697 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 147 [2024-10-11 02:27:52,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,700 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 155 [2024-10-11 02:27:52,702 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,703 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 163 [2024-10-11 02:27:52,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,706 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 171 [2024-10-11 02:27:52,707 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,710 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 179 [2024-10-11 02:27:52,711 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,713 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 187 [2024-10-11 02:27:52,714 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,716 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 195 [2024-10-11 02:27:52,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,719 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 203 [2024-10-11 02:27:52,720 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,722 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 211 [2024-10-11 02:27:52,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,725 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 219 [2024-10-11 02:27:52,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,728 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 227 [2024-10-11 02:27:52,729 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,731 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 235 [2024-10-11 02:27:52,732 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,734 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 243 [2024-10-11 02:27:52,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,739 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 251 [2024-10-11 02:27:52,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,742 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 259 [2024-10-11 02:27:52,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,746 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 267 [2024-10-11 02:27:52,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,749 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 275 [2024-10-11 02:27:52,751 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,753 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 283 [2024-10-11 02:27:52,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,756 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 291 [2024-10-11 02:27:52,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,760 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 299 [2024-10-11 02:27:52,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,763 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 307 [2024-10-11 02:27:52,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,766 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 315 [2024-10-11 02:27:52,767 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,769 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 323 [2024-10-11 02:27:52,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,772 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 331 [2024-10-11 02:27:52,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,776 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 339 [2024-10-11 02:27:52,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,780 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 347 [2024-10-11 02:27:52,782 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,784 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 355 [2024-10-11 02:27:52,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,787 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 363 [2024-10-11 02:27:52,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:27:52,794 INFO L134 CoverageAnalysis]: Checked inductivity of 8464 backedges. 92 proven. 4232 refuted. 0 times theorem prover too weak. 4140 trivial. 0 not checked. [2024-10-11 02:27:52,795 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:27:52,795 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [289862435] [2024-10-11 02:27:52,795 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [289862435] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:27:52,795 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1916080073] [2024-10-11 02:27:52,795 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-10-11 02:27:52,796 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:52,796 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:52,797 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:52,799 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-10-11 02:27:54,501 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 47 check-sat command(s) [2024-10-11 02:27:54,501 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-11 02:27:54,508 INFO L255 TraceCheckSpWp]: Trace formula consists of 1011 conjuncts, 95 conjuncts are in the unsatisfiable core [2024-10-11 02:27:54,518 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:27:55,008 INFO L134 CoverageAnalysis]: Checked inductivity of 8464 backedges. 92 proven. 8372 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-11 02:27:55,009 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:27:56,333 INFO L134 CoverageAnalysis]: Checked inductivity of 8464 backedges. 92 proven. 4232 refuted. 0 times theorem prover too weak. 4140 trivial. 0 not checked. [2024-10-11 02:27:56,334 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1916080073] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:27:56,334 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:27:56,334 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [51, 49, 50] total 56 [2024-10-11 02:27:56,334 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1883530969] [2024-10-11 02:27:56,334 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:27:56,335 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 56 states [2024-10-11 02:27:56,335 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:27:56,337 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 56 interpolants. [2024-10-11 02:27:56,338 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1436, Invalid=1644, Unknown=0, NotChecked=0, Total=3080 [2024-10-11 02:27:56,338 INFO L87 Difference]: Start difference. First operand 376 states and 376 transitions. Second operand has 56 states, 56 states have (on average 5.357142857142857) internal successors, (300), 56 states have internal predecessors, (300), 50 states have call successors, (96), 48 states have call predecessors, (96), 47 states have return successors, (95), 49 states have call predecessors, (95), 49 states have call successors, (95) [2024-10-11 02:27:57,707 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:27:57,708 INFO L93 Difference]: Finished difference Result 413 states and 416 transitions. [2024-10-11 02:27:57,708 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 102 states. [2024-10-11 02:27:57,709 INFO L78 Accepts]: Start accepts. Automaton has has 56 states, 56 states have (on average 5.357142857142857) internal successors, (300), 56 states have internal predecessors, (300), 50 states have call successors, (96), 48 states have call predecessors, (96), 47 states have return successors, (95), 49 states have call predecessors, (95), 49 states have call successors, (95) Word has length 375 [2024-10-11 02:27:57,710 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:27:57,718 INFO L225 Difference]: With dead ends: 413 [2024-10-11 02:27:57,718 INFO L226 Difference]: Without dead ends: 408 [2024-10-11 02:27:57,721 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 938 GetRequests, 792 SyntacticMatches, 44 SemanticMatches, 102 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2538 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=3978, Invalid=6734, Unknown=0, NotChecked=0, Total=10712 [2024-10-11 02:27:57,723 INFO L432 NwaCegarLoop]: 10 mSDtfsCounter, 15 mSDsluCounter, 223 mSDsCounter, 0 mSdLazyCounter, 206 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 233 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 206 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-11 02:27:57,724 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 233 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 206 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-11 02:27:57,725 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 408 states. [2024-10-11 02:27:57,787 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 408 to 408. [2024-10-11 02:27:57,787 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 408 states, 306 states have (on average 1.0032679738562091) internal successors, (307), 306 states have internal predecessors, (307), 51 states have call successors, (51), 51 states have call predecessors, (51), 50 states have return successors, (50), 50 states have call predecessors, (50), 50 states have call successors, (50) [2024-10-11 02:27:57,789 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 408 states to 408 states and 408 transitions. [2024-10-11 02:27:57,789 INFO L78 Accepts]: Start accepts. Automaton has 408 states and 408 transitions. Word has length 375 [2024-10-11 02:27:57,790 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:27:57,790 INFO L471 AbstractCegarLoop]: Abstraction has 408 states and 408 transitions. [2024-10-11 02:27:57,791 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 56 states, 56 states have (on average 5.357142857142857) internal successors, (300), 56 states have internal predecessors, (300), 50 states have call successors, (96), 48 states have call predecessors, (96), 47 states have return successors, (95), 49 states have call predecessors, (95), 49 states have call successors, (95) [2024-10-11 02:27:57,791 INFO L276 IsEmpty]: Start isEmpty. Operand 408 states and 408 transitions. [2024-10-11 02:27:57,797 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 408 [2024-10-11 02:27:57,798 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:27:57,798 INFO L215 NwaCegarLoop]: trace histogram [51, 51, 50, 50, 50, 50, 50, 50, 1, 1, 1, 1, 1] [2024-10-11 02:27:57,809 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-10-11 02:27:57,998 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:57,999 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:27:57,999 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:27:57,999 INFO L85 PathProgramCache]: Analyzing trace with hash -1280322287, now seen corresponding path program 6 times [2024-10-11 02:27:57,999 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:27:57,999 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [43068680] [2024-10-11 02:27:57,999 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:27:57,999 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:27:58,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:27:58,221 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1169535974] [2024-10-11 02:27:58,221 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-10-11 02:27:58,221 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:27:58,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:27:58,226 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:27:58,229 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process