./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/array-crafted/zero_sum_m2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3289d67d 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/array-crafted/zero_sum_m2.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 64e2b591ee375a99f019d69fefe326e9fd46db25f76a67e4f3bee333adbec68f --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-3289d67-m [2024-11-16 02:41:28,095 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-16 02:41:28,171 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-16 02:41:28,176 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-16 02:41:28,177 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-16 02:41:28,191 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-16 02:41:28,192 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-16 02:41:28,193 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-16 02:41:28,193 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-16 02:41:28,195 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-16 02:41:28,195 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-16 02:41:28,195 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-16 02:41:28,196 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-16 02:41:28,197 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-16 02:41:28,197 INFO L153 SettingsManager]: * Use SBE=true [2024-11-16 02:41:28,198 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-16 02:41:28,198 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-16 02:41:28,198 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-16 02:41:28,198 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-16 02:41:28,198 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-16 02:41:28,198 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-16 02:41:28,199 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-16 02:41:28,201 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-16 02:41:28,201 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-16 02:41:28,201 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-16 02:41:28,202 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-16 02:41:28,202 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-16 02:41:28,202 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-16 02:41:28,202 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-16 02:41:28,202 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-16 02:41:28,202 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-16 02:41:28,202 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-16 02:41:28,203 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-16 02:41:28,203 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-16 02:41:28,203 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-16 02:41:28,203 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-16 02:41:28,203 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-16 02:41:28,203 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-16 02:41:28,203 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-16 02:41:28,204 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-16 02:41:28,204 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-16 02:41:28,205 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-16 02:41:28,205 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 -> 64e2b591ee375a99f019d69fefe326e9fd46db25f76a67e4f3bee333adbec68f [2024-11-16 02:41:28,433 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-16 02:41:28,474 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-16 02:41:28,479 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-16 02:41:28,480 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-16 02:41:28,483 INFO L274 PluginConnector]: CDTParser initialized [2024-11-16 02:41:28,485 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-crafted/zero_sum_m2.c [2024-11-16 02:41:29,846 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-16 02:41:30,017 INFO L384 CDTParser]: Found 1 translation units. [2024-11-16 02:41:30,017 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-crafted/zero_sum_m2.c [2024-11-16 02:41:30,023 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/dc11b8359/7afc75a3109f448db6a597d8924e7755/FLAGac5529f9c [2024-11-16 02:41:30,447 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/dc11b8359/7afc75a3109f448db6a597d8924e7755 [2024-11-16 02:41:30,449 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-16 02:41:30,451 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-16 02:41:30,455 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-16 02:41:30,455 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-16 02:41:30,460 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-16 02:41:30,465 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,466 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@448fc671 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30, skipping insertion in model container [2024-11-16 02:41:30,467 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,508 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-16 02:41:30,792 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/array-crafted/zero_sum_m2.c[402,415] [2024-11-16 02:41:30,810 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-16 02:41:30,817 INFO L200 MainTranslator]: Completed pre-run [2024-11-16 02:41:30,827 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/array-crafted/zero_sum_m2.c[402,415] [2024-11-16 02:41:30,833 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-16 02:41:30,844 INFO L204 MainTranslator]: Completed translation [2024-11-16 02:41:30,845 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30 WrapperNode [2024-11-16 02:41:30,845 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-16 02:41:30,845 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-16 02:41:30,846 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-16 02:41:30,846 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-16 02:41:30,850 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,855 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,868 INFO L138 Inliner]: procedures = 15, calls = 15, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 81 [2024-11-16 02:41:30,869 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-16 02:41:30,870 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-16 02:41:30,870 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-16 02:41:30,870 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-16 02:41:30,877 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,877 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,882 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,892 INFO L175 MemorySlicer]: Split 7 memory accesses to 2 slices as follows [2, 5]. 71 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0]. The 1 writes are split as follows [0, 1]. [2024-11-16 02:41:30,892 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,892 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,900 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,900 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,900 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,901 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,905 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-16 02:41:30,906 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-16 02:41:30,906 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-16 02:41:30,906 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-16 02:41:30,906 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30" (1/1) ... [2024-11-16 02:41:30,910 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-16 02:41:30,918 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:41:30,930 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-16 02:41:30,936 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-16 02:41:30,973 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-16 02:41:30,974 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-16 02:41:30,974 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-16 02:41:30,974 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-16 02:41:30,974 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-16 02:41:30,974 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-16 02:41:30,974 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-16 02:41:30,975 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-16 02:41:30,976 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-16 02:41:30,976 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-16 02:41:30,976 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-16 02:41:31,045 INFO L256 CfgBuilder]: Building ICFG [2024-11-16 02:41:31,047 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-16 02:41:31,172 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-11-16 02:41:31,173 INFO L307 CfgBuilder]: Performing block encoding [2024-11-16 02:41:31,183 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-16 02:41:31,187 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-16 02:41:31,188 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.11 02:41:31 BoogieIcfgContainer [2024-11-16 02:41:31,188 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-16 02:41:31,189 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-16 02:41:31,193 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-16 02:41:31,196 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-16 02:41:31,200 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.11 02:41:30" (1/3) ... [2024-11-16 02:41:31,201 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@398668bc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.11 02:41:31, skipping insertion in model container [2024-11-16 02:41:31,201 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 02:41:30" (2/3) ... [2024-11-16 02:41:31,201 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@398668bc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.11 02:41:31, skipping insertion in model container [2024-11-16 02:41:31,202 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.11 02:41:31" (3/3) ... [2024-11-16 02:41:31,203 INFO L112 eAbstractionObserver]: Analyzing ICFG zero_sum_m2.c [2024-11-16 02:41:31,217 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-16 02:41:31,218 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-16 02:41:31,267 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-16 02:41:31,275 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;@31aec375, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-16 02:41:31,275 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-16 02:41:31,280 INFO L276 IsEmpty]: Start isEmpty. Operand has 28 states, 26 states have (on average 1.5) internal successors, (39), 27 states have internal predecessors, (39), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:31,285 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-16 02:41:31,285 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:31,286 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:31,287 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:31,292 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:31,292 INFO L85 PathProgramCache]: Analyzing trace with hash 131574968, now seen corresponding path program 1 times [2024-11-16 02:41:31,302 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:31,302 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1031403050] [2024-11-16 02:41:31,302 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:31,303 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:31,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:31,463 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-16 02:41:31,464 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:31,464 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1031403050] [2024-11-16 02:41:31,465 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1031403050] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 02:41:31,465 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 02:41:31,465 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-16 02:41:31,466 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1974833758] [2024-11-16 02:41:31,467 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 02:41:31,470 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-16 02:41:31,471 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:31,488 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-16 02:41:31,489 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-16 02:41:31,491 INFO L87 Difference]: Start difference. First operand has 28 states, 26 states have (on average 1.5) internal successors, (39), 27 states have internal predecessors, (39), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand has 2 states, 2 states have (on average 8.0) internal successors, (16), 2 states have internal predecessors, (16), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:31,501 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:41:31,502 INFO L93 Difference]: Finished difference Result 50 states and 69 transitions. [2024-11-16 02:41:31,502 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-16 02:41:31,504 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 8.0) internal successors, (16), 2 states have internal predecessors, (16), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 16 [2024-11-16 02:41:31,504 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:41:31,509 INFO L225 Difference]: With dead ends: 50 [2024-11-16 02:41:31,509 INFO L226 Difference]: Without dead ends: 22 [2024-11-16 02:41:31,511 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-16 02:41:31,514 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 02:41:31,514 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 02:41:31,527 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2024-11-16 02:41:31,534 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2024-11-16 02:41:31,536 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 21 states have internal predecessors, (26), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:31,536 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 26 transitions. [2024-11-16 02:41:31,537 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 26 transitions. Word has length 16 [2024-11-16 02:41:31,538 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:41:31,538 INFO L471 AbstractCegarLoop]: Abstraction has 22 states and 26 transitions. [2024-11-16 02:41:31,538 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 8.0) internal successors, (16), 2 states have internal predecessors, (16), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:31,538 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 26 transitions. [2024-11-16 02:41:31,539 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-16 02:41:31,539 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:31,539 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:31,539 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-16 02:41:31,539 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:31,540 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:31,540 INFO L85 PathProgramCache]: Analyzing trace with hash 1145332249, now seen corresponding path program 1 times [2024-11-16 02:41:31,540 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:31,540 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2014630897] [2024-11-16 02:41:31,540 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:31,541 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:31,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:31,652 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-16 02:41:31,652 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:31,653 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2014630897] [2024-11-16 02:41:31,653 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2014630897] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 02:41:31,653 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 02:41:31,653 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-16 02:41:31,653 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [234900970] [2024-11-16 02:41:31,653 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 02:41:31,654 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-16 02:41:31,654 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:31,655 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-16 02:41:31,655 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-16 02:41:31,655 INFO L87 Difference]: Start difference. First operand 22 states and 26 transitions. Second operand has 3 states, 3 states have (on average 7.0) internal successors, (21), 3 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:31,709 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:41:31,710 INFO L93 Difference]: Finished difference Result 41 states and 49 transitions. [2024-11-16 02:41:31,710 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-16 02:41:31,710 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 7.0) internal successors, (21), 3 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 21 [2024-11-16 02:41:31,711 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:41:31,711 INFO L225 Difference]: With dead ends: 41 [2024-11-16 02:41:31,712 INFO L226 Difference]: Without dead ends: 24 [2024-11-16 02:41:31,712 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-16 02:41:31,713 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 12 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 37 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 02:41:31,715 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 37 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 02:41:31,715 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2024-11-16 02:41:31,718 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-16 02:41:31,718 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 23 states have internal predecessors, (28), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:31,718 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 28 transitions. [2024-11-16 02:41:31,719 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 28 transitions. Word has length 21 [2024-11-16 02:41:31,719 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:41:31,719 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 28 transitions. [2024-11-16 02:41:31,721 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 7.0) internal successors, (21), 3 states have internal predecessors, (21), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:31,721 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 28 transitions. [2024-11-16 02:41:31,722 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-16 02:41:31,722 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:31,723 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:31,723 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-16 02:41:31,725 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:31,725 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:31,725 INFO L85 PathProgramCache]: Analyzing trace with hash 675862136, now seen corresponding path program 1 times [2024-11-16 02:41:31,726 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:31,726 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1578993001] [2024-11-16 02:41:31,726 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:31,726 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:31,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:31,800 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-16 02:41:31,801 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:31,801 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1578993001] [2024-11-16 02:41:31,801 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1578993001] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 02:41:31,801 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 02:41:31,802 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-16 02:41:31,802 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [995881285] [2024-11-16 02:41:31,802 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 02:41:31,802 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-16 02:41:31,803 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:31,803 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-16 02:41:31,803 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-16 02:41:31,804 INFO L87 Difference]: Start difference. First operand 24 states and 28 transitions. Second operand has 4 states, 4 states have (on average 5.5) internal successors, (22), 4 states have internal predecessors, (22), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:31,863 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:41:31,863 INFO L93 Difference]: Finished difference Result 46 states and 56 transitions. [2024-11-16 02:41:31,864 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-16 02:41:31,864 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 5.5) internal successors, (22), 4 states have internal predecessors, (22), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 23 [2024-11-16 02:41:31,864 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:41:31,865 INFO L225 Difference]: With dead ends: 46 [2024-11-16 02:41:31,865 INFO L226 Difference]: Without dead ends: 32 [2024-11-16 02:41:31,865 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 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-16 02:41:31,866 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 23 mSDsluCounter, 9 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 25 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 02:41:31,866 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 25 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 02:41:31,867 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2024-11-16 02:41:31,877 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2024-11-16 02:41:31,878 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 31 states have (on average 1.1612903225806452) internal successors, (36), 31 states have internal predecessors, (36), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:31,878 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 36 transitions. [2024-11-16 02:41:31,879 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 36 transitions. Word has length 23 [2024-11-16 02:41:31,879 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:41:31,879 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 36 transitions. [2024-11-16 02:41:31,879 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 5.5) internal successors, (22), 4 states have internal predecessors, (22), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:31,879 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 36 transitions. [2024-11-16 02:41:31,883 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-16 02:41:31,884 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:31,884 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:31,884 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-16 02:41:31,884 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:31,885 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:31,885 INFO L85 PathProgramCache]: Analyzing trace with hash 1506281336, now seen corresponding path program 1 times [2024-11-16 02:41:31,885 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:31,885 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [979660475] [2024-11-16 02:41:31,885 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:31,885 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:31,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:32,028 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-16 02:41:32,028 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:32,028 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [979660475] [2024-11-16 02:41:32,029 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [979660475] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:41:32,029 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [928630273] [2024-11-16 02:41:32,029 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:32,029 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:32,029 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:41:32,032 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-16 02:41:32,033 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-16 02:41:32,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:32,087 INFO L255 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-16 02:41:32,091 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:41:32,141 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-16 02:41:32,142 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:41:32,170 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-16 02:41:32,173 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [928630273] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:41:32,174 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:41:32,174 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 7 [2024-11-16 02:41:32,174 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [356157237] [2024-11-16 02:41:32,174 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:41:32,177 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-16 02:41:32,177 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:32,178 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-16 02:41:32,178 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2024-11-16 02:41:32,178 INFO L87 Difference]: Start difference. First operand 32 states and 36 transitions. Second operand has 7 states, 7 states have (on average 5.0) internal successors, (35), 7 states have internal predecessors, (35), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:32,228 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:41:32,229 INFO L93 Difference]: Finished difference Result 59 states and 67 transitions. [2024-11-16 02:41:32,230 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-16 02:41:32,230 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 5.0) internal successors, (35), 7 states have internal predecessors, (35), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 31 [2024-11-16 02:41:32,230 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:41:32,231 INFO L225 Difference]: With dead ends: 59 [2024-11-16 02:41:32,231 INFO L226 Difference]: Without dead ends: 34 [2024-11-16 02:41:32,231 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 58 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2024-11-16 02:41:32,233 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 61 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 02:41:32,234 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 61 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 02:41:32,236 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2024-11-16 02:41:32,239 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2024-11-16 02:41:32,241 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 33 states have (on average 1.1515151515151516) internal successors, (38), 33 states have internal predecessors, (38), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:32,241 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 38 transitions. [2024-11-16 02:41:32,242 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 38 transitions. Word has length 31 [2024-11-16 02:41:32,242 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:41:32,242 INFO L471 AbstractCegarLoop]: Abstraction has 34 states and 38 transitions. [2024-11-16 02:41:32,243 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 5.0) internal successors, (35), 7 states have internal predecessors, (35), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:32,243 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 38 transitions. [2024-11-16 02:41:32,243 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-11-16 02:41:32,243 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:32,244 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:32,261 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-16 02:41:32,444 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:32,445 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:32,446 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:32,448 INFO L85 PathProgramCache]: Analyzing trace with hash -357969641, now seen corresponding path program 2 times [2024-11-16 02:41:32,448 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:32,449 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [657893055] [2024-11-16 02:41:32,449 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:32,449 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:32,468 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:32,620 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-16 02:41:32,621 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:32,621 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [657893055] [2024-11-16 02:41:32,621 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [657893055] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:41:32,621 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [595351053] [2024-11-16 02:41:32,621 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 02:41:32,621 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:32,622 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:41:32,628 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-16 02:41:32,630 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-16 02:41:32,675 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 02:41:32,675 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:41:32,677 INFO L255 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-16 02:41:32,678 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:41:32,722 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-16 02:41:32,724 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:41:32,771 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-16 02:41:32,772 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [595351053] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:41:32,772 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:41:32,772 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 8 [2024-11-16 02:41:32,772 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [266211406] [2024-11-16 02:41:32,772 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:41:32,772 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-16 02:41:32,773 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:32,773 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-16 02:41:32,773 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=31, Unknown=0, NotChecked=0, Total=56 [2024-11-16 02:41:32,773 INFO L87 Difference]: Start difference. First operand 34 states and 38 transitions. Second operand has 8 states, 8 states have (on average 5.125) internal successors, (41), 8 states have internal predecessors, (41), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:32,824 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:41:32,825 INFO L93 Difference]: Finished difference Result 62 states and 72 transitions. [2024-11-16 02:41:32,825 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 02:41:32,825 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 5.125) internal successors, (41), 8 states have internal predecessors, (41), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 33 [2024-11-16 02:41:32,825 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:41:32,826 INFO L225 Difference]: With dead ends: 62 [2024-11-16 02:41:32,826 INFO L226 Difference]: Without dead ends: 42 [2024-11-16 02:41:32,826 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 60 SyntacticMatches, 3 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=31, Unknown=0, NotChecked=0, Total=56 [2024-11-16 02:41:32,827 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 22 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 76 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 02:41:32,827 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 56 Invalid, 76 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 02:41:32,828 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-16 02:41:32,830 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2024-11-16 02:41:32,831 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 41 states have (on average 1.1219512195121952) internal successors, (46), 41 states have internal predecessors, (46), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:32,831 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 46 transitions. [2024-11-16 02:41:32,831 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 46 transitions. Word has length 33 [2024-11-16 02:41:32,831 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:41:32,832 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 46 transitions. [2024-11-16 02:41:32,832 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 5.125) internal successors, (41), 8 states have internal predecessors, (41), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:32,832 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 46 transitions. [2024-11-16 02:41:32,832 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-16 02:41:32,833 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:32,833 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:32,846 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-16 02:41:33,033 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:33,034 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:33,034 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:33,034 INFO L85 PathProgramCache]: Analyzing trace with hash -462167529, now seen corresponding path program 3 times [2024-11-16 02:41:33,034 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:33,034 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1481035521] [2024-11-16 02:41:33,034 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:33,034 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:33,089 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:34,332 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 02:41:34,333 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:34,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1481035521] [2024-11-16 02:41:34,333 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1481035521] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:41:34,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2009959242] [2024-11-16 02:41:34,333 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-16 02:41:34,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:34,333 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:41:34,337 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-16 02:41:34,338 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-16 02:41:34,402 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-16 02:41:34,402 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:41:34,403 INFO L255 TraceCheckSpWp]: Trace formula consists of 136 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-11-16 02:41:34,406 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:41:34,470 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 1 [2024-11-16 02:41:35,075 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-16 02:41:35,076 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 16 [2024-11-16 02:41:35,148 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 4 proven. 24 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-16 02:41:35,148 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:41:35,786 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-16 02:41:35,787 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2009959242] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:41:35,787 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:41:35,787 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 19, 18] total 44 [2024-11-16 02:41:35,787 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1184949094] [2024-11-16 02:41:35,787 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:41:35,788 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 44 states [2024-11-16 02:41:35,788 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:35,788 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2024-11-16 02:41:35,789 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=135, Invalid=1757, Unknown=0, NotChecked=0, Total=1892 [2024-11-16 02:41:35,789 INFO L87 Difference]: Start difference. First operand 42 states and 46 transitions. Second operand has 44 states, 44 states have (on average 2.4545454545454546) internal successors, (108), 44 states have internal predecessors, (108), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:36,710 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:41:36,711 INFO L93 Difference]: Finished difference Result 70 states and 77 transitions. [2024-11-16 02:41:36,711 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-16 02:41:36,711 INFO L78 Accepts]: Start accepts. Automaton has has 44 states, 44 states have (on average 2.4545454545454546) internal successors, (108), 44 states have internal predecessors, (108), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2024-11-16 02:41:36,712 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:41:36,712 INFO L225 Difference]: With dead ends: 70 [2024-11-16 02:41:36,712 INFO L226 Difference]: Without dead ends: 65 [2024-11-16 02:41:36,713 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 56 SyntacticMatches, 0 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 514 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=229, Invalid=2963, Unknown=0, NotChecked=0, Total=3192 [2024-11-16 02:41:36,713 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 6 mSDsluCounter, 508 mSDsCounter, 0 mSdLazyCounter, 687 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 532 SdHoareTripleChecker+Invalid, 693 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 687 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-16 02:41:36,714 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 532 Invalid, 693 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 687 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-16 02:41:36,714 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2024-11-16 02:41:36,719 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 61. [2024-11-16 02:41:36,720 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 60 states have (on average 1.1333333333333333) internal successors, (68), 60 states have internal predecessors, (68), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:36,720 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 68 transitions. [2024-11-16 02:41:36,720 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 68 transitions. Word has length 41 [2024-11-16 02:41:36,720 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:41:36,721 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 68 transitions. [2024-11-16 02:41:36,721 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 44 states, 44 states have (on average 2.4545454545454546) internal successors, (108), 44 states have internal predecessors, (108), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:36,721 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 68 transitions. [2024-11-16 02:41:36,722 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-16 02:41:36,722 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:36,722 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:36,742 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-16 02:41:36,923 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:36,929 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:36,930 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:36,930 INFO L85 PathProgramCache]: Analyzing trace with hash 160574838, now seen corresponding path program 4 times [2024-11-16 02:41:36,930 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:36,930 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2013204857] [2024-11-16 02:41:36,930 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:36,930 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:36,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:37,066 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 8 proven. 10 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-16 02:41:37,066 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:37,066 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2013204857] [2024-11-16 02:41:37,067 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2013204857] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:41:37,067 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1682261931] [2024-11-16 02:41:37,067 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-16 02:41:37,067 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:37,067 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:41:37,069 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-16 02:41:37,070 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-16 02:41:37,114 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-16 02:41:37,114 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:41:37,115 INFO L255 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-16 02:41:37,116 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:41:37,208 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-16 02:41:37,208 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:41:37,278 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-16 02:41:37,279 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1682261931] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:41:37,279 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:41:37,279 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 16 [2024-11-16 02:41:37,279 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1022998446] [2024-11-16 02:41:37,279 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:41:37,280 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-16 02:41:37,280 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:37,280 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-16 02:41:37,281 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=184, Unknown=0, NotChecked=0, Total=240 [2024-11-16 02:41:37,281 INFO L87 Difference]: Start difference. First operand 61 states and 68 transitions. Second operand has 16 states, 16 states have (on average 3.4375) internal successors, (55), 16 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:37,395 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:41:37,395 INFO L93 Difference]: Finished difference Result 127 states and 143 transitions. [2024-11-16 02:41:37,396 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-16 02:41:37,396 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.4375) internal successors, (55), 16 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 43 [2024-11-16 02:41:37,396 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:41:37,397 INFO L225 Difference]: With dead ends: 127 [2024-11-16 02:41:37,397 INFO L226 Difference]: Without dead ends: 71 [2024-11-16 02:41:37,397 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 74 SyntacticMatches, 5 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 99 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=75, Invalid=231, Unknown=0, NotChecked=0, Total=306 [2024-11-16 02:41:37,397 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 54 mSDsluCounter, 104 mSDsCounter, 0 mSdLazyCounter, 125 mSolverCounterSat, 56 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 181 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 56 IncrementalHoareTripleChecker+Valid, 125 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 02:41:37,398 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 128 Invalid, 181 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [56 Valid, 125 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 02:41:37,398 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2024-11-16 02:41:37,405 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 64. [2024-11-16 02:41:37,406 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 63 states have (on average 1.1111111111111112) internal successors, (70), 63 states have internal predecessors, (70), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:37,406 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 70 transitions. [2024-11-16 02:41:37,410 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 70 transitions. Word has length 43 [2024-11-16 02:41:37,411 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:41:37,411 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 70 transitions. [2024-11-16 02:41:37,411 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.4375) internal successors, (55), 16 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:37,411 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 70 transitions. [2024-11-16 02:41:37,412 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-11-16 02:41:37,412 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:37,412 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:37,439 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-16 02:41:37,612 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:37,613 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:37,613 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:37,613 INFO L85 PathProgramCache]: Analyzing trace with hash 1444331607, now seen corresponding path program 5 times [2024-11-16 02:41:37,613 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:37,613 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [550367706] [2024-11-16 02:41:37,613 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:37,616 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:37,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:37,693 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 2 proven. 16 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 02:41:37,694 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:37,694 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [550367706] [2024-11-16 02:41:37,694 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [550367706] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:41:37,694 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [131573391] [2024-11-16 02:41:37,694 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-16 02:41:37,694 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:37,694 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:41:37,696 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-16 02:41:37,700 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-16 02:41:37,751 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2024-11-16 02:41:37,751 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:41:37,752 INFO L255 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-16 02:41:37,753 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:41:37,868 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 12 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 02:41:37,871 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:41:37,992 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 12 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 02:41:37,992 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [131573391] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:41:37,992 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:41:37,992 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 16 [2024-11-16 02:41:37,992 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [766192563] [2024-11-16 02:41:37,992 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:41:37,992 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-16 02:41:37,992 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:37,993 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-16 02:41:37,993 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=184, Unknown=0, NotChecked=0, Total=240 [2024-11-16 02:41:37,993 INFO L87 Difference]: Start difference. First operand 64 states and 70 transitions. Second operand has 16 states, 16 states have (on average 3.9375) internal successors, (63), 16 states have internal predecessors, (63), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:38,171 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:41:38,171 INFO L93 Difference]: Finished difference Result 71 states and 77 transitions. [2024-11-16 02:41:38,171 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-16 02:41:38,171 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.9375) internal successors, (63), 16 states have internal predecessors, (63), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 45 [2024-11-16 02:41:38,172 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:41:38,172 INFO L225 Difference]: With dead ends: 71 [2024-11-16 02:41:38,172 INFO L226 Difference]: Without dead ends: 52 [2024-11-16 02:41:38,172 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 77 SyntacticMatches, 6 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 124 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=85, Invalid=295, Unknown=0, NotChecked=0, Total=380 [2024-11-16 02:41:38,173 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 47 mSDsluCounter, 128 mSDsCounter, 0 mSdLazyCounter, 178 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 155 SdHoareTripleChecker+Invalid, 214 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 178 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 02:41:38,173 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 155 Invalid, 214 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 178 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 02:41:38,173 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2024-11-16 02:41:38,178 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2024-11-16 02:41:38,179 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 51 states have (on average 1.0980392156862746) internal successors, (56), 51 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:38,179 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 56 transitions. [2024-11-16 02:41:38,179 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 56 transitions. Word has length 45 [2024-11-16 02:41:38,179 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:41:38,179 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 56 transitions. [2024-11-16 02:41:38,180 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.9375) internal successors, (63), 16 states have internal predecessors, (63), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:38,180 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 56 transitions. [2024-11-16 02:41:38,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-16 02:41:38,180 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:38,180 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:38,194 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-16 02:41:38,381 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:38,381 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:38,381 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:38,382 INFO L85 PathProgramCache]: Analyzing trace with hash 907387382, now seen corresponding path program 6 times [2024-11-16 02:41:38,382 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:38,382 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2059495448] [2024-11-16 02:41:38,382 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:38,382 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:38,417 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:39,754 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 60 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 02:41:39,754 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:39,754 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2059495448] [2024-11-16 02:41:39,754 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2059495448] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:41:39,754 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [322543336] [2024-11-16 02:41:39,755 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-16 02:41:39,755 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:39,755 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:41:39,759 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-16 02:41:39,766 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-16 02:41:39,817 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2024-11-16 02:41:39,817 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:41:39,820 INFO L255 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 71 conjuncts are in the unsatisfiable core [2024-11-16 02:41:39,822 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:41:39,917 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 1 [2024-11-16 02:41:41,240 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:41:41,241 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:41:41,253 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-16 02:41:41,253 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 36 treesize of output 37 [2024-11-16 02:41:41,356 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 60 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 02:41:41,357 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:41:43,071 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 25 [2024-11-16 02:41:43,079 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-16 02:41:43,079 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 40 treesize of output 30 [2024-11-16 02:41:43,285 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 60 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 02:41:43,285 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [322543336] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:41:43,285 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:41:43,285 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 28, 28] total 74 [2024-11-16 02:41:43,286 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [912772155] [2024-11-16 02:41:43,286 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:41:43,286 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 74 states [2024-11-16 02:41:43,286 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:43,287 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 74 interpolants. [2024-11-16 02:41:43,289 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=370, Invalid=5032, Unknown=0, NotChecked=0, Total=5402 [2024-11-16 02:41:43,289 INFO L87 Difference]: Start difference. First operand 52 states and 56 transitions. Second operand has 74 states, 74 states have (on average 1.9324324324324325) internal successors, (143), 74 states have internal predecessors, (143), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:49,357 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:41:49,357 INFO L93 Difference]: Finished difference Result 181 states and 205 transitions. [2024-11-16 02:41:49,358 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 69 states. [2024-11-16 02:41:49,358 INFO L78 Accepts]: Start accepts. Automaton has has 74 states, 74 states have (on average 1.9324324324324325) internal successors, (143), 74 states have internal predecessors, (143), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 51 [2024-11-16 02:41:49,358 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:41:49,360 INFO L225 Difference]: With dead ends: 181 [2024-11-16 02:41:49,360 INFO L226 Difference]: Without dead ends: 174 [2024-11-16 02:41:49,363 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3949 ImplicationChecksByTransitivity, 7.1s TimeCoverageRelationStatistics Valid=1235, Invalid=14017, Unknown=0, NotChecked=0, Total=15252 [2024-11-16 02:41:49,364 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 217 mSDsluCounter, 1306 mSDsCounter, 0 mSdLazyCounter, 1801 mSolverCounterSat, 242 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 217 SdHoareTripleChecker+Valid, 1346 SdHoareTripleChecker+Invalid, 2043 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 242 IncrementalHoareTripleChecker+Valid, 1801 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2024-11-16 02:41:49,364 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [217 Valid, 1346 Invalid, 2043 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [242 Valid, 1801 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2024-11-16 02:41:49,366 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2024-11-16 02:41:49,390 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 117. [2024-11-16 02:41:49,390 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 117 states, 116 states have (on average 1.1379310344827587) internal successors, (132), 116 states have internal predecessors, (132), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:49,391 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 132 transitions. [2024-11-16 02:41:49,391 INFO L78 Accepts]: Start accepts. Automaton has 117 states and 132 transitions. Word has length 51 [2024-11-16 02:41:49,391 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:41:49,391 INFO L471 AbstractCegarLoop]: Abstraction has 117 states and 132 transitions. [2024-11-16 02:41:49,392 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 74 states, 74 states have (on average 1.9324324324324325) internal successors, (143), 74 states have internal predecessors, (143), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:49,392 INFO L276 IsEmpty]: Start isEmpty. Operand 117 states and 132 transitions. [2024-11-16 02:41:49,392 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2024-11-16 02:41:49,392 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:49,392 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:49,406 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-16 02:41:49,593 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:49,593 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:49,594 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:49,594 INFO L85 PathProgramCache]: Analyzing trace with hash 2042851733, now seen corresponding path program 7 times [2024-11-16 02:41:49,598 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:49,598 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2019540078] [2024-11-16 02:41:49,598 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:49,598 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:49,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:49,784 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 14 proven. 18 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-16 02:41:49,788 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:49,788 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2019540078] [2024-11-16 02:41:49,788 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2019540078] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:41:49,788 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2054659627] [2024-11-16 02:41:49,788 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-16 02:41:49,789 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:49,789 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:41:49,790 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-16 02:41:49,791 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-16 02:41:49,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:49,845 INFO L255 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-16 02:41:49,849 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:41:50,012 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 20 proven. 12 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-16 02:41:50,013 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:41:50,134 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 20 proven. 12 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-16 02:41:50,135 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2054659627] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:41:50,135 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:41:50,135 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2024-11-16 02:41:50,135 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2069553825] [2024-11-16 02:41:50,135 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:41:50,137 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-16 02:41:50,137 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:50,137 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-16 02:41:50,137 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=202, Unknown=0, NotChecked=0, Total=272 [2024-11-16 02:41:50,138 INFO L87 Difference]: Start difference. First operand 117 states and 132 transitions. Second operand has 17 states, 17 states have (on average 3.1176470588235294) internal successors, (53), 17 states have internal predecessors, (53), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:50,249 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:41:50,249 INFO L93 Difference]: Finished difference Result 181 states and 201 transitions. [2024-11-16 02:41:50,250 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-16 02:41:50,250 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 3.1176470588235294) internal successors, (53), 17 states have internal predecessors, (53), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 53 [2024-11-16 02:41:50,250 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:41:50,251 INFO L225 Difference]: With dead ends: 181 [2024-11-16 02:41:50,251 INFO L226 Difference]: Without dead ends: 77 [2024-11-16 02:41:50,252 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 93 SyntacticMatches, 7 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 129 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=70, Invalid=202, Unknown=0, NotChecked=0, Total=272 [2024-11-16 02:41:50,252 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 18 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 174 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 196 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 02:41:50,253 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 154 Invalid, 196 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 174 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 02:41:50,254 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2024-11-16 02:41:50,267 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2024-11-16 02:41:50,268 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 76 states have (on average 1.105263157894737) internal successors, (84), 76 states have internal predecessors, (84), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:50,268 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 84 transitions. [2024-11-16 02:41:50,269 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 84 transitions. Word has length 53 [2024-11-16 02:41:50,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:41:50,269 INFO L471 AbstractCegarLoop]: Abstraction has 77 states and 84 transitions. [2024-11-16 02:41:50,269 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 3.1176470588235294) internal successors, (53), 17 states have internal predecessors, (53), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:50,269 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 84 transitions. [2024-11-16 02:41:50,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2024-11-16 02:41:50,272 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:50,272 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:50,284 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-16 02:41:50,472 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:50,473 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:50,473 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:50,473 INFO L85 PathProgramCache]: Analyzing trace with hash -1039750668, now seen corresponding path program 8 times [2024-11-16 02:41:50,473 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:50,473 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [39362562] [2024-11-16 02:41:50,473 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:50,473 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:50,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:50,590 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 6 proven. 26 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-11-16 02:41:50,591 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:50,591 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [39362562] [2024-11-16 02:41:50,591 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [39362562] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:41:50,591 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [621398976] [2024-11-16 02:41:50,591 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 02:41:50,591 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:50,591 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:41:50,593 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-16 02:41:50,596 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-16 02:41:50,649 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 02:41:50,650 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:41:50,650 INFO L255 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-16 02:41:50,652 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:41:50,716 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 12 proven. 20 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-11-16 02:41:50,716 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:41:50,785 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 12 proven. 20 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-11-16 02:41:50,785 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [621398976] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:41:50,785 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:41:50,785 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2024-11-16 02:41:50,786 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1845693946] [2024-11-16 02:41:50,787 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:41:50,789 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-16 02:41:50,789 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:50,789 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-16 02:41:50,789 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=199, Unknown=0, NotChecked=0, Total=272 [2024-11-16 02:41:50,789 INFO L87 Difference]: Start difference. First operand 77 states and 84 transitions. Second operand has 17 states, 17 states have (on average 3.1176470588235294) internal successors, (53), 17 states have internal predecessors, (53), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:50,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:41:50,870 INFO L93 Difference]: Finished difference Result 108 states and 120 transitions. [2024-11-16 02:41:50,870 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-16 02:41:50,870 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 3.1176470588235294) internal successors, (53), 17 states have internal predecessors, (53), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 55 [2024-11-16 02:41:50,870 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:41:50,871 INFO L225 Difference]: With dead ends: 108 [2024-11-16 02:41:50,871 INFO L226 Difference]: Without dead ends: 62 [2024-11-16 02:41:50,871 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 96 SyntacticMatches, 8 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 141 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=80, Invalid=226, Unknown=0, NotChecked=0, Total=306 [2024-11-16 02:41:50,871 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 62 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 115 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 154 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 115 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 02:41:50,871 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 114 Invalid, 154 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 115 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 02:41:50,872 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2024-11-16 02:41:50,879 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2024-11-16 02:41:50,879 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 61 states have (on average 1.0819672131147542) internal successors, (66), 61 states have internal predecessors, (66), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:50,879 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 66 transitions. [2024-11-16 02:41:50,879 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 66 transitions. Word has length 55 [2024-11-16 02:41:50,880 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:41:50,880 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 66 transitions. [2024-11-16 02:41:50,880 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 3.1176470588235294) internal successors, (53), 17 states have internal predecessors, (53), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:50,880 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 66 transitions. [2024-11-16 02:41:50,880 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2024-11-16 02:41:50,880 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:50,880 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:50,894 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-16 02:41:51,081 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,SelfDestructingSolverStorable10 [2024-11-16 02:41:51,082 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:51,082 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:51,082 INFO L85 PathProgramCache]: Analyzing trace with hash 1158608661, now seen corresponding path program 9 times [2024-11-16 02:41:51,083 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:51,083 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1798546565] [2024-11-16 02:41:51,083 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:51,083 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:51,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:52,993 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 02:41:52,993 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:52,993 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1798546565] [2024-11-16 02:41:52,994 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1798546565] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:41:52,994 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1515738832] [2024-11-16 02:41:52,994 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-16 02:41:52,994 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:52,994 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:41:52,995 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-16 02:41:52,996 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-16 02:41:53,058 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-16 02:41:53,059 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:41:53,060 INFO L255 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 85 conjuncts are in the unsatisfiable core [2024-11-16 02:41:53,063 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:41:53,104 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 1 [2024-11-16 02:41:54,199 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:41:54,212 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-16 02:41:54,213 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 38 treesize of output 39 [2024-11-16 02:41:54,316 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 8 proven. 80 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-16 02:41:54,317 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:41:55,816 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 0 proven. 88 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-16 02:41:55,817 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1515738832] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:41:55,817 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:41:55,817 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 27, 26] total 76 [2024-11-16 02:41:55,817 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [745147432] [2024-11-16 02:41:55,817 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:41:55,817 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 76 states [2024-11-16 02:41:55,817 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:55,818 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 76 interpolants. [2024-11-16 02:41:55,819 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=303, Invalid=5397, Unknown=0, NotChecked=0, Total=5700 [2024-11-16 02:41:55,819 INFO L87 Difference]: Start difference. First operand 62 states and 66 transitions. Second operand has 76 states, 76 states have (on average 2.1447368421052633) internal successors, (163), 76 states have internal predecessors, (163), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:58,402 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:41:58,402 INFO L93 Difference]: Finished difference Result 102 states and 109 transitions. [2024-11-16 02:41:58,403 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2024-11-16 02:41:58,403 INFO L78 Accepts]: Start accepts. Automaton has has 76 states, 76 states have (on average 2.1447368421052633) internal successors, (163), 76 states have internal predecessors, (163), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 61 [2024-11-16 02:41:58,403 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:41:58,404 INFO L225 Difference]: With dead ends: 102 [2024-11-16 02:41:58,404 INFO L226 Difference]: Without dead ends: 97 [2024-11-16 02:41:58,406 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 179 GetRequests, 76 SyntacticMatches, 0 SemanticMatches, 103 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2203 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=595, Invalid=10325, Unknown=0, NotChecked=0, Total=10920 [2024-11-16 02:41:58,406 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 11 mSDsluCounter, 1320 mSDsCounter, 0 mSdLazyCounter, 1675 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 1355 SdHoareTripleChecker+Invalid, 1685 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 1675 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-16 02:41:58,407 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 1355 Invalid, 1685 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 1675 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-16 02:41:58,407 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2024-11-16 02:41:58,418 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 89. [2024-11-16 02:41:58,418 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 88 states have (on average 1.0909090909090908) internal successors, (96), 88 states have internal predecessors, (96), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:58,418 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 96 transitions. [2024-11-16 02:41:58,419 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 96 transitions. Word has length 61 [2024-11-16 02:41:58,419 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:41:58,419 INFO L471 AbstractCegarLoop]: Abstraction has 89 states and 96 transitions. [2024-11-16 02:41:58,419 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 76 states, 76 states have (on average 2.1447368421052633) internal successors, (163), 76 states have internal predecessors, (163), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:58,419 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 96 transitions. [2024-11-16 02:41:58,420 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2024-11-16 02:41:58,420 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:58,420 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:58,434 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-16 02:41:58,624 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:58,625 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:58,625 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:58,625 INFO L85 PathProgramCache]: Analyzing trace with hash -1346635020, now seen corresponding path program 10 times [2024-11-16 02:41:58,625 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:58,625 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [424854550] [2024-11-16 02:41:58,625 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:58,625 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:58,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:58,801 INFO L134 CoverageAnalysis]: Checked inductivity of 110 backedges. 22 proven. 28 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-16 02:41:58,801 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:58,801 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [424854550] [2024-11-16 02:41:58,801 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [424854550] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:41:58,801 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1796884142] [2024-11-16 02:41:58,801 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-16 02:41:58,801 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:58,802 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:41:58,803 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-16 02:41:58,805 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-16 02:41:58,859 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-16 02:41:58,860 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:41:58,860 INFO L255 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-16 02:41:58,861 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:41:59,032 INFO L134 CoverageAnalysis]: Checked inductivity of 110 backedges. 30 proven. 20 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-16 02:41:59,033 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:41:59,136 INFO L134 CoverageAnalysis]: Checked inductivity of 110 backedges. 30 proven. 20 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-16 02:41:59,136 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1796884142] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:41:59,136 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:41:59,136 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 24 [2024-11-16 02:41:59,136 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [890142303] [2024-11-16 02:41:59,136 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:41:59,137 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-16 02:41:59,137 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:59,137 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-16 02:41:59,137 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=439, Unknown=0, NotChecked=0, Total=552 [2024-11-16 02:41:59,137 INFO L87 Difference]: Start difference. First operand 89 states and 96 transitions. Second operand has 24 states, 24 states have (on average 2.9583333333333335) internal successors, (71), 24 states have internal predecessors, (71), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:59,301 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:41:59,301 INFO L93 Difference]: Finished difference Result 183 states and 199 transitions. [2024-11-16 02:41:59,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-16 02:41:59,302 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 2.9583333333333335) internal successors, (71), 24 states have internal predecessors, (71), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 63 [2024-11-16 02:41:59,302 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:41:59,302 INFO L225 Difference]: With dead ends: 183 [2024-11-16 02:41:59,302 INFO L226 Difference]: Without dead ends: 99 [2024-11-16 02:41:59,303 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 106 SyntacticMatches, 9 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 314 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=163, Invalid=593, Unknown=0, NotChecked=0, Total=756 [2024-11-16 02:41:59,303 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 87 mSDsluCounter, 161 mSDsCounter, 0 mSdLazyCounter, 201 mSolverCounterSat, 89 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 87 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 290 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 89 IncrementalHoareTripleChecker+Valid, 201 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 02:41:59,303 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [87 Valid, 193 Invalid, 290 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [89 Valid, 201 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 02:41:59,303 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2024-11-16 02:41:59,312 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 92. [2024-11-16 02:41:59,313 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 91 states have (on average 1.0769230769230769) internal successors, (98), 91 states have internal predecessors, (98), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:59,313 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 98 transitions. [2024-11-16 02:41:59,313 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 98 transitions. Word has length 63 [2024-11-16 02:41:59,313 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:41:59,313 INFO L471 AbstractCegarLoop]: Abstraction has 92 states and 98 transitions. [2024-11-16 02:41:59,313 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 2.9583333333333335) internal successors, (71), 24 states have internal predecessors, (71), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:41:59,314 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 98 transitions. [2024-11-16 02:41:59,314 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2024-11-16 02:41:59,314 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:41:59,314 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 5, 5, 5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:41:59,327 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-16 02:41:59,518 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-16 02:41:59,519 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:41:59,519 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:41:59,519 INFO L85 PathProgramCache]: Analyzing trace with hash 93202005, now seen corresponding path program 11 times [2024-11-16 02:41:59,519 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:41:59,519 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1709260940] [2024-11-16 02:41:59,520 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:41:59,520 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:41:59,528 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:41:59,632 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 12 proven. 38 refuted. 0 times theorem prover too weak. 70 trivial. 0 not checked. [2024-11-16 02:41:59,632 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:41:59,633 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1709260940] [2024-11-16 02:41:59,633 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1709260940] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:41:59,633 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [85622582] [2024-11-16 02:41:59,633 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-16 02:41:59,633 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:41:59,633 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:41:59,635 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 02:41:59,636 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-16 02:41:59,718 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2024-11-16 02:41:59,719 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:41:59,720 INFO L255 TraceCheckSpWp]: Trace formula consists of 220 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-16 02:41:59,721 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:41:59,841 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 20 proven. 30 refuted. 0 times theorem prover too weak. 70 trivial. 0 not checked. [2024-11-16 02:41:59,842 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:41:59,934 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 20 proven. 30 refuted. 0 times theorem prover too weak. 70 trivial. 0 not checked. [2024-11-16 02:41:59,934 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [85622582] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:41:59,934 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:41:59,934 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 24 [2024-11-16 02:41:59,935 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1585387402] [2024-11-16 02:41:59,935 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:41:59,936 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-16 02:41:59,936 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:41:59,936 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-16 02:41:59,936 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=439, Unknown=0, NotChecked=0, Total=552 [2024-11-16 02:41:59,936 INFO L87 Difference]: Start difference. First operand 92 states and 98 transitions. Second operand has 24 states, 24 states have (on average 2.9583333333333335) internal successors, (71), 24 states have internal predecessors, (71), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:00,099 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:42:00,100 INFO L93 Difference]: Finished difference Result 99 states and 105 transitions. [2024-11-16 02:42:00,100 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-16 02:42:00,100 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 2.9583333333333335) internal successors, (71), 24 states have internal predecessors, (71), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 65 [2024-11-16 02:42:00,100 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:42:00,101 INFO L225 Difference]: With dead ends: 99 [2024-11-16 02:42:00,101 INFO L226 Difference]: Without dead ends: 72 [2024-11-16 02:42:00,101 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 147 GetRequests, 109 SyntacticMatches, 10 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 388 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=175, Invalid=695, Unknown=0, NotChecked=0, Total=870 [2024-11-16 02:42:00,102 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 119 mSDsluCounter, 226 mSDsCounter, 0 mSdLazyCounter, 270 mSolverCounterSat, 94 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 119 SdHoareTripleChecker+Valid, 263 SdHoareTripleChecker+Invalid, 364 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 94 IncrementalHoareTripleChecker+Valid, 270 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 02:42:00,102 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [119 Valid, 263 Invalid, 364 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [94 Valid, 270 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 02:42:00,102 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2024-11-16 02:42:00,109 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 72. [2024-11-16 02:42:00,109 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 71 states have (on average 1.0704225352112675) internal successors, (76), 71 states have internal predecessors, (76), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:00,109 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 76 transitions. [2024-11-16 02:42:00,110 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 76 transitions. Word has length 65 [2024-11-16 02:42:00,110 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:42:00,110 INFO L471 AbstractCegarLoop]: Abstraction has 72 states and 76 transitions. [2024-11-16 02:42:00,110 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 2.9583333333333335) internal successors, (71), 24 states have internal predecessors, (71), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:00,110 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 76 transitions. [2024-11-16 02:42:00,110 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2024-11-16 02:42:00,110 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:42:00,110 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:42:00,126 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-11-16 02:42:00,311 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-16 02:42:00,312 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:42:00,312 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:42:00,312 INFO L85 PathProgramCache]: Analyzing trace with hash 1867878772, now seen corresponding path program 12 times [2024-11-16 02:42:00,312 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:42:00,312 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [429537424] [2024-11-16 02:42:00,313 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:42:00,313 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:42:00,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:42:02,410 INFO L134 CoverageAnalysis]: Checked inductivity of 150 backedges. 2 proven. 148 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 02:42:02,410 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:42:02,410 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [429537424] [2024-11-16 02:42:02,410 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [429537424] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:42:02,410 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1532738205] [2024-11-16 02:42:02,411 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-16 02:42:02,411 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:02,411 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:42:02,412 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 02:42:02,413 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-16 02:42:02,489 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 6 check-sat command(s) [2024-11-16 02:42:02,489 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:42:02,490 INFO L255 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 99 conjuncts are in the unsatisfiable core [2024-11-16 02:42:02,492 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:42:02,546 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 1 [2024-11-16 02:42:04,022 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-16 02:42:04,022 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 16 [2024-11-16 02:42:04,119 INFO L134 CoverageAnalysis]: Checked inductivity of 150 backedges. 10 proven. 120 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2024-11-16 02:42:04,119 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:42:06,167 INFO L134 CoverageAnalysis]: Checked inductivity of 150 backedges. 0 proven. 130 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2024-11-16 02:42:06,168 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1532738205] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:42:06,168 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:42:06,168 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [35, 31, 30] total 89 [2024-11-16 02:42:06,168 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [756659706] [2024-11-16 02:42:06,168 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:42:06,170 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 89 states [2024-11-16 02:42:06,170 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:42:06,171 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2024-11-16 02:42:06,172 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=294, Invalid=7538, Unknown=0, NotChecked=0, Total=7832 [2024-11-16 02:42:06,172 INFO L87 Difference]: Start difference. First operand 72 states and 76 transitions. Second operand has 89 states, 89 states have (on average 2.1235955056179776) internal successors, (189), 89 states have internal predecessors, (189), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:09,457 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:42:09,457 INFO L93 Difference]: Finished difference Result 118 states and 125 transitions. [2024-11-16 02:42:09,457 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2024-11-16 02:42:09,458 INFO L78 Accepts]: Start accepts. Automaton has has 89 states, 89 states have (on average 2.1235955056179776) internal successors, (189), 89 states have internal predecessors, (189), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 71 [2024-11-16 02:42:09,458 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:42:09,458 INFO L225 Difference]: With dead ends: 118 [2024-11-16 02:42:09,459 INFO L226 Difference]: Without dead ends: 113 [2024-11-16 02:42:09,461 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 209 GetRequests, 88 SyntacticMatches, 0 SemanticMatches, 121 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2838 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=624, Invalid=14382, Unknown=0, NotChecked=0, Total=15006 [2024-11-16 02:42:09,461 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 34 mSDsluCounter, 1842 mSDsCounter, 0 mSdLazyCounter, 2257 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 1882 SdHoareTripleChecker+Invalid, 2297 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 2257 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-11-16 02:42:09,461 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 1882 Invalid, 2297 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 2257 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2024-11-16 02:42:09,462 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113 states. [2024-11-16 02:42:09,473 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113 to 103. [2024-11-16 02:42:09,474 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 102 states have (on average 1.0784313725490196) internal successors, (110), 102 states have internal predecessors, (110), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:09,474 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 110 transitions. [2024-11-16 02:42:09,474 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 110 transitions. Word has length 71 [2024-11-16 02:42:09,475 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:42:09,475 INFO L471 AbstractCegarLoop]: Abstraction has 103 states and 110 transitions. [2024-11-16 02:42:09,475 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 89 states, 89 states have (on average 2.1235955056179776) internal successors, (189), 89 states have internal predecessors, (189), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:09,475 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 110 transitions. [2024-11-16 02:42:09,475 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-16 02:42:09,476 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:42:09,476 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:42:09,488 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-11-16 02:42:09,676 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-16 02:42:09,676 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:42:09,676 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:42:09,677 INFO L85 PathProgramCache]: Analyzing trace with hash 1657108883, now seen corresponding path program 13 times [2024-11-16 02:42:09,677 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:42:09,677 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1753999966] [2024-11-16 02:42:09,677 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:42:09,677 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:42:09,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:42:09,812 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 32 proven. 40 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2024-11-16 02:42:09,812 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:42:09,812 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1753999966] [2024-11-16 02:42:09,812 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1753999966] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:42:09,812 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [660983135] [2024-11-16 02:42:09,812 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-16 02:42:09,813 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:09,813 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:42:09,814 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 02:42:09,818 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-16 02:42:09,885 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:42:09,886 INFO L255 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-16 02:42:09,887 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:42:10,049 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 42 proven. 30 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2024-11-16 02:42:10,050 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:42:10,162 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 42 proven. 30 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2024-11-16 02:42:10,162 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [660983135] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:42:10,162 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:42:10,162 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 15] total 23 [2024-11-16 02:42:10,162 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2020153971] [2024-11-16 02:42:10,162 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:42:10,163 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-16 02:42:10,164 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:42:10,165 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-16 02:42:10,165 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=382, Unknown=0, NotChecked=0, Total=506 [2024-11-16 02:42:10,165 INFO L87 Difference]: Start difference. First operand 103 states and 110 transitions. Second operand has 23 states, 23 states have (on average 2.8260869565217392) internal successors, (65), 23 states have internal predecessors, (65), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:10,348 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:42:10,348 INFO L93 Difference]: Finished difference Result 203 states and 217 transitions. [2024-11-16 02:42:10,348 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-16 02:42:10,348 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.8260869565217392) internal successors, (65), 23 states have internal predecessors, (65), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 73 [2024-11-16 02:42:10,349 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:42:10,349 INFO L225 Difference]: With dead ends: 203 [2024-11-16 02:42:10,349 INFO L226 Difference]: Without dead ends: 105 [2024-11-16 02:42:10,349 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 159 GetRequests, 127 SyntacticMatches, 11 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 275 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=124, Invalid=382, Unknown=0, NotChecked=0, Total=506 [2024-11-16 02:42:10,350 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 30 mSDsluCounter, 214 mSDsCounter, 0 mSdLazyCounter, 237 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 251 SdHoareTripleChecker+Invalid, 274 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 237 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-16 02:42:10,350 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 251 Invalid, 274 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 237 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-16 02:42:10,350 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states. [2024-11-16 02:42:10,362 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 105. [2024-11-16 02:42:10,362 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 104 states have (on average 1.0769230769230769) internal successors, (112), 104 states have internal predecessors, (112), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:10,362 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 112 transitions. [2024-11-16 02:42:10,363 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 112 transitions. Word has length 73 [2024-11-16 02:42:10,363 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:42:10,363 INFO L471 AbstractCegarLoop]: Abstraction has 105 states and 112 transitions. [2024-11-16 02:42:10,363 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.8260869565217392) internal successors, (65), 23 states have internal predecessors, (65), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:10,363 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 112 transitions. [2024-11-16 02:42:10,363 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2024-11-16 02:42:10,363 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:42:10,364 INFO L215 NwaCegarLoop]: trace histogram [7, 7, 6, 6, 6, 6, 6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:42:10,376 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-16 02:42:10,564 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-16 02:42:10,564 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:42:10,564 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:42:10,564 INFO L85 PathProgramCache]: Analyzing trace with hash 234867826, now seen corresponding path program 14 times [2024-11-16 02:42:10,564 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:42:10,565 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2129038027] [2024-11-16 02:42:10,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:42:10,565 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:42:10,593 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:42:10,817 INFO L134 CoverageAnalysis]: Checked inductivity of 174 backedges. 20 proven. 52 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2024-11-16 02:42:10,817 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:42:10,817 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2129038027] [2024-11-16 02:42:10,817 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2129038027] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:42:10,817 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [717171706] [2024-11-16 02:42:10,817 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 02:42:10,817 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:10,817 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:42:10,819 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 02:42:10,823 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-16 02:42:10,889 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 02:42:10,889 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:42:10,890 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-16 02:42:10,891 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:42:10,976 INFO L134 CoverageAnalysis]: Checked inductivity of 174 backedges. 30 proven. 42 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2024-11-16 02:42:10,977 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:42:11,148 INFO L134 CoverageAnalysis]: Checked inductivity of 174 backedges. 30 proven. 42 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2024-11-16 02:42:11,148 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [717171706] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:42:11,149 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:42:11,149 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 15] total 23 [2024-11-16 02:42:11,149 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [170441895] [2024-11-16 02:42:11,149 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:42:11,150 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-16 02:42:11,150 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:42:11,150 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-16 02:42:11,150 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=129, Invalid=377, Unknown=0, NotChecked=0, Total=506 [2024-11-16 02:42:11,150 INFO L87 Difference]: Start difference. First operand 105 states and 112 transitions. Second operand has 23 states, 23 states have (on average 2.8260869565217392) internal successors, (65), 23 states have internal predecessors, (65), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:11,285 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:42:11,286 INFO L93 Difference]: Finished difference Result 144 states and 156 transitions. [2024-11-16 02:42:11,286 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-16 02:42:11,286 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.8260869565217392) internal successors, (65), 23 states have internal predecessors, (65), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 75 [2024-11-16 02:42:11,286 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:42:11,287 INFO L225 Difference]: With dead ends: 144 [2024-11-16 02:42:11,287 INFO L226 Difference]: Without dead ends: 82 [2024-11-16 02:42:11,287 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 164 GetRequests, 130 SyntacticMatches, 12 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 310 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=138, Invalid=414, Unknown=0, NotChecked=0, Total=552 [2024-11-16 02:42:11,288 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 62 mSDsluCounter, 120 mSDsCounter, 0 mSdLazyCounter, 154 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 193 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 154 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 02:42:11,288 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 142 Invalid, 193 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 154 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 02:42:11,289 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2024-11-16 02:42:11,301 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 82. [2024-11-16 02:42:11,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 81 states have (on average 1.0617283950617284) internal successors, (86), 81 states have internal predecessors, (86), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:11,302 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 86 transitions. [2024-11-16 02:42:11,302 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 86 transitions. Word has length 75 [2024-11-16 02:42:11,303 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:42:11,303 INFO L471 AbstractCegarLoop]: Abstraction has 82 states and 86 transitions. [2024-11-16 02:42:11,303 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.8260869565217392) internal successors, (65), 23 states have internal predecessors, (65), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:11,303 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 86 transitions. [2024-11-16 02:42:11,303 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2024-11-16 02:42:11,303 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:42:11,304 INFO L215 NwaCegarLoop]: trace histogram [7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:42:11,316 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2024-11-16 02:42:11,504 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:11,505 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:42:11,505 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:42:11,505 INFO L85 PathProgramCache]: Analyzing trace with hash 2104697107, now seen corresponding path program 15 times [2024-11-16 02:42:11,505 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:42:11,506 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [93043902] [2024-11-16 02:42:11,506 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:42:11,506 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:42:11,550 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:42:15,911 INFO L134 CoverageAnalysis]: Checked inductivity of 210 backedges. 0 proven. 210 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 02:42:15,912 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:42:15,912 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [93043902] [2024-11-16 02:42:15,913 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [93043902] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:42:15,913 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1854067564] [2024-11-16 02:42:15,913 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-16 02:42:15,913 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:15,913 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:42:15,914 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 02:42:15,916 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-16 02:42:16,026 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-11-16 02:42:16,026 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:42:16,029 INFO L255 TraceCheckSpWp]: Trace formula consists of 272 conjuncts, 127 conjuncts are in the unsatisfiable core [2024-11-16 02:42:16,031 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:42:16,115 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-16 02:42:18,195 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:42:18,207 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-16 02:42:18,207 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 30 treesize of output 33 [2024-11-16 02:42:18,324 INFO L134 CoverageAnalysis]: Checked inductivity of 210 backedges. 0 proven. 210 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 02:42:18,325 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:42:21,242 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 23 [2024-11-16 02:42:21,248 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-16 02:42:21,248 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 38 treesize of output 28 [2024-11-16 02:42:21,716 INFO L134 CoverageAnalysis]: Checked inductivity of 210 backedges. 0 proven. 210 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 02:42:21,717 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1854067564] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:42:21,717 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:42:21,717 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [40, 41, 43] total 112 [2024-11-16 02:42:21,717 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [52926715] [2024-11-16 02:42:21,717 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:42:21,718 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 112 states [2024-11-16 02:42:21,718 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:42:21,718 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 112 interpolants. [2024-11-16 02:42:21,719 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=707, Invalid=11725, Unknown=0, NotChecked=0, Total=12432 [2024-11-16 02:42:21,720 INFO L87 Difference]: Start difference. First operand 82 states and 86 transitions. Second operand has 112 states, 112 states have (on average 1.9910714285714286) internal successors, (223), 112 states have internal predecessors, (223), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:27,087 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:42:27,088 INFO L93 Difference]: Finished difference Result 197 states and 209 transitions. [2024-11-16 02:42:27,088 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 73 states. [2024-11-16 02:42:27,088 INFO L78 Accepts]: Start accepts. Automaton has has 112 states, 112 states have (on average 1.9910714285714286) internal successors, (223), 112 states have internal predecessors, (223), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 81 [2024-11-16 02:42:27,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:42:27,089 INFO L225 Difference]: With dead ends: 197 [2024-11-16 02:42:27,089 INFO L226 Difference]: Without dead ends: 191 [2024-11-16 02:42:27,090 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 241 GetRequests, 90 SyntacticMatches, 0 SemanticMatches, 151 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5958 ImplicationChecksByTransitivity, 9.2s TimeCoverageRelationStatistics Valid=1419, Invalid=21837, Unknown=0, NotChecked=0, Total=23256 [2024-11-16 02:42:27,093 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 128 mSDsluCounter, 2618 mSDsCounter, 0 mSdLazyCounter, 3166 mSolverCounterSat, 124 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 128 SdHoareTripleChecker+Valid, 2663 SdHoareTripleChecker+Invalid, 3290 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 124 IncrementalHoareTripleChecker+Valid, 3166 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2024-11-16 02:42:27,093 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [128 Valid, 2663 Invalid, 3290 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [124 Valid, 3166 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2024-11-16 02:42:27,097 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 191 states. [2024-11-16 02:42:27,114 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 191 to 117. [2024-11-16 02:42:27,115 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 117 states, 116 states have (on average 1.0689655172413792) internal successors, (124), 116 states have internal predecessors, (124), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:27,115 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 124 transitions. [2024-11-16 02:42:27,115 INFO L78 Accepts]: Start accepts. Automaton has 117 states and 124 transitions. Word has length 81 [2024-11-16 02:42:27,116 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:42:27,116 INFO L471 AbstractCegarLoop]: Abstraction has 117 states and 124 transitions. [2024-11-16 02:42:27,116 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 112 states, 112 states have (on average 1.9910714285714286) internal successors, (223), 112 states have internal predecessors, (223), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:27,116 INFO L276 IsEmpty]: Start isEmpty. Operand 117 states and 124 transitions. [2024-11-16 02:42:27,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2024-11-16 02:42:27,116 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:42:27,117 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 7, 7, 7, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:42:27,135 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-16 02:42:27,320 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-16 02:42:27,321 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:42:27,321 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:42:27,321 INFO L85 PathProgramCache]: Analyzing trace with hash 1606262130, now seen corresponding path program 16 times [2024-11-16 02:42:27,321 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:42:27,321 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1018139319] [2024-11-16 02:42:27,321 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:42:27,322 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:42:27,332 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:42:27,516 INFO L134 CoverageAnalysis]: Checked inductivity of 224 backedges. 44 proven. 54 refuted. 0 times theorem prover too weak. 126 trivial. 0 not checked. [2024-11-16 02:42:27,517 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:42:27,517 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1018139319] [2024-11-16 02:42:27,517 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1018139319] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:42:27,517 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1477350344] [2024-11-16 02:42:27,517 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-16 02:42:27,517 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:27,517 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:42:27,520 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 02:42:27,523 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-16 02:42:27,610 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-16 02:42:27,611 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:42:27,612 INFO L255 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-16 02:42:27,613 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:42:27,894 INFO L134 CoverageAnalysis]: Checked inductivity of 224 backedges. 56 proven. 42 refuted. 0 times theorem prover too weak. 126 trivial. 0 not checked. [2024-11-16 02:42:27,894 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:42:28,069 INFO L134 CoverageAnalysis]: Checked inductivity of 224 backedges. 56 proven. 42 refuted. 0 times theorem prover too weak. 126 trivial. 0 not checked. [2024-11-16 02:42:28,069 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1477350344] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:42:28,069 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:42:28,069 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 17] total 32 [2024-11-16 02:42:28,069 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [370254346] [2024-11-16 02:42:28,069 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:42:28,070 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2024-11-16 02:42:28,070 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:42:28,070 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2024-11-16 02:42:28,070 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=190, Invalid=802, Unknown=0, NotChecked=0, Total=992 [2024-11-16 02:42:28,070 INFO L87 Difference]: Start difference. First operand 117 states and 124 transitions. Second operand has 32 states, 32 states have (on average 2.71875) internal successors, (87), 32 states have internal predecessors, (87), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:28,314 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:42:28,314 INFO L93 Difference]: Finished difference Result 239 states and 255 transitions. [2024-11-16 02:42:28,314 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-16 02:42:28,314 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 32 states have (on average 2.71875) internal successors, (87), 32 states have internal predecessors, (87), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 83 [2024-11-16 02:42:28,315 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:42:28,315 INFO L225 Difference]: With dead ends: 239 [2024-11-16 02:42:28,319 INFO L226 Difference]: Without dead ends: 127 [2024-11-16 02:42:28,320 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 138 SyntacticMatches, 13 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 645 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=283, Invalid=1123, Unknown=0, NotChecked=0, Total=1406 [2024-11-16 02:42:28,320 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 142 mSDsluCounter, 241 mSDsCounter, 0 mSdLazyCounter, 276 mSolverCounterSat, 144 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 142 SdHoareTripleChecker+Valid, 281 SdHoareTripleChecker+Invalid, 420 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 144 IncrementalHoareTripleChecker+Valid, 276 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-16 02:42:28,320 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [142 Valid, 281 Invalid, 420 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [144 Valid, 276 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-16 02:42:28,321 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2024-11-16 02:42:28,336 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 120. [2024-11-16 02:42:28,336 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 119 states have (on average 1.0588235294117647) internal successors, (126), 119 states have internal predecessors, (126), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:28,337 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 126 transitions. [2024-11-16 02:42:28,337 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 126 transitions. Word has length 83 [2024-11-16 02:42:28,337 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:42:28,337 INFO L471 AbstractCegarLoop]: Abstraction has 120 states and 126 transitions. [2024-11-16 02:42:28,337 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 32 states have (on average 2.71875) internal successors, (87), 32 states have internal predecessors, (87), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:28,337 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 126 transitions. [2024-11-16 02:42:28,338 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2024-11-16 02:42:28,338 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:42:28,338 INFO L215 NwaCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:42:28,351 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2024-11-16 02:42:28,542 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:28,547 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:42:28,547 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:42:28,547 INFO L85 PathProgramCache]: Analyzing trace with hash 1148854611, now seen corresponding path program 17 times [2024-11-16 02:42:28,547 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:42:28,547 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [294839417] [2024-11-16 02:42:28,547 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:42:28,548 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:42:28,562 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:42:28,716 INFO L134 CoverageAnalysis]: Checked inductivity of 238 backedges. 30 proven. 68 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-11-16 02:42:28,716 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:42:28,716 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [294839417] [2024-11-16 02:42:28,717 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [294839417] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:42:28,717 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2110552329] [2024-11-16 02:42:28,717 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-16 02:42:28,717 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:28,717 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:42:28,719 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 02:42:28,726 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-16 02:42:28,886 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2024-11-16 02:42:28,886 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:42:28,889 INFO L255 TraceCheckSpWp]: Trace formula consists of 288 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-16 02:42:28,890 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:42:29,041 INFO L134 CoverageAnalysis]: Checked inductivity of 238 backedges. 42 proven. 56 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-11-16 02:42:29,041 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:42:29,187 INFO L134 CoverageAnalysis]: Checked inductivity of 238 backedges. 42 proven. 56 refuted. 0 times theorem prover too weak. 140 trivial. 0 not checked. [2024-11-16 02:42:29,187 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2110552329] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:42:29,187 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:42:29,187 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 17] total 26 [2024-11-16 02:42:29,187 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [706316612] [2024-11-16 02:42:29,187 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:42:29,188 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-11-16 02:42:29,188 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:42:29,188 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-11-16 02:42:29,188 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=163, Invalid=487, Unknown=0, NotChecked=0, Total=650 [2024-11-16 02:42:29,189 INFO L87 Difference]: Start difference. First operand 120 states and 126 transitions. Second operand has 26 states, 26 states have (on average 3.3461538461538463) internal successors, (87), 26 states have internal predecessors, (87), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:29,302 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:42:29,302 INFO L93 Difference]: Finished difference Result 127 states and 133 transitions. [2024-11-16 02:42:29,302 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-16 02:42:29,303 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 3.3461538461538463) internal successors, (87), 26 states have internal predecessors, (87), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 85 [2024-11-16 02:42:29,303 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:42:29,303 INFO L225 Difference]: With dead ends: 127 [2024-11-16 02:42:29,303 INFO L226 Difference]: Without dead ends: 92 [2024-11-16 02:42:29,304 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 186 GetRequests, 147 SyntacticMatches, 14 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 417 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=173, Invalid=529, Unknown=0, NotChecked=0, Total=702 [2024-11-16 02:42:29,305 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 56 mSDsluCounter, 161 mSDsCounter, 0 mSdLazyCounter, 192 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 233 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 192 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 02:42:29,306 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 184 Invalid, 233 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 192 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 02:42:29,306 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2024-11-16 02:42:29,321 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 92. [2024-11-16 02:42:29,321 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 91 states have (on average 1.054945054945055) internal successors, (96), 91 states have internal predecessors, (96), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:29,321 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 96 transitions. [2024-11-16 02:42:29,322 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 96 transitions. Word has length 85 [2024-11-16 02:42:29,322 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:42:29,322 INFO L471 AbstractCegarLoop]: Abstraction has 92 states and 96 transitions. [2024-11-16 02:42:29,322 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 3.3461538461538463) internal successors, (87), 26 states have internal predecessors, (87), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:29,322 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 96 transitions. [2024-11-16 02:42:29,323 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2024-11-16 02:42:29,323 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:42:29,323 INFO L215 NwaCegarLoop]: trace histogram [8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:42:29,336 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2024-11-16 02:42:29,523 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:29,524 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:42:29,524 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:42:29,524 INFO L85 PathProgramCache]: Analyzing trace with hash -444246542, now seen corresponding path program 18 times [2024-11-16 02:42:29,524 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:42:29,525 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [184870642] [2024-11-16 02:42:29,525 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:42:29,525 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:42:29,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:42:33,126 INFO L134 CoverageAnalysis]: Checked inductivity of 280 backedges. 2 proven. 278 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 02:42:33,126 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:42:33,126 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [184870642] [2024-11-16 02:42:33,127 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [184870642] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:42:33,127 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [299659310] [2024-11-16 02:42:33,127 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-16 02:42:33,127 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:33,127 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:42:33,128 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 02:42:33,129 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-16 02:42:33,310 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2024-11-16 02:42:33,311 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:42:33,313 INFO L255 TraceCheckSpWp]: Trace formula consists of 306 conjuncts, 150 conjuncts are in the unsatisfiable core [2024-11-16 02:42:33,318 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:42:33,547 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-16 02:42:33,596 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-16 02:42:33,647 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-16 02:42:36,402 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:42:36,403 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:42:36,404 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:42:36,405 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:42:36,406 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:42:36,407 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:42:36,408 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:42:36,411 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:42:36,412 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:42:36,417 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:42:36,478 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-16 02:42:36,478 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 10 select indices, 10 select index equivalence classes, 30 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 45 case distinctions, treesize of input 72 treesize of output 135 [2024-11-16 02:42:36,706 INFO L134 CoverageAnalysis]: Checked inductivity of 280 backedges. 0 proven. 280 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 02:42:36,706 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:42:40,922 INFO L134 CoverageAnalysis]: Checked inductivity of 280 backedges. 0 proven. 280 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 02:42:40,922 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [299659310] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:42:40,922 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:42:40,922 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [45, 46, 45] total 129 [2024-11-16 02:42:40,923 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [93442674] [2024-11-16 02:42:40,923 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:42:40,923 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 129 states [2024-11-16 02:42:40,923 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:42:40,924 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 129 interpolants. [2024-11-16 02:42:40,925 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1005, Invalid=15507, Unknown=0, NotChecked=0, Total=16512 [2024-11-16 02:42:40,925 INFO L87 Difference]: Start difference. First operand 92 states and 96 transitions. Second operand has 129 states, 129 states have (on average 2.0387596899224807) internal successors, (263), 129 states have internal predecessors, (263), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:51,615 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:42:51,616 INFO L93 Difference]: Finished difference Result 251 states and 270 transitions. [2024-11-16 02:42:51,616 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2024-11-16 02:42:51,616 INFO L78 Accepts]: Start accepts. Automaton has has 129 states, 129 states have (on average 2.0387596899224807) internal successors, (263), 129 states have internal predecessors, (263), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 91 [2024-11-16 02:42:51,616 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:42:51,620 INFO L225 Difference]: With dead ends: 251 [2024-11-16 02:42:51,620 INFO L226 Difference]: Without dead ends: 244 [2024-11-16 02:42:51,622 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 286 GetRequests, 98 SyntacticMatches, 0 SemanticMatches, 188 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8711 ImplicationChecksByTransitivity, 15.0s TimeCoverageRelationStatistics Valid=2840, Invalid=33070, Unknown=0, NotChecked=0, Total=35910 [2024-11-16 02:42:51,622 INFO L432 NwaCegarLoop]: 57 mSDtfsCounter, 332 mSDsluCounter, 3823 mSDsCounter, 0 mSdLazyCounter, 4795 mSolverCounterSat, 380 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 332 SdHoareTripleChecker+Valid, 3880 SdHoareTripleChecker+Invalid, 5175 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 380 IncrementalHoareTripleChecker+Valid, 4795 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.1s IncrementalHoareTripleChecker+Time [2024-11-16 02:42:51,622 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [332 Valid, 3880 Invalid, 5175 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [380 Valid, 4795 Invalid, 0 Unknown, 0 Unchecked, 3.1s Time] [2024-11-16 02:42:51,623 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 244 states. [2024-11-16 02:42:51,662 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 244 to 197. [2024-11-16 02:42:51,662 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 197 states, 196 states have (on average 1.0765306122448979) internal successors, (211), 196 states have internal predecessors, (211), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:51,663 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 197 states to 197 states and 211 transitions. [2024-11-16 02:42:51,663 INFO L78 Accepts]: Start accepts. Automaton has 197 states and 211 transitions. Word has length 91 [2024-11-16 02:42:51,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:42:51,666 INFO L471 AbstractCegarLoop]: Abstraction has 197 states and 211 transitions. [2024-11-16 02:42:51,667 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 129 states, 129 states have (on average 2.0387596899224807) internal successors, (263), 129 states have internal predecessors, (263), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:51,667 INFO L276 IsEmpty]: Start isEmpty. Operand 197 states and 211 transitions. [2024-11-16 02:42:51,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2024-11-16 02:42:51,667 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:42:51,668 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 8, 8, 8, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:42:51,681 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2024-11-16 02:42:51,869 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:51,869 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:42:51,869 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:42:51,869 INFO L85 PathProgramCache]: Analyzing trace with hash -876299567, now seen corresponding path program 19 times [2024-11-16 02:42:51,869 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:42:51,869 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [270032706] [2024-11-16 02:42:51,870 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:42:51,870 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:42:51,886 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:42:52,123 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 58 proven. 70 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-11-16 02:42:52,123 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:42:52,123 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [270032706] [2024-11-16 02:42:52,123 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [270032706] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:42:52,123 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1182509225] [2024-11-16 02:42:52,123 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-16 02:42:52,124 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:52,124 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:42:52,125 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 02:42:52,126 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2024-11-16 02:42:52,205 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:42:52,206 INFO L255 TraceCheckSpWp]: Trace formula consists of 312 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-16 02:42:52,207 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:42:52,452 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 72 proven. 56 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-11-16 02:42:52,452 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:42:52,595 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 72 proven. 56 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-11-16 02:42:52,595 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1182509225] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:42:52,595 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:42:52,595 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 29 [2024-11-16 02:42:52,595 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1565869159] [2024-11-16 02:42:52,595 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:42:52,596 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2024-11-16 02:42:52,596 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:42:52,596 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2024-11-16 02:42:52,597 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=194, Invalid=618, Unknown=0, NotChecked=0, Total=812 [2024-11-16 02:42:52,597 INFO L87 Difference]: Start difference. First operand 197 states and 211 transitions. Second operand has 29 states, 29 states have (on average 2.6551724137931036) internal successors, (77), 29 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:52,797 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:42:52,798 INFO L93 Difference]: Finished difference Result 274 states and 291 transitions. [2024-11-16 02:42:52,798 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-16 02:42:52,798 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 29 states have (on average 2.6551724137931036) internal successors, (77), 29 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 93 [2024-11-16 02:42:52,799 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:42:52,799 INFO L225 Difference]: With dead ends: 274 [2024-11-16 02:42:52,799 INFO L226 Difference]: Without dead ends: 133 [2024-11-16 02:42:52,800 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 203 GetRequests, 161 SyntacticMatches, 15 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 469 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=194, Invalid=618, Unknown=0, NotChecked=0, Total=812 [2024-11-16 02:42:52,800 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 41 mSDsluCounter, 323 mSDsCounter, 0 mSdLazyCounter, 359 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 368 SdHoareTripleChecker+Invalid, 408 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 359 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 02:42:52,800 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 368 Invalid, 408 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 359 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 02:42:52,801 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 133 states. [2024-11-16 02:42:52,824 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 133 to 133. [2024-11-16 02:42:52,825 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 133 states, 132 states have (on average 1.0606060606060606) internal successors, (140), 132 states have internal predecessors, (140), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:52,825 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 140 transitions. [2024-11-16 02:42:52,825 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 140 transitions. Word has length 93 [2024-11-16 02:42:52,825 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:42:52,825 INFO L471 AbstractCegarLoop]: Abstraction has 133 states and 140 transitions. [2024-11-16 02:42:52,826 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 2.6551724137931036) internal successors, (77), 29 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:52,826 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 140 transitions. [2024-11-16 02:42:52,826 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2024-11-16 02:42:52,826 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:42:52,826 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 8, 8, 8, 8, 8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:42:52,838 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2024-11-16 02:42:53,026 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:53,027 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:42:53,027 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:42:53,027 INFO L85 PathProgramCache]: Analyzing trace with hash -835632144, now seen corresponding path program 20 times [2024-11-16 02:42:53,027 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:42:53,027 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [827465939] [2024-11-16 02:42:53,027 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:42:53,028 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:42:53,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:42:53,232 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 42 proven. 86 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2024-11-16 02:42:53,232 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:42:53,232 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [827465939] [2024-11-16 02:42:53,233 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [827465939] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:42:53,233 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1047334225] [2024-11-16 02:42:53,233 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 02:42:53,233 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:53,233 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:42:53,234 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 02:42:53,235 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2024-11-16 02:42:53,316 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 02:42:53,316 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:42:53,317 INFO L255 TraceCheckSpWp]: Trace formula consists of 322 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-16 02:42:53,318 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:42:53,469 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 56 proven. 72 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2024-11-16 02:42:53,469 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 02:42:53,611 INFO L134 CoverageAnalysis]: Checked inductivity of 312 backedges. 56 proven. 72 refuted. 0 times theorem prover too weak. 184 trivial. 0 not checked. [2024-11-16 02:42:53,612 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1047334225] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 02:42:53,612 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 02:42:53,612 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 29 [2024-11-16 02:42:53,612 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [333153354] [2024-11-16 02:42:53,612 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 02:42:53,612 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2024-11-16 02:42:53,612 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 02:42:53,613 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2024-11-16 02:42:53,613 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=201, Invalid=611, Unknown=0, NotChecked=0, Total=812 [2024-11-16 02:42:53,613 INFO L87 Difference]: Start difference. First operand 133 states and 140 transitions. Second operand has 29 states, 29 states have (on average 2.6551724137931036) internal successors, (77), 29 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:53,744 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 02:42:53,744 INFO L93 Difference]: Finished difference Result 180 states and 192 transitions. [2024-11-16 02:42:53,744 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-16 02:42:53,744 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 29 states have (on average 2.6551724137931036) internal successors, (77), 29 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 95 [2024-11-16 02:42:53,744 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 02:42:53,745 INFO L225 Difference]: With dead ends: 180 [2024-11-16 02:42:53,745 INFO L226 Difference]: Without dead ends: 102 [2024-11-16 02:42:53,745 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 208 GetRequests, 164 SyntacticMatches, 16 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 539 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=212, Invalid=658, Unknown=0, NotChecked=0, Total=870 [2024-11-16 02:42:53,746 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 98 mSDsluCounter, 175 mSDsCounter, 0 mSdLazyCounter, 216 mSolverCounterSat, 63 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 98 SdHoareTripleChecker+Valid, 199 SdHoareTripleChecker+Invalid, 279 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 63 IncrementalHoareTripleChecker+Valid, 216 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 02:42:53,746 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [98 Valid, 199 Invalid, 279 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [63 Valid, 216 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 02:42:53,746 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2024-11-16 02:42:53,765 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 102. [2024-11-16 02:42:53,765 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 101 states have (on average 1.0495049504950495) internal successors, (106), 101 states have internal predecessors, (106), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:53,766 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 106 transitions. [2024-11-16 02:42:53,766 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 106 transitions. Word has length 95 [2024-11-16 02:42:53,766 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 02:42:53,766 INFO L471 AbstractCegarLoop]: Abstraction has 102 states and 106 transitions. [2024-11-16 02:42:53,766 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 2.6551724137931036) internal successors, (77), 29 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 02:42:53,766 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 106 transitions. [2024-11-16 02:42:53,767 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-16 02:42:53,767 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 02:42:53,767 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 02:42:53,780 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2024-11-16 02:42:53,971 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable22 [2024-11-16 02:42:53,972 INFO L396 AbstractCegarLoop]: === Iteration 24 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 02:42:53,972 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 02:42:53,972 INFO L85 PathProgramCache]: Analyzing trace with hash 1312677905, now seen corresponding path program 21 times [2024-11-16 02:42:53,972 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 02:42:53,972 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [977155127] [2024-11-16 02:42:53,972 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 02:42:53,972 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 02:42:54,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 02:42:58,312 INFO L134 CoverageAnalysis]: Checked inductivity of 360 backedges. 6 proven. 354 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 02:42:58,312 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 02:42:58,312 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [977155127] [2024-11-16 02:42:58,312 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [977155127] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 02:42:58,313 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1035755211] [2024-11-16 02:42:58,313 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-16 02:42:58,313 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 02:42:58,313 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 02:42:58,314 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 02:42:58,315 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2024-11-16 02:42:58,426 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2024-11-16 02:42:58,427 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 02:42:58,436 INFO L255 TraceCheckSpWp]: Trace formula consists of 340 conjuncts, 159 conjuncts are in the unsatisfiable core [2024-11-16 02:42:58,438 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 02:42:58,496 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 1 [2024-11-16 02:42:58,500 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 1 [2024-11-16 02:42:58,509 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 1 [2024-11-16 02:43:01,840 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:43:01,842 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:43:01,846 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:43:01,848 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:43:01,849 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:43:01,851 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-16 02:43:01,884 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-16 02:43:01,884 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 8 select indices, 8 select index equivalence classes, 18 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 58 treesize of output 93 [2024-11-16 02:43:02,069 INFO L134 CoverageAnalysis]: Checked inductivity of 360 backedges. 16 proven. 288 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2024-11-16 02:43:02,069 INFO L311 TraceCheckSpWp]: Computing backward predicates...