./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursive/Addition03-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursive/Addition03-1.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 2b4726bd085117d6d28f7ec87f442bbec9d0d87c17bc39b8147695c8c5a6ec7b --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-08 15:17:28,791 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-08 15:17:28,862 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-08 15:17:28,866 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-08 15:17:28,867 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-08 15:17:28,897 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-08 15:17:28,898 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-08 15:17:28,898 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-08 15:17:28,899 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-08 15:17:28,899 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-08 15:17:28,900 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-08 15:17:28,900 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-08 15:17:28,900 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-08 15:17:28,902 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-08 15:17:28,902 INFO L153 SettingsManager]: * Use SBE=true [2024-11-08 15:17:28,903 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-08 15:17:28,903 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-08 15:17:28,903 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-08 15:17:28,903 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-08 15:17:28,903 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-08 15:17:28,904 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-08 15:17:28,904 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-08 15:17:28,905 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-08 15:17:28,905 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-08 15:17:28,905 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-08 15:17:28,906 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-08 15:17:28,906 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-08 15:17:28,906 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-08 15:17:28,906 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-08 15:17:28,907 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-08 15:17:28,907 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-08 15:17:28,907 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-08 15:17:28,907 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 15:17:28,907 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-08 15:17:28,907 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-08 15:17:28,908 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-08 15:17:28,908 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-08 15:17:28,908 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-08 15:17:28,908 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-08 15:17:28,908 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-08 15:17:28,908 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-08 15:17:28,908 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-08 15:17:28,909 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 2b4726bd085117d6d28f7ec87f442bbec9d0d87c17bc39b8147695c8c5a6ec7b [2024-11-08 15:17:29,137 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-08 15:17:29,154 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-08 15:17:29,157 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-08 15:17:29,158 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-08 15:17:29,159 INFO L274 PluginConnector]: CDTParser initialized [2024-11-08 15:17:29,160 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Addition03-1.c [2024-11-08 15:17:30,412 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-08 15:17:30,560 INFO L384 CDTParser]: Found 1 translation units. [2024-11-08 15:17:30,561 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Addition03-1.c [2024-11-08 15:17:30,566 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/25ed1ac36/c46fda1027de46249bb7d502e9afb658/FLAGf6098b937 [2024-11-08 15:17:30,982 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/25ed1ac36/c46fda1027de46249bb7d502e9afb658 [2024-11-08 15:17:30,985 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-08 15:17:30,986 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-08 15:17:30,991 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-08 15:17:30,991 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-08 15:17:30,995 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-08 15:17:30,996 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 03:17:30" (1/1) ... [2024-11-08 15:17:30,996 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@ee89db0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:30, skipping insertion in model container [2024-11-08 15:17:30,996 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 03:17:30" (1/1) ... [2024-11-08 15:17:31,014 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-08 15:17:31,159 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Addition03-1.c[840,853] [2024-11-08 15:17:31,163 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 15:17:31,171 INFO L200 MainTranslator]: Completed pre-run [2024-11-08 15:17:31,183 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Addition03-1.c[840,853] [2024-11-08 15:17:31,184 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 15:17:31,196 INFO L204 MainTranslator]: Completed translation [2024-11-08 15:17:31,196 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31 WrapperNode [2024-11-08 15:17:31,196 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-08 15:17:31,197 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-08 15:17:31,197 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-08 15:17:31,197 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-08 15:17:31,203 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31" (1/1) ... [2024-11-08 15:17:31,207 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31" (1/1) ... [2024-11-08 15:17:31,219 INFO L138 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 27 [2024-11-08 15:17:31,219 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-08 15:17:31,220 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-08 15:17:31,220 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-08 15:17:31,220 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-08 15:17:31,229 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31" (1/1) ... [2024-11-08 15:17:31,229 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31" (1/1) ... [2024-11-08 15:17:31,230 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31" (1/1) ... [2024-11-08 15:17:31,238 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-08 15:17:31,239 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31" (1/1) ... [2024-11-08 15:17:31,239 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31" (1/1) ... [2024-11-08 15:17:31,240 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31" (1/1) ... [2024-11-08 15:17:31,242 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31" (1/1) ... [2024-11-08 15:17:31,243 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31" (1/1) ... [2024-11-08 15:17:31,243 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31" (1/1) ... [2024-11-08 15:17:31,244 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-08 15:17:31,245 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-08 15:17:31,245 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-08 15:17:31,245 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-08 15:17:31,249 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31" (1/1) ... [2024-11-08 15:17:31,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 15:17:31,261 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:17:31,274 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-08 15:17:31,280 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-08 15:17:31,314 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-08 15:17:31,314 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-08 15:17:31,314 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-08 15:17:31,315 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-08 15:17:31,315 INFO L130 BoogieDeclarations]: Found specification of procedure addition [2024-11-08 15:17:31,315 INFO L138 BoogieDeclarations]: Found implementation of procedure addition [2024-11-08 15:17:31,363 INFO L238 CfgBuilder]: Building ICFG [2024-11-08 15:17:31,364 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-08 15:17:31,459 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-11-08 15:17:31,460 INFO L287 CfgBuilder]: Performing block encoding [2024-11-08 15:17:31,469 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-08 15:17:31,469 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-08 15:17:31,469 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 03:17:31 BoogieIcfgContainer [2024-11-08 15:17:31,470 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-08 15:17:31,471 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-08 15:17:31,471 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-08 15:17:31,474 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-08 15:17:31,474 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.11 03:17:30" (1/3) ... [2024-11-08 15:17:31,475 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7a27d0b4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 03:17:31, skipping insertion in model container [2024-11-08 15:17:31,475 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 03:17:31" (2/3) ... [2024-11-08 15:17:31,475 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7a27d0b4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 03:17:31, skipping insertion in model container [2024-11-08 15:17:31,475 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 03:17:31" (3/3) ... [2024-11-08 15:17:31,477 INFO L112 eAbstractionObserver]: Analyzing ICFG Addition03-1.c [2024-11-08 15:17:31,490 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-08 15:17:31,491 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-08 15:17:31,540 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-08 15:17:31,545 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;@4e819389, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-08 15:17:31,546 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-08 15:17:31,549 INFO L276 IsEmpty]: Start isEmpty. Operand has 20 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 15 states have internal predecessors, (19), 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-11-08 15:17:31,554 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-08 15:17:31,555 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:17:31,555 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:17:31,555 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:17:31,559 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:17:31,560 INFO L85 PathProgramCache]: Analyzing trace with hash -100249854, now seen corresponding path program 1 times [2024-11-08 15:17:31,567 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:17:31,567 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1773776160] [2024-11-08 15:17:31,568 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:17:31,568 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:17:31,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:31,819 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:17:31,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:31,881 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-08 15:17:31,882 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:17:31,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1773776160] [2024-11-08 15:17:31,885 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1773776160] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 15:17:31,886 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 15:17:31,886 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 15:17:31,887 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1443481133] [2024-11-08 15:17:31,889 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 15:17:31,892 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 15:17:31,893 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:17:31,914 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 15:17:31,915 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 15:17:31,916 INFO L87 Difference]: Start difference. First operand has 20 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 15 states have internal predecessors, (19), 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 5 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-08 15:17:32,022 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:17:32,022 INFO L93 Difference]: Finished difference Result 31 states and 40 transitions. [2024-11-08 15:17:32,024 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 15:17:32,025 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 10 [2024-11-08 15:17:32,026 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:17:32,031 INFO L225 Difference]: With dead ends: 31 [2024-11-08 15:17:32,031 INFO L226 Difference]: Without dead ends: 21 [2024-11-08 15:17:32,033 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 15:17:32,036 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 7 mSDsluCounter, 30 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 15:17:32,037 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 45 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 15:17:32,052 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2024-11-08 15:17:32,066 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 19. [2024-11-08 15:17:32,067 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 14 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-08 15:17:32,068 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 24 transitions. [2024-11-08 15:17:32,069 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 24 transitions. Word has length 10 [2024-11-08 15:17:32,069 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:17:32,070 INFO L471 AbstractCegarLoop]: Abstraction has 19 states and 24 transitions. [2024-11-08 15:17:32,070 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-08 15:17:32,070 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 24 transitions. [2024-11-08 15:17:32,071 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-08 15:17:32,071 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:17:32,071 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:17:32,072 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-08 15:17:32,072 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:17:32,072 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:17:32,072 INFO L85 PathProgramCache]: Analyzing trace with hash -2083914533, now seen corresponding path program 1 times [2024-11-08 15:17:32,073 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:17:32,073 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2089527345] [2024-11-08 15:17:32,073 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:17:32,073 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:17:32,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:32,110 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:17:32,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:32,187 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-08 15:17:32,187 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:17:32,188 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2089527345] [2024-11-08 15:17:32,188 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2089527345] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 15:17:32,188 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 15:17:32,188 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-08 15:17:32,188 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [518040176] [2024-11-08 15:17:32,188 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 15:17:32,189 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-08 15:17:32,189 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:17:32,190 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-08 15:17:32,190 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-08 15:17:32,190 INFO L87 Difference]: Start difference. First operand 19 states and 24 transitions. Second operand has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-08 15:17:32,219 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:17:32,219 INFO L93 Difference]: Finished difference Result 29 states and 37 transitions. [2024-11-08 15:17:32,219 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-08 15:17:32,219 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2024-11-08 15:17:32,220 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:17:32,220 INFO L225 Difference]: With dead ends: 29 [2024-11-08 15:17:32,220 INFO L226 Difference]: Without dead ends: 21 [2024-11-08 15:17:32,221 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-08 15:17:32,222 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 6 mSDsluCounter, 22 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 15:17:32,222 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 44 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 15:17:32,223 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2024-11-08 15:17:32,227 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 19. [2024-11-08 15:17:32,227 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-08 15:17:32,228 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 23 transitions. [2024-11-08 15:17:32,228 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 23 transitions. Word has length 12 [2024-11-08 15:17:32,228 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:17:32,229 INFO L471 AbstractCegarLoop]: Abstraction has 19 states and 23 transitions. [2024-11-08 15:17:32,229 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-08 15:17:32,229 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 23 transitions. [2024-11-08 15:17:32,229 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-08 15:17:32,230 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:17:32,230 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:17:32,230 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-08 15:17:32,230 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:17:32,230 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:17:32,230 INFO L85 PathProgramCache]: Analyzing trace with hash 1402250658, now seen corresponding path program 1 times [2024-11-08 15:17:32,230 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:17:32,231 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1822850551] [2024-11-08 15:17:32,231 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:17:32,231 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:17:32,241 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:32,288 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:17:32,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:32,353 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:32,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:32,383 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-08 15:17:32,384 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:17:32,384 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1822850551] [2024-11-08 15:17:32,384 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1822850551] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:17:32,384 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [423407741] [2024-11-08 15:17:32,384 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:17:32,385 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:17:32,385 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:17:32,387 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:17:32,389 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-08 15:17:32,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:32,445 INFO L255 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-08 15:17:32,452 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:17:32,530 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-08 15:17:32,531 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:17:32,748 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-08 15:17:32,748 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [423407741] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 15:17:32,749 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 15:17:32,749 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6, 7] total 13 [2024-11-08 15:17:32,749 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [427278375] [2024-11-08 15:17:32,749 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 15:17:32,749 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-08 15:17:32,750 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:17:32,750 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-08 15:17:32,751 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=111, Unknown=0, NotChecked=0, Total=156 [2024-11-08 15:17:32,751 INFO L87 Difference]: Start difference. First operand 19 states and 23 transitions. Second operand has 13 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 4 states have call successors, (4), 1 states have call predecessors, (4), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-08 15:17:32,883 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:17:32,883 INFO L93 Difference]: Finished difference Result 54 states and 75 transitions. [2024-11-08 15:17:32,884 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-08 15:17:32,884 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 4 states have call successors, (4), 1 states have call predecessors, (4), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 17 [2024-11-08 15:17:32,884 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:17:32,885 INFO L225 Difference]: With dead ends: 54 [2024-11-08 15:17:32,885 INFO L226 Difference]: Without dead ends: 34 [2024-11-08 15:17:32,886 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 29 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=75, Invalid=165, Unknown=0, NotChecked=0, Total=240 [2024-11-08 15:17:32,887 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 22 mSDsluCounter, 49 mSDsCounter, 0 mSdLazyCounter, 116 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 63 SdHoareTripleChecker+Invalid, 136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 116 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 15:17:32,887 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 63 Invalid, 136 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 116 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 15:17:32,888 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2024-11-08 15:17:32,893 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 32. [2024-11-08 15:17:32,893 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 23 states have internal predecessors, (28), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (8), 5 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-08 15:17:32,894 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 40 transitions. [2024-11-08 15:17:32,894 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 40 transitions. Word has length 17 [2024-11-08 15:17:32,894 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:17:32,894 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 40 transitions. [2024-11-08 15:17:32,894 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 4 states have call successors, (4), 1 states have call predecessors, (4), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-08 15:17:32,895 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 40 transitions. [2024-11-08 15:17:32,895 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-08 15:17:32,895 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:17:32,896 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:17:32,909 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-08 15:17:33,099 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:17:33,100 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:17:33,100 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:17:33,100 INFO L85 PathProgramCache]: Analyzing trace with hash -1901242716, now seen corresponding path program 2 times [2024-11-08 15:17:33,100 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:17:33,100 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1061110076] [2024-11-08 15:17:33,100 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:17:33,100 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:17:33,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:33,173 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:17:33,178 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:33,222 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:33,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:33,263 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:33,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:33,288 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:33,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:33,323 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-08 15:17:33,324 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:17:33,324 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1061110076] [2024-11-08 15:17:33,324 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1061110076] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:17:33,324 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [4944393] [2024-11-08 15:17:33,326 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 15:17:33,326 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:17:33,326 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:17:33,328 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:17:33,329 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-08 15:17:33,376 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 15:17:33,376 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 15:17:33,380 INFO L255 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-08 15:17:33,382 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:17:33,453 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-08 15:17:33,454 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:17:33,928 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-08 15:17:33,929 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [4944393] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 15:17:33,929 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 15:17:33,929 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 11] total 17 [2024-11-08 15:17:33,929 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [10771214] [2024-11-08 15:17:33,929 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 15:17:33,929 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-08 15:17:33,929 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:17:33,930 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-08 15:17:33,930 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=195, Unknown=0, NotChecked=0, Total=272 [2024-11-08 15:17:33,930 INFO L87 Difference]: Start difference. First operand 32 states and 40 transitions. Second operand has 17 states, 17 states have (on average 2.176470588235294) internal successors, (37), 17 states have internal predecessors, (37), 6 states have call successors, (6), 1 states have call predecessors, (6), 6 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) [2024-11-08 15:17:34,074 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:17:34,074 INFO L93 Difference]: Finished difference Result 46 states and 57 transitions. [2024-11-08 15:17:34,074 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-08 15:17:34,074 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.176470588235294) internal successors, (37), 17 states have internal predecessors, (37), 6 states have call successors, (6), 1 states have call predecessors, (6), 6 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) Word has length 31 [2024-11-08 15:17:34,075 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:17:34,075 INFO L225 Difference]: With dead ends: 46 [2024-11-08 15:17:34,075 INFO L226 Difference]: Without dead ends: 40 [2024-11-08 15:17:34,076 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 57 SyntacticMatches, 3 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 118 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=147, Invalid=315, Unknown=0, NotChecked=0, Total=462 [2024-11-08 15:17:34,077 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 51 mSDsluCounter, 77 mSDsCounter, 0 mSdLazyCounter, 133 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 173 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 133 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 15:17:34,077 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 91 Invalid, 173 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 133 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 15:17:34,078 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2024-11-08 15:17:34,085 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 38. [2024-11-08 15:17:34,086 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 27 states have internal predecessors, (32), 4 states have call successors, (4), 3 states have call predecessors, (4), 6 states have return successors, (10), 7 states have call predecessors, (10), 4 states have call successors, (10) [2024-11-08 15:17:34,087 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 46 transitions. [2024-11-08 15:17:34,087 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 46 transitions. Word has length 31 [2024-11-08 15:17:34,087 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:17:34,087 INFO L471 AbstractCegarLoop]: Abstraction has 38 states and 46 transitions. [2024-11-08 15:17:34,087 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.176470588235294) internal successors, (37), 17 states have internal predecessors, (37), 6 states have call successors, (6), 1 states have call predecessors, (6), 6 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) [2024-11-08 15:17:34,087 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 46 transitions. [2024-11-08 15:17:34,088 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-11-08 15:17:34,088 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:17:34,088 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:17:34,102 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-08 15:17:34,289 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2024-11-08 15:17:34,289 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:17:34,290 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:17:34,290 INFO L85 PathProgramCache]: Analyzing trace with hash -2146751834, now seen corresponding path program 3 times [2024-11-08 15:17:34,290 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:17:34,290 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1644037490] [2024-11-08 15:17:34,290 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:17:34,290 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:17:34,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:34,359 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:17:34,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:34,419 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:34,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:34,481 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:34,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:34,525 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:34,528 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:34,554 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:34,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:34,574 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:34,576 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:34,599 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-08 15:17:34,600 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:17:34,600 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1644037490] [2024-11-08 15:17:34,600 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1644037490] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:17:34,600 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [533334107] [2024-11-08 15:17:34,600 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 15:17:34,601 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:17:34,601 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:17:34,602 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:17:34,604 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-08 15:17:34,652 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-08 15:17:34,652 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 15:17:34,654 INFO L255 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-08 15:17:34,656 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:17:34,738 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-11-08 15:17:34,738 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:17:35,702 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 0 proven. 75 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-08 15:17:35,703 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [533334107] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 15:17:35,703 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 15:17:35,703 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10, 15] total 21 [2024-11-08 15:17:35,703 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1643042228] [2024-11-08 15:17:35,703 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 15:17:35,704 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-08 15:17:35,704 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:17:35,704 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-08 15:17:35,705 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=117, Invalid=303, Unknown=0, NotChecked=0, Total=420 [2024-11-08 15:17:35,705 INFO L87 Difference]: Start difference. First operand 38 states and 46 transitions. Second operand has 21 states, 21 states have (on average 2.238095238095238) internal successors, (47), 21 states have internal predecessors, (47), 8 states have call successors, (8), 1 states have call predecessors, (8), 8 states have return successors, (17), 8 states have call predecessors, (17), 8 states have call successors, (17) [2024-11-08 15:17:35,836 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:17:35,836 INFO L93 Difference]: Finished difference Result 52 states and 63 transitions. [2024-11-08 15:17:35,837 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-08 15:17:35,837 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.238095238095238) internal successors, (47), 21 states have internal predecessors, (47), 8 states have call successors, (8), 1 states have call predecessors, (8), 8 states have return successors, (17), 8 states have call predecessors, (17), 8 states have call successors, (17) Word has length 45 [2024-11-08 15:17:35,838 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:17:35,838 INFO L225 Difference]: With dead ends: 52 [2024-11-08 15:17:35,838 INFO L226 Difference]: Without dead ends: 46 [2024-11-08 15:17:35,839 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 85 SyntacticMatches, 5 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 231 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=243, Invalid=513, Unknown=0, NotChecked=0, Total=756 [2024-11-08 15:17:35,839 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 48 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 108 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 88 SdHoareTripleChecker+Invalid, 139 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 108 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 15:17:35,840 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 88 Invalid, 139 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 108 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 15:17:35,840 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-08 15:17:35,845 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 44. [2024-11-08 15:17:35,845 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 31 states have (on average 1.1612903225806452) internal successors, (36), 31 states have internal predecessors, (36), 4 states have call successors, (4), 3 states have call predecessors, (4), 8 states have return successors, (12), 9 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-08 15:17:35,846 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 52 transitions. [2024-11-08 15:17:35,846 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 52 transitions. Word has length 45 [2024-11-08 15:17:35,846 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:17:35,847 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 52 transitions. [2024-11-08 15:17:35,847 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.238095238095238) internal successors, (47), 21 states have internal predecessors, (47), 8 states have call successors, (8), 1 states have call predecessors, (8), 8 states have return successors, (17), 8 states have call predecessors, (17), 8 states have call successors, (17) [2024-11-08 15:17:35,847 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 52 transitions. [2024-11-08 15:17:35,848 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-11-08 15:17:35,848 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:17:35,848 INFO L215 NwaCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:17:35,865 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-08 15:17:36,052 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:17:36,053 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:17:36,053 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:17:36,053 INFO L85 PathProgramCache]: Analyzing trace with hash -489684568, now seen corresponding path program 4 times [2024-11-08 15:17:36,053 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:17:36,053 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1054393211] [2024-11-08 15:17:36,053 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:17:36,053 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:17:36,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:36,110 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:17:36,115 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:36,179 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:36,184 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:36,228 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:36,232 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:36,298 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:36,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:36,330 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:36,333 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:36,355 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:36,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:36,376 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:36,379 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:36,399 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:36,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:36,430 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 0 proven. 84 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-08 15:17:36,430 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:17:36,430 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1054393211] [2024-11-08 15:17:36,432 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1054393211] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:17:36,432 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1937192274] [2024-11-08 15:17:36,432 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-08 15:17:36,432 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:17:36,432 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:17:36,434 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:17:36,435 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-08 15:17:36,493 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-08 15:17:36,494 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 15:17:36,494 INFO L255 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-08 15:17:36,496 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:17:36,572 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 98 trivial. 0 not checked. [2024-11-08 15:17:36,573 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:17:38,374 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 0 proven. 147 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-08 15:17:38,374 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1937192274] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 15:17:38,374 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 15:17:38,374 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 12, 19] total 25 [2024-11-08 15:17:38,374 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1035961922] [2024-11-08 15:17:38,374 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 15:17:38,375 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-08 15:17:38,375 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:17:38,376 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-08 15:17:38,376 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=165, Invalid=435, Unknown=0, NotChecked=0, Total=600 [2024-11-08 15:17:38,376 INFO L87 Difference]: Start difference. First operand 44 states and 52 transitions. Second operand has 25 states, 25 states have (on average 2.28) internal successors, (57), 25 states have internal predecessors, (57), 10 states have call successors, (10), 1 states have call predecessors, (10), 10 states have return successors, (23), 10 states have call predecessors, (23), 10 states have call successors, (23) [2024-11-08 15:17:38,556 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:17:38,556 INFO L93 Difference]: Finished difference Result 58 states and 69 transitions. [2024-11-08 15:17:38,557 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-08 15:17:38,557 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 2.28) internal successors, (57), 25 states have internal predecessors, (57), 10 states have call successors, (10), 1 states have call predecessors, (10), 10 states have return successors, (23), 10 states have call predecessors, (23), 10 states have call successors, (23) Word has length 59 [2024-11-08 15:17:38,558 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:17:38,560 INFO L225 Difference]: With dead ends: 58 [2024-11-08 15:17:38,560 INFO L226 Difference]: Without dead ends: 52 [2024-11-08 15:17:38,561 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 152 GetRequests, 113 SyntacticMatches, 7 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 380 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=363, Invalid=759, Unknown=0, NotChecked=0, Total=1122 [2024-11-08 15:17:38,563 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 131 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 108 mSolverCounterSat, 104 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 141 SdHoareTripleChecker+Valid, 87 SdHoareTripleChecker+Invalid, 212 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 104 IncrementalHoareTripleChecker+Valid, 108 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 15:17:38,563 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [141 Valid, 87 Invalid, 212 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [104 Valid, 108 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 15:17:38,564 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2024-11-08 15:17:38,568 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 50. [2024-11-08 15:17:38,568 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 35 states have (on average 1.1428571428571428) internal successors, (40), 35 states have internal predecessors, (40), 4 states have call successors, (4), 3 states have call predecessors, (4), 10 states have return successors, (14), 11 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-08 15:17:38,569 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 58 transitions. [2024-11-08 15:17:38,569 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 58 transitions. Word has length 59 [2024-11-08 15:17:38,569 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:17:38,569 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 58 transitions. [2024-11-08 15:17:38,570 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 2.28) internal successors, (57), 25 states have internal predecessors, (57), 10 states have call successors, (10), 1 states have call predecessors, (10), 10 states have return successors, (23), 10 states have call predecessors, (23), 10 states have call successors, (23) [2024-11-08 15:17:38,570 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 58 transitions. [2024-11-08 15:17:38,572 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-08 15:17:38,574 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:17:38,575 INFO L215 NwaCegarLoop]: trace histogram [10, 10, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:17:38,588 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-08 15:17:38,778 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:17:38,779 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:17:38,779 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:17:38,779 INFO L85 PathProgramCache]: Analyzing trace with hash -1199719510, now seen corresponding path program 5 times [2024-11-08 15:17:38,779 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:17:38,779 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [174944894] [2024-11-08 15:17:38,779 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:17:38,780 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:17:38,787 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:38,857 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:17:38,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:38,965 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:38,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:39,034 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:39,039 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:39,091 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:39,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:39,142 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:39,146 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:39,184 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:39,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:39,216 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:39,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:39,242 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:39,245 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:39,264 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:39,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:39,306 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:39,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:39,332 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 0 proven. 135 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-08 15:17:39,333 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:17:39,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [174944894] [2024-11-08 15:17:39,333 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [174944894] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:17:39,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1863008067] [2024-11-08 15:17:39,333 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-08 15:17:39,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:17:39,334 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:17:39,336 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:17:39,338 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-08 15:17:39,422 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2024-11-08 15:17:39,422 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 15:17:39,424 INFO L255 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-08 15:17:39,426 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:17:39,513 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 162 trivial. 0 not checked. [2024-11-08 15:17:39,514 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:17:42,420 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 0 proven. 243 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-08 15:17:42,421 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1863008067] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 15:17:42,421 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 15:17:42,421 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14, 23] total 29 [2024-11-08 15:17:42,421 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1013760130] [2024-11-08 15:17:42,421 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 15:17:42,422 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2024-11-08 15:17:42,422 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:17:42,422 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2024-11-08 15:17:42,423 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=221, Invalid=591, Unknown=0, NotChecked=0, Total=812 [2024-11-08 15:17:42,423 INFO L87 Difference]: Start difference. First operand 50 states and 58 transitions. Second operand has 29 states, 29 states have (on average 2.310344827586207) internal successors, (67), 29 states have internal predecessors, (67), 12 states have call successors, (12), 1 states have call predecessors, (12), 12 states have return successors, (29), 12 states have call predecessors, (29), 12 states have call successors, (29) [2024-11-08 15:17:42,596 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:17:42,596 INFO L93 Difference]: Finished difference Result 64 states and 75 transitions. [2024-11-08 15:17:42,596 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-08 15:17:42,597 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 29 states have (on average 2.310344827586207) internal successors, (67), 29 states have internal predecessors, (67), 12 states have call successors, (12), 1 states have call predecessors, (12), 12 states have return successors, (29), 12 states have call predecessors, (29), 12 states have call successors, (29) Word has length 73 [2024-11-08 15:17:42,597 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:17:42,598 INFO L225 Difference]: With dead ends: 64 [2024-11-08 15:17:42,598 INFO L226 Difference]: Without dead ends: 58 [2024-11-08 15:17:42,599 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 188 GetRequests, 141 SyntacticMatches, 9 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 565 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=507, Invalid=1053, Unknown=0, NotChecked=0, Total=1560 [2024-11-08 15:17:42,599 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 79 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 143 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 91 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 184 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 143 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 15:17:42,599 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [91 Valid, 116 Invalid, 184 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 143 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 15:17:42,600 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2024-11-08 15:17:42,605 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 56. [2024-11-08 15:17:42,605 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 39 states have (on average 1.1282051282051282) internal successors, (44), 39 states have internal predecessors, (44), 4 states have call successors, (4), 3 states have call predecessors, (4), 12 states have return successors, (16), 13 states have call predecessors, (16), 4 states have call successors, (16) [2024-11-08 15:17:42,606 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 64 transitions. [2024-11-08 15:17:42,606 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 64 transitions. Word has length 73 [2024-11-08 15:17:42,606 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:17:42,606 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 64 transitions. [2024-11-08 15:17:42,606 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 2.310344827586207) internal successors, (67), 29 states have internal predecessors, (67), 12 states have call successors, (12), 1 states have call predecessors, (12), 12 states have return successors, (29), 12 states have call predecessors, (29), 12 states have call successors, (29) [2024-11-08 15:17:42,607 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 64 transitions. [2024-11-08 15:17:42,608 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-08 15:17:42,608 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:17:42,608 INFO L215 NwaCegarLoop]: trace histogram [12, 12, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:17:42,622 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-08 15:17:42,812 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:17:42,813 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:17:42,813 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:17:42,813 INFO L85 PathProgramCache]: Analyzing trace with hash -1560921940, now seen corresponding path program 6 times [2024-11-08 15:17:42,813 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:17:42,813 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1440004489] [2024-11-08 15:17:42,814 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:17:42,814 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:17:42,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:42,900 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:17:42,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:43,020 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:43,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:43,134 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:43,141 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:43,221 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:43,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:43,285 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:43,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:43,343 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:43,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:43,385 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:43,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:43,422 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:43,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:43,452 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:43,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:43,497 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:43,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:43,518 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:43,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:43,537 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:43,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:43,564 INFO L134 CoverageAnalysis]: Checked inductivity of 429 backedges. 0 proven. 198 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2024-11-08 15:17:43,565 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:17:43,565 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1440004489] [2024-11-08 15:17:43,565 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1440004489] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:17:43,565 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [567378678] [2024-11-08 15:17:43,565 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-08 15:17:43,565 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:17:43,565 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:17:43,567 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:17:43,568 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-08 15:17:43,697 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 12 check-sat command(s) [2024-11-08 15:17:43,697 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 15:17:43,698 INFO L255 TraceCheckSpWp]: Trace formula consists of 259 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-11-08 15:17:43,700 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:17:43,785 INFO L134 CoverageAnalysis]: Checked inductivity of 429 backedges. 0 proven. 187 refuted. 0 times theorem prover too weak. 242 trivial. 0 not checked. [2024-11-08 15:17:43,786 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:17:48,739 INFO L134 CoverageAnalysis]: Checked inductivity of 429 backedges. 0 proven. 363 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-08 15:17:48,740 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [567378678] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 15:17:48,740 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 15:17:48,740 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 16, 27] total 33 [2024-11-08 15:17:48,740 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [902581354] [2024-11-08 15:17:48,740 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 15:17:48,740 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2024-11-08 15:17:48,741 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:17:48,741 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2024-11-08 15:17:48,742 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=285, Invalid=771, Unknown=0, NotChecked=0, Total=1056 [2024-11-08 15:17:48,742 INFO L87 Difference]: Start difference. First operand 56 states and 64 transitions. Second operand has 33 states, 33 states have (on average 2.3333333333333335) internal successors, (77), 33 states have internal predecessors, (77), 14 states have call successors, (14), 1 states have call predecessors, (14), 14 states have return successors, (35), 14 states have call predecessors, (35), 14 states have call successors, (35) [2024-11-08 15:17:48,950 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:17:48,950 INFO L93 Difference]: Finished difference Result 70 states and 81 transitions. [2024-11-08 15:17:48,950 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-08 15:17:48,950 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 33 states have (on average 2.3333333333333335) internal successors, (77), 33 states have internal predecessors, (77), 14 states have call successors, (14), 1 states have call predecessors, (14), 14 states have return successors, (35), 14 states have call predecessors, (35), 14 states have call successors, (35) Word has length 87 [2024-11-08 15:17:48,951 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:17:48,951 INFO L225 Difference]: With dead ends: 70 [2024-11-08 15:17:48,951 INFO L226 Difference]: Without dead ends: 64 [2024-11-08 15:17:48,952 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 224 GetRequests, 169 SyntacticMatches, 11 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 786 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=675, Invalid=1395, Unknown=0, NotChecked=0, Total=2070 [2024-11-08 15:17:48,953 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 109 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 144 mSolverCounterSat, 74 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 123 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 218 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 74 IncrementalHoareTripleChecker+Valid, 144 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 15:17:48,953 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [123 Valid, 124 Invalid, 218 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [74 Valid, 144 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 15:17:48,953 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2024-11-08 15:17:48,958 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 62. [2024-11-08 15:17:48,958 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 43 states have (on average 1.1162790697674418) internal successors, (48), 43 states have internal predecessors, (48), 4 states have call successors, (4), 3 states have call predecessors, (4), 14 states have return successors, (18), 15 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-08 15:17:48,959 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 70 transitions. [2024-11-08 15:17:48,959 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 70 transitions. Word has length 87 [2024-11-08 15:17:48,959 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:17:48,959 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 70 transitions. [2024-11-08 15:17:48,959 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 33 states have (on average 2.3333333333333335) internal successors, (77), 33 states have internal predecessors, (77), 14 states have call successors, (14), 1 states have call predecessors, (14), 14 states have return successors, (35), 14 states have call predecessors, (35), 14 states have call successors, (35) [2024-11-08 15:17:48,959 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 70 transitions. [2024-11-08 15:17:48,960 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-08 15:17:48,960 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:17:48,960 INFO L215 NwaCegarLoop]: trace histogram [14, 14, 13, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:17:48,973 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-08 15:17:49,164 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:17:49,165 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:17:49,165 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:17:49,165 INFO L85 PathProgramCache]: Analyzing trace with hash 1048271022, now seen corresponding path program 7 times [2024-11-08 15:17:49,165 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:17:49,165 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [916485844] [2024-11-08 15:17:49,165 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:17:49,166 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:17:49,178 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:49,290 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:17:49,299 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:49,470 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:49,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:49,598 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:49,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:49,711 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:49,721 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:49,797 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:49,803 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:49,880 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:49,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:49,968 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:49,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:50,024 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:50,030 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:50,100 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:50,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:50,144 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:50,148 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:50,182 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:50,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:50,216 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:50,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:50,245 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:50,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:50,269 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:50,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:50,307 INFO L134 CoverageAnalysis]: Checked inductivity of 598 backedges. 0 proven. 273 refuted. 0 times theorem prover too weak. 325 trivial. 0 not checked. [2024-11-08 15:17:50,307 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:17:50,307 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [916485844] [2024-11-08 15:17:50,307 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [916485844] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:17:50,307 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [131476071] [2024-11-08 15:17:50,307 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-08 15:17:50,307 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:17:50,308 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:17:50,309 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:17:50,311 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-08 15:17:50,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:50,525 INFO L255 TraceCheckSpWp]: Trace formula consists of 297 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-08 15:17:50,527 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:17:50,648 INFO L134 CoverageAnalysis]: Checked inductivity of 598 backedges. 0 proven. 260 refuted. 0 times theorem prover too weak. 338 trivial. 0 not checked. [2024-11-08 15:17:50,649 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:17:58,634 INFO L134 CoverageAnalysis]: Checked inductivity of 598 backedges. 0 proven. 507 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-08 15:17:58,634 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [131476071] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 15:17:58,634 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 15:17:58,634 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 18, 31] total 37 [2024-11-08 15:17:58,634 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [930529115] [2024-11-08 15:17:58,634 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 15:17:58,635 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2024-11-08 15:17:58,635 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:17:58,636 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2024-11-08 15:17:58,636 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=357, Invalid=975, Unknown=0, NotChecked=0, Total=1332 [2024-11-08 15:17:58,637 INFO L87 Difference]: Start difference. First operand 62 states and 70 transitions. Second operand has 37 states, 37 states have (on average 2.3513513513513513) internal successors, (87), 37 states have internal predecessors, (87), 16 states have call successors, (16), 1 states have call predecessors, (16), 16 states have return successors, (41), 16 states have call predecessors, (41), 16 states have call successors, (41) [2024-11-08 15:17:58,846 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:17:58,846 INFO L93 Difference]: Finished difference Result 76 states and 87 transitions. [2024-11-08 15:17:58,849 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-11-08 15:17:58,850 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 37 states have (on average 2.3513513513513513) internal successors, (87), 37 states have internal predecessors, (87), 16 states have call successors, (16), 1 states have call predecessors, (16), 16 states have return successors, (41), 16 states have call predecessors, (41), 16 states have call successors, (41) Word has length 101 [2024-11-08 15:17:58,850 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:17:58,851 INFO L225 Difference]: With dead ends: 76 [2024-11-08 15:17:58,851 INFO L226 Difference]: Without dead ends: 70 [2024-11-08 15:17:58,852 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 260 GetRequests, 197 SyntacticMatches, 13 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1043 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=867, Invalid=1785, Unknown=0, NotChecked=0, Total=2652 [2024-11-08 15:17:58,852 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 90 mSDsluCounter, 129 mSDsCounter, 0 mSdLazyCounter, 155 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 106 SdHoareTripleChecker+Valid, 143 SdHoareTripleChecker+Invalid, 205 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 155 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 15:17:58,852 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [106 Valid, 143 Invalid, 205 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 155 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 15:17:58,853 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2024-11-08 15:17:58,867 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 68. [2024-11-08 15:17:58,867 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 47 states have (on average 1.1063829787234043) internal successors, (52), 47 states have internal predecessors, (52), 4 states have call successors, (4), 3 states have call predecessors, (4), 16 states have return successors, (20), 17 states have call predecessors, (20), 4 states have call successors, (20) [2024-11-08 15:17:58,868 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 76 transitions. [2024-11-08 15:17:58,868 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 76 transitions. Word has length 101 [2024-11-08 15:17:58,868 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:17:58,872 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 76 transitions. [2024-11-08 15:17:58,873 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 37 states, 37 states have (on average 2.3513513513513513) internal successors, (87), 37 states have internal predecessors, (87), 16 states have call successors, (16), 1 states have call predecessors, (16), 16 states have return successors, (41), 16 states have call predecessors, (41), 16 states have call successors, (41) [2024-11-08 15:17:58,873 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 76 transitions. [2024-11-08 15:17:58,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 116 [2024-11-08 15:17:58,874 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:17:58,874 INFO L215 NwaCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:17:58,895 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-08 15:17:59,074 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:17:59,074 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:17:59,075 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:17:59,075 INFO L85 PathProgramCache]: Analyzing trace with hash 2075065264, now seen corresponding path program 8 times [2024-11-08 15:17:59,075 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:17:59,075 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [924260075] [2024-11-08 15:17:59,075 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:17:59,075 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:17:59,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:59,227 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:17:59,238 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:59,374 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:59,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:59,524 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:59,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:59,659 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:59,666 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:59,745 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:59,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:59,840 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:59,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:59,914 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:59,920 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:17:59,974 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:17:59,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:00,040 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:00,049 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:00,093 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:00,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:00,149 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:00,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:00,184 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:00,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:00,217 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:00,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:00,243 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:00,245 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:00,269 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:00,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:00,289 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:00,290 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:00,320 INFO L134 CoverageAnalysis]: Checked inductivity of 795 backedges. 0 proven. 360 refuted. 0 times theorem prover too weak. 435 trivial. 0 not checked. [2024-11-08 15:18:00,321 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:18:00,321 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [924260075] [2024-11-08 15:18:00,321 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [924260075] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:18:00,321 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2002684584] [2024-11-08 15:18:00,321 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 15:18:00,321 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:18:00,321 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:18:00,325 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:18:00,326 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-08 15:18:00,632 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 15:18:00,632 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 15:18:00,634 INFO L255 TraceCheckSpWp]: Trace formula consists of 335 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-08 15:18:00,637 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:18:00,754 INFO L134 CoverageAnalysis]: Checked inductivity of 795 backedges. 0 proven. 345 refuted. 0 times theorem prover too weak. 450 trivial. 0 not checked. [2024-11-08 15:18:00,754 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:18:12,729 INFO L134 CoverageAnalysis]: Checked inductivity of 795 backedges. 0 proven. 675 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-08 15:18:12,730 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2002684584] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 15:18:12,730 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 15:18:12,730 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 20, 35] total 41 [2024-11-08 15:18:12,730 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1814528693] [2024-11-08 15:18:12,730 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 15:18:12,731 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 41 states [2024-11-08 15:18:12,732 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:18:12,732 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2024-11-08 15:18:12,733 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=437, Invalid=1203, Unknown=0, NotChecked=0, Total=1640 [2024-11-08 15:18:12,736 INFO L87 Difference]: Start difference. First operand 68 states and 76 transitions. Second operand has 41 states, 41 states have (on average 2.3658536585365852) internal successors, (97), 41 states have internal predecessors, (97), 18 states have call successors, (18), 1 states have call predecessors, (18), 18 states have return successors, (47), 18 states have call predecessors, (47), 18 states have call successors, (47) [2024-11-08 15:18:13,014 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:18:13,014 INFO L93 Difference]: Finished difference Result 82 states and 93 transitions. [2024-11-08 15:18:13,014 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-08 15:18:13,014 INFO L78 Accepts]: Start accepts. Automaton has has 41 states, 41 states have (on average 2.3658536585365852) internal successors, (97), 41 states have internal predecessors, (97), 18 states have call successors, (18), 1 states have call predecessors, (18), 18 states have return successors, (47), 18 states have call predecessors, (47), 18 states have call successors, (47) Word has length 115 [2024-11-08 15:18:13,015 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:18:13,015 INFO L225 Difference]: With dead ends: 82 [2024-11-08 15:18:13,015 INFO L226 Difference]: Without dead ends: 76 [2024-11-08 15:18:13,017 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 296 GetRequests, 225 SyntacticMatches, 15 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1336 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=1083, Invalid=2223, Unknown=0, NotChecked=0, Total=3306 [2024-11-08 15:18:13,017 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 298 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 164 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 316 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 313 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 164 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 15:18:13,017 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [316 Valid, 153 Invalid, 313 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [164 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 15:18:13,018 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2024-11-08 15:18:13,023 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 74. [2024-11-08 15:18:13,023 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 51 states have (on average 1.0980392156862746) internal successors, (56), 51 states have internal predecessors, (56), 4 states have call successors, (4), 3 states have call predecessors, (4), 18 states have return successors, (22), 19 states have call predecessors, (22), 4 states have call successors, (22) [2024-11-08 15:18:13,024 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 82 transitions. [2024-11-08 15:18:13,024 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 82 transitions. Word has length 115 [2024-11-08 15:18:13,024 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:18:13,024 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 82 transitions. [2024-11-08 15:18:13,024 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 41 states, 41 states have (on average 2.3658536585365852) internal successors, (97), 41 states have internal predecessors, (97), 18 states have call successors, (18), 1 states have call predecessors, (18), 18 states have return successors, (47), 18 states have call predecessors, (47), 18 states have call successors, (47) [2024-11-08 15:18:13,024 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 82 transitions. [2024-11-08 15:18:13,025 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2024-11-08 15:18:13,025 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:18:13,025 INFO L215 NwaCegarLoop]: trace histogram [18, 18, 17, 17, 17, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:18:13,039 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-08 15:18:13,226 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-08 15:18:13,226 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:18:13,226 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:18:13,226 INFO L85 PathProgramCache]: Analyzing trace with hash -107806286, now seen corresponding path program 9 times [2024-11-08 15:18:13,227 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:18:13,227 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1250699416] [2024-11-08 15:18:13,227 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:18:13,227 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:18:13,245 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:13,413 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:18:13,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:13,567 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:13,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:13,689 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:13,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:13,823 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:13,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:13,921 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:13,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,009 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:14,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,093 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:14,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,176 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:14,183 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,249 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:14,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,324 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:14,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,375 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:14,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,425 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:14,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,466 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:14,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,500 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:14,503 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,531 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:14,534 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,559 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:14,562 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,585 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:14,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,618 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:14,619 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:14,656 INFO L134 CoverageAnalysis]: Checked inductivity of 1020 backedges. 0 proven. 459 refuted. 0 times theorem prover too weak. 561 trivial. 0 not checked. [2024-11-08 15:18:14,656 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:18:14,656 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1250699416] [2024-11-08 15:18:14,656 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1250699416] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:18:14,656 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [524926875] [2024-11-08 15:18:14,656 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 15:18:14,657 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:18:14,657 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:18:14,660 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:18:14,661 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-08 15:18:15,083 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 18 check-sat command(s) [2024-11-08 15:18:15,083 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 15:18:15,085 INFO L255 TraceCheckSpWp]: Trace formula consists of 373 conjuncts, 38 conjuncts are in the unsatisfiable core [2024-11-08 15:18:15,087 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:18:15,194 INFO L134 CoverageAnalysis]: Checked inductivity of 1020 backedges. 0 proven. 442 refuted. 0 times theorem prover too weak. 578 trivial. 0 not checked. [2024-11-08 15:18:15,194 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:18:32,984 INFO L134 CoverageAnalysis]: Checked inductivity of 1020 backedges. 0 proven. 867 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-08 15:18:32,984 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [524926875] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 15:18:32,984 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 15:18:32,984 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 22, 39] total 45 [2024-11-08 15:18:32,984 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1975053392] [2024-11-08 15:18:32,984 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 15:18:32,985 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 45 states [2024-11-08 15:18:32,985 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:18:32,985 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2024-11-08 15:18:32,986 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=525, Invalid=1455, Unknown=0, NotChecked=0, Total=1980 [2024-11-08 15:18:32,986 INFO L87 Difference]: Start difference. First operand 74 states and 82 transitions. Second operand has 45 states, 45 states have (on average 2.3777777777777778) internal successors, (107), 45 states have internal predecessors, (107), 20 states have call successors, (20), 1 states have call predecessors, (20), 20 states have return successors, (53), 20 states have call predecessors, (53), 20 states have call successors, (53) [2024-11-08 15:18:33,272 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 15:18:33,272 INFO L93 Difference]: Finished difference Result 88 states and 99 transitions. [2024-11-08 15:18:33,272 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-08 15:18:33,273 INFO L78 Accepts]: Start accepts. Automaton has has 45 states, 45 states have (on average 2.3777777777777778) internal successors, (107), 45 states have internal predecessors, (107), 20 states have call successors, (20), 1 states have call predecessors, (20), 20 states have return successors, (53), 20 states have call predecessors, (53), 20 states have call successors, (53) Word has length 129 [2024-11-08 15:18:33,273 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 15:18:33,274 INFO L225 Difference]: With dead ends: 88 [2024-11-08 15:18:33,274 INFO L226 Difference]: Without dead ends: 82 [2024-11-08 15:18:33,276 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 332 GetRequests, 253 SyntacticMatches, 17 SemanticMatches, 62 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1665 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=1323, Invalid=2709, Unknown=0, NotChecked=0, Total=4032 [2024-11-08 15:18:33,277 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 223 mSDsluCounter, 168 mSDsCounter, 0 mSdLazyCounter, 192 mSolverCounterSat, 115 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 243 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 307 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 115 IncrementalHoareTripleChecker+Valid, 192 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 15:18:33,277 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [243 Valid, 183 Invalid, 307 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [115 Valid, 192 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 15:18:33,278 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2024-11-08 15:18:33,286 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 80. [2024-11-08 15:18:33,287 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 55 states have (on average 1.0909090909090908) internal successors, (60), 55 states have internal predecessors, (60), 4 states have call successors, (4), 3 states have call predecessors, (4), 20 states have return successors, (24), 21 states have call predecessors, (24), 4 states have call successors, (24) [2024-11-08 15:18:33,287 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 88 transitions. [2024-11-08 15:18:33,287 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 88 transitions. Word has length 129 [2024-11-08 15:18:33,288 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 15:18:33,288 INFO L471 AbstractCegarLoop]: Abstraction has 80 states and 88 transitions. [2024-11-08 15:18:33,288 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 45 states, 45 states have (on average 2.3777777777777778) internal successors, (107), 45 states have internal predecessors, (107), 20 states have call successors, (20), 1 states have call predecessors, (20), 20 states have return successors, (53), 20 states have call predecessors, (53), 20 states have call successors, (53) [2024-11-08 15:18:33,288 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 88 transitions. [2024-11-08 15:18:33,289 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 144 [2024-11-08 15:18:33,290 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 15:18:33,290 INFO L215 NwaCegarLoop]: trace histogram [20, 20, 19, 19, 19, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 15:18:33,307 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-08 15:18:33,490 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:18:33,491 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 15:18:33,491 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 15:18:33,491 INFO L85 PathProgramCache]: Analyzing trace with hash 1602833076, now seen corresponding path program 10 times [2024-11-08 15:18:33,491 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 15:18:33,491 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [767714256] [2024-11-08 15:18:33,492 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 15:18:33,492 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 15:18:33,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:33,706 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 15:18:33,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:33,912 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:33,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:34,079 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:34,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:34,244 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:34,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:34,380 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:34,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:34,479 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:34,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:34,572 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:34,580 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:34,668 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:34,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:34,757 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:34,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:34,841 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:34,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:34,957 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:34,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:35,047 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:35,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:35,137 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:35,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:35,197 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:35,202 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:35,247 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:35,251 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:35,285 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:35,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:35,316 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:35,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:35,347 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:35,349 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:35,375 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:35,376 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:35,398 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-08 15:18:35,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 15:18:35,434 INFO L134 CoverageAnalysis]: Checked inductivity of 1273 backedges. 0 proven. 570 refuted. 0 times theorem prover too weak. 703 trivial. 0 not checked. [2024-11-08 15:18:35,435 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 15:18:35,435 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [767714256] [2024-11-08 15:18:35,435 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [767714256] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 15:18:35,435 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1233363062] [2024-11-08 15:18:35,435 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-08 15:18:35,435 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 15:18:35,435 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 15:18:35,438 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 15:18:35,439 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-08 15:18:36,025 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-08 15:18:36,025 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 15:18:36,027 INFO L255 TraceCheckSpWp]: Trace formula consists of 411 conjuncts, 42 conjuncts are in the unsatisfiable core [2024-11-08 15:18:36,029 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 15:18:36,136 INFO L134 CoverageAnalysis]: Checked inductivity of 1273 backedges. 0 proven. 551 refuted. 0 times theorem prover too weak. 722 trivial. 0 not checked. [2024-11-08 15:18:36,137 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 15:18:59,918 INFO L134 CoverageAnalysis]: Checked inductivity of 1273 backedges. 0 proven. 1083 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2024-11-08 15:18:59,918 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1233363062] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 15:18:59,919 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 15:18:59,919 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 24, 43] total 49 [2024-11-08 15:18:59,919 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1642733933] [2024-11-08 15:18:59,919 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 15:18:59,919 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 49 states [2024-11-08 15:18:59,919 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 15:18:59,920 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2024-11-08 15:18:59,920 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=621, Invalid=1731, Unknown=0, NotChecked=0, Total=2352 [2024-11-08 15:18:59,921 INFO L87 Difference]: Start difference. First operand 80 states and 88 transitions. Second operand has 49 states, 49 states have (on average 2.3877551020408165) internal successors, (117), 49 states have internal predecessors, (117), 22 states have call successors, (22), 1 states have call predecessors, (22), 22 states have return successors, (59), 22 states have call predecessors, (59), 22 states have call successors, (59)