./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/array-cav19/array_min_and_copy_shift_sum_add.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/array-cav19/array_min_and_copy_shift_sum_add.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 8262fd4bdb4bed8fef0fbefd142e15775d81a64587fab0af0aa2004f91ae895c --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-08 10:10:42,492 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-08 10:10:42,569 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-08 10:10:42,578 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-08 10:10:42,579 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-08 10:10:42,610 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-08 10:10:42,611 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-08 10:10:42,611 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-08 10:10:42,612 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-08 10:10:42,614 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-08 10:10:42,614 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-08 10:10:42,615 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-08 10:10:42,615 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-08 10:10:42,617 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-08 10:10:42,618 INFO L153 SettingsManager]: * Use SBE=true [2024-11-08 10:10:42,618 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-08 10:10:42,618 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-08 10:10:42,619 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-08 10:10:42,619 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-08 10:10:42,619 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-08 10:10:42,619 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-08 10:10:42,623 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-08 10:10:42,623 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-08 10:10:42,623 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-08 10:10:42,624 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-08 10:10:42,624 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-08 10:10:42,624 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-08 10:10:42,624 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-08 10:10:42,625 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-08 10:10:42,625 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-08 10:10:42,625 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-08 10:10:42,625 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-08 10:10:42,626 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 10:10:42,626 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-08 10:10:42,626 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-08 10:10:42,627 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-08 10:10:42,627 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-08 10:10:42,627 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-08 10:10:42,627 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-08 10:10:42,627 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-08 10:10:42,628 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-08 10:10:42,629 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-08 10:10:42,630 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 -> 8262fd4bdb4bed8fef0fbefd142e15775d81a64587fab0af0aa2004f91ae895c [2024-11-08 10:10:42,949 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-08 10:10:42,975 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-08 10:10:42,977 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-08 10:10:42,979 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-08 10:10:42,979 INFO L274 PluginConnector]: CDTParser initialized [2024-11-08 10:10:42,980 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-cav19/array_min_and_copy_shift_sum_add.c [2024-11-08 10:10:44,383 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-08 10:10:44,597 INFO L384 CDTParser]: Found 1 translation units. [2024-11-08 10:10:44,598 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-cav19/array_min_and_copy_shift_sum_add.c [2024-11-08 10:10:44,607 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b82c88261/7aefde3e12c844dfa2582e5ad75aee53/FLAGd44b78ca6 [2024-11-08 10:10:44,976 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b82c88261/7aefde3e12c844dfa2582e5ad75aee53 [2024-11-08 10:10:44,978 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-08 10:10:44,979 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-08 10:10:44,980 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-08 10:10:44,980 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-08 10:10:44,985 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-08 10:10:44,985 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 10:10:44" (1/1) ... [2024-11-08 10:10:44,986 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1711c582 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:44, skipping insertion in model container [2024-11-08 10:10:44,986 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 10:10:44" (1/1) ... [2024-11-08 10:10:45,003 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-08 10:10:45,164 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-cav19/array_min_and_copy_shift_sum_add.c[423,436] [2024-11-08 10:10:45,182 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 10:10:45,190 INFO L200 MainTranslator]: Completed pre-run [2024-11-08 10:10:45,202 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-cav19/array_min_and_copy_shift_sum_add.c[423,436] [2024-11-08 10:10:45,209 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 10:10:45,225 INFO L204 MainTranslator]: Completed translation [2024-11-08 10:10:45,225 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45 WrapperNode [2024-11-08 10:10:45,226 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-08 10:10:45,227 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-08 10:10:45,227 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-08 10:10:45,227 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-08 10:10:45,234 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45" (1/1) ... [2024-11-08 10:10:45,241 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45" (1/1) ... [2024-11-08 10:10:45,272 INFO L138 Inliner]: procedures = 15, calls = 24, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 84 [2024-11-08 10:10:45,272 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-08 10:10:45,273 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-08 10:10:45,273 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-08 10:10:45,273 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-08 10:10:45,285 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45" (1/1) ... [2024-11-08 10:10:45,286 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45" (1/1) ... [2024-11-08 10:10:45,289 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45" (1/1) ... [2024-11-08 10:10:45,305 INFO L175 MemorySlicer]: Split 9 memory accesses to 3 slices as follows [2, 5, 2]. 56 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0]. The 1 writes are split as follows [0, 0, 1]. [2024-11-08 10:10:45,310 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45" (1/1) ... [2024-11-08 10:10:45,310 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45" (1/1) ... [2024-11-08 10:10:45,318 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45" (1/1) ... [2024-11-08 10:10:45,325 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45" (1/1) ... [2024-11-08 10:10:45,330 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45" (1/1) ... [2024-11-08 10:10:45,331 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45" (1/1) ... [2024-11-08 10:10:45,333 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-08 10:10:45,334 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-08 10:10:45,334 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-08 10:10:45,334 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-08 10:10:45,335 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45" (1/1) ... [2024-11-08 10:10:45,342 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 10:10:45,357 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:10:45,374 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-08 10:10:45,381 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-08 10:10:45,427 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-08 10:10:45,428 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-08 10:10:45,428 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-08 10:10:45,428 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-08 10:10:45,428 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-08 10:10:45,428 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-11-08 10:10:45,429 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-08 10:10:45,429 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-08 10:10:45,429 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-08 10:10:45,429 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-11-08 10:10:45,429 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-08 10:10:45,429 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-08 10:10:45,430 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-08 10:10:45,430 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-08 10:10:45,430 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-11-08 10:10:45,430 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-08 10:10:45,506 INFO L238 CfgBuilder]: Building ICFG [2024-11-08 10:10:45,508 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-08 10:10:45,702 INFO L? ?]: Removed 14 outVars from TransFormulas that were not future-live. [2024-11-08 10:10:45,702 INFO L287 CfgBuilder]: Performing block encoding [2024-11-08 10:10:45,713 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-08 10:10:45,714 INFO L316 CfgBuilder]: Removed 3 assume(true) statements. [2024-11-08 10:10:45,714 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 10:10:45 BoogieIcfgContainer [2024-11-08 10:10:45,714 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-08 10:10:45,716 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-08 10:10:45,716 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-08 10:10:45,719 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-08 10:10:45,720 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.11 10:10:44" (1/3) ... [2024-11-08 10:10:45,721 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c74035a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 10:10:45, skipping insertion in model container [2024-11-08 10:10:45,722 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:45" (2/3) ... [2024-11-08 10:10:45,722 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c74035a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 10:10:45, skipping insertion in model container [2024-11-08 10:10:45,722 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 10:10:45" (3/3) ... [2024-11-08 10:10:45,723 INFO L112 eAbstractionObserver]: Analyzing ICFG array_min_and_copy_shift_sum_add.c [2024-11-08 10:10:45,740 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-08 10:10:45,740 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-08 10:10:45,790 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-08 10:10:45,796 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;@1d1afb3, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-08 10:10:45,796 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-08 10:10:45,800 INFO L276 IsEmpty]: Start isEmpty. Operand has 30 states, 24 states have (on average 1.4583333333333333) internal successors, (35), 25 states have internal predecessors, (35), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-08 10:10:45,806 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-11-08 10:10:45,807 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:45,807 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:45,808 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:45,813 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:45,813 INFO L85 PathProgramCache]: Analyzing trace with hash 449069998, now seen corresponding path program 1 times [2024-11-08 10:10:45,822 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:45,823 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [412515471] [2024-11-08 10:10:45,823 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:45,823 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:45,944 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:46,007 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:46,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:46,024 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:46,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:46,035 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 10:10:46,036 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:46,036 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [412515471] [2024-11-08 10:10:46,037 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [412515471] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 10:10:46,037 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 10:10:46,037 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-08 10:10:46,038 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1161149685] [2024-11-08 10:10:46,039 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 10:10:46,042 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-08 10:10:46,042 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:46,061 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-08 10:10:46,061 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 10:10:46,063 INFO L87 Difference]: Start difference. First operand has 30 states, 24 states have (on average 1.4583333333333333) internal successors, (35), 25 states have internal predecessors, (35), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 7.5) internal successors, (15), 2 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 10:10:46,077 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:46,077 INFO L93 Difference]: Finished difference Result 57 states and 81 transitions. [2024-11-08 10:10:46,079 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-08 10:10:46,080 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 7.5) internal successors, (15), 2 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2024-11-08 10:10:46,081 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:46,087 INFO L225 Difference]: With dead ends: 57 [2024-11-08 10:10:46,087 INFO L226 Difference]: Without dead ends: 26 [2024-11-08 10:10:46,089 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 10:10:46,093 INFO L432 NwaCegarLoop]: 36 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, 36 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-08 10:10:46,094 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 10:10:46,109 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2024-11-08 10:10:46,127 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2024-11-08 10:10:46,129 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 21 states have internal predecessors, (26), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-08 10:10:46,130 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 32 transitions. [2024-11-08 10:10:46,132 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 32 transitions. Word has length 22 [2024-11-08 10:10:46,134 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:46,134 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 32 transitions. [2024-11-08 10:10:46,134 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 7.5) internal successors, (15), 2 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 10:10:46,134 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 32 transitions. [2024-11-08 10:10:46,136 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-11-08 10:10:46,136 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:46,136 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:46,136 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-08 10:10:46,137 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:46,137 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:46,137 INFO L85 PathProgramCache]: Analyzing trace with hash -1458862922, now seen corresponding path program 1 times [2024-11-08 10:10:46,138 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:46,138 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [338460000] [2024-11-08 10:10:46,138 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:46,138 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:46,196 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:46,449 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:46,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:46,458 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:46,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:46,475 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 10:10:46,479 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:46,479 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [338460000] [2024-11-08 10:10:46,479 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [338460000] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 10:10:46,480 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 10:10:46,480 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-08 10:10:46,480 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1411184234] [2024-11-08 10:10:46,481 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 10:10:46,482 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-08 10:10:46,483 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:46,484 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-08 10:10:46,485 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-08 10:10:46,486 INFO L87 Difference]: Start difference. First operand 26 states and 32 transitions. Second operand has 4 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 10:10:46,516 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:46,517 INFO L93 Difference]: Finished difference Result 31 states and 37 transitions. [2024-11-08 10:10:46,518 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-08 10:10:46,518 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2024-11-08 10:10:46,519 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:46,519 INFO L225 Difference]: With dead ends: 31 [2024-11-08 10:10:46,520 INFO L226 Difference]: Without dead ends: 27 [2024-11-08 10:10:46,521 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-08 10:10:46,522 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 9 mSDsluCounter, 41 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 10:10:46,523 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 71 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 10:10:46,525 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2024-11-08 10:10:46,532 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2024-11-08 10:10:46,534 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 22 states have internal predecessors, (27), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-08 10:10:46,534 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 33 transitions. [2024-11-08 10:10:46,536 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 33 transitions. Word has length 22 [2024-11-08 10:10:46,537 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:46,537 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 33 transitions. [2024-11-08 10:10:46,538 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 10:10:46,538 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 33 transitions. [2024-11-08 10:10:46,539 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-08 10:10:46,539 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:46,540 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:46,540 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-08 10:10:46,541 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:46,541 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:46,541 INFO L85 PathProgramCache]: Analyzing trace with hash -1754695528, now seen corresponding path program 1 times [2024-11-08 10:10:46,541 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:46,542 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [67223370] [2024-11-08 10:10:46,542 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:46,542 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:46,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:46,708 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:46,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:46,714 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:46,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:46,723 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 10:10:46,724 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:46,725 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [67223370] [2024-11-08 10:10:46,725 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [67223370] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 10:10:46,725 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 10:10:46,725 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 10:10:46,725 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [785106816] [2024-11-08 10:10:46,729 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 10:10:46,729 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 10:10:46,729 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:46,730 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 10:10:46,730 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2024-11-08 10:10:46,730 INFO L87 Difference]: Start difference. First operand 27 states and 33 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 10:10:46,835 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:46,836 INFO L93 Difference]: Finished difference Result 50 states and 63 transitions. [2024-11-08 10:10:46,836 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 10:10:46,837 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2024-11-08 10:10:46,837 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:46,838 INFO L225 Difference]: With dead ends: 50 [2024-11-08 10:10:46,838 INFO L226 Difference]: Without dead ends: 36 [2024-11-08 10:10:46,838 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2024-11-08 10:10:46,839 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 8 mSDsluCounter, 47 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 62 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 10:10:46,840 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 68 Invalid, 62 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 10:10:46,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2024-11-08 10:10:46,846 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 29. [2024-11-08 10:10:46,846 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 24 states have (on average 1.2083333333333333) internal successors, (29), 24 states have internal predecessors, (29), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-08 10:10:46,847 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 35 transitions. [2024-11-08 10:10:46,847 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 35 transitions. Word has length 24 [2024-11-08 10:10:46,847 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:46,848 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 35 transitions. [2024-11-08 10:10:46,848 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 10:10:46,848 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2024-11-08 10:10:46,850 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-08 10:10:46,850 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:46,850 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:46,851 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-08 10:10:46,851 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:46,851 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:46,852 INFO L85 PathProgramCache]: Analyzing trace with hash 365972882, now seen corresponding path program 1 times [2024-11-08 10:10:46,852 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:46,852 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1267805349] [2024-11-08 10:10:46,852 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:46,853 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:46,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:47,675 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:47,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:47,682 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:47,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:47,687 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 10:10:47,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:47,694 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:47,695 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:47,695 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1267805349] [2024-11-08 10:10:47,695 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1267805349] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:10:47,695 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1370041337] [2024-11-08 10:10:47,695 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:47,696 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:10:47,696 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:10:47,698 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:10:47,700 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-08 10:10:47,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:47,796 INFO L255 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-08 10:10:47,805 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:10:48,056 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-08 10:10:48,135 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 15 treesize of output 7 [2024-11-08 10:10:48,163 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:48,165 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:10:48,250 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 17 treesize of output 15 [2024-11-08 10:10:48,258 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 24 treesize of output 22 [2024-11-08 10:10:48,335 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:10:48,336 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 18 treesize of output 15 [2024-11-08 10:10:48,395 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:48,395 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1370041337] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:10:48,395 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:10:48,396 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9, 9] total 21 [2024-11-08 10:10:48,396 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2004173130] [2024-11-08 10:10:48,396 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:10:48,398 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-08 10:10:48,398 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:48,399 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-08 10:10:48,399 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=330, Unknown=0, NotChecked=0, Total=420 [2024-11-08 10:10:48,400 INFO L87 Difference]: Start difference. First operand 29 states and 35 transitions. Second operand has 21 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 21 states have internal predecessors, (54), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 10:10:48,704 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:48,704 INFO L93 Difference]: Finished difference Result 55 states and 69 transitions. [2024-11-08 10:10:48,705 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-08 10:10:48,705 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 21 states have internal predecessors, (54), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 36 [2024-11-08 10:10:48,706 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:48,706 INFO L225 Difference]: With dead ends: 55 [2024-11-08 10:10:48,707 INFO L226 Difference]: Without dead ends: 51 [2024-11-08 10:10:48,707 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 68 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 274 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=153, Invalid=497, Unknown=0, NotChecked=0, Total=650 [2024-11-08 10:10:48,708 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 53 mSDsluCounter, 173 mSDsCounter, 0 mSdLazyCounter, 226 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 198 SdHoareTripleChecker+Invalid, 240 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 226 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-08 10:10:48,708 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 198 Invalid, 240 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 226 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-08 10:10:48,709 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2024-11-08 10:10:48,715 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 46. [2024-11-08 10:10:48,716 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 39 states have (on average 1.2820512820512822) internal successors, (50), 39 states have internal predecessors, (50), 5 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-08 10:10:48,717 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 60 transitions. [2024-11-08 10:10:48,717 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 60 transitions. Word has length 36 [2024-11-08 10:10:48,717 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:48,718 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 60 transitions. [2024-11-08 10:10:48,718 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 21 states have internal predecessors, (54), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 10:10:48,718 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 60 transitions. [2024-11-08 10:10:48,719 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-08 10:10:48,719 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:48,719 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:48,737 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-08 10:10:48,920 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-08 10:10:48,921 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:48,921 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:48,921 INFO L85 PathProgramCache]: Analyzing trace with hash -645144368, now seen corresponding path program 1 times [2024-11-08 10:10:48,921 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:48,921 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1653043325] [2024-11-08 10:10:48,921 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:48,922 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:48,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:49,409 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:49,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:49,412 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:49,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:49,416 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 10:10:49,417 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:49,421 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:49,422 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:49,422 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1653043325] [2024-11-08 10:10:49,422 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1653043325] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:10:49,423 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [781800894] [2024-11-08 10:10:49,423 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:49,425 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:10:49,425 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:10:49,427 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:10:49,429 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-08 10:10:49,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:49,494 INFO L255 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-08 10:10:49,500 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:10:49,646 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-08 10:10:49,703 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 15 treesize of output 7 [2024-11-08 10:10:49,721 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:49,723 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:10:49,783 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 17 treesize of output 15 [2024-11-08 10:10:49,787 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 24 treesize of output 22 [2024-11-08 10:10:49,880 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:10:49,880 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 18 treesize of output 15 [2024-11-08 10:10:49,913 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:49,913 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [781800894] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:10:49,913 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:10:49,913 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10, 10] total 24 [2024-11-08 10:10:49,914 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1432786642] [2024-11-08 10:10:49,914 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:10:49,914 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-08 10:10:49,914 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:49,915 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-08 10:10:49,915 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=447, Unknown=0, NotChecked=0, Total=552 [2024-11-08 10:10:49,916 INFO L87 Difference]: Start difference. First operand 46 states and 60 transitions. Second operand has 24 states, 24 states have (on average 2.25) internal successors, (54), 24 states have internal predecessors, (54), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 10:10:50,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:50,201 INFO L93 Difference]: Finished difference Result 70 states and 89 transitions. [2024-11-08 10:10:50,202 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-08 10:10:50,202 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 2.25) internal successors, (54), 24 states have internal predecessors, (54), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 36 [2024-11-08 10:10:50,202 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:50,204 INFO L225 Difference]: With dead ends: 70 [2024-11-08 10:10:50,204 INFO L226 Difference]: Without dead ends: 66 [2024-11-08 10:10:50,204 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 66 SyntacticMatches, 3 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 361 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=169, Invalid=643, Unknown=0, NotChecked=0, Total=812 [2024-11-08 10:10:50,208 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 40 mSDsluCounter, 205 mSDsCounter, 0 mSdLazyCounter, 279 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 293 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 279 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-08 10:10:50,210 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 229 Invalid, 293 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 279 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-08 10:10:50,211 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2024-11-08 10:10:50,223 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 46. [2024-11-08 10:10:50,223 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 39 states have (on average 1.2820512820512822) internal successors, (50), 39 states have internal predecessors, (50), 5 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-08 10:10:50,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 60 transitions. [2024-11-08 10:10:50,225 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 60 transitions. Word has length 36 [2024-11-08 10:10:50,225 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:50,226 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 60 transitions. [2024-11-08 10:10:50,227 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 2.25) internal successors, (54), 24 states have internal predecessors, (54), 6 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-08 10:10:50,227 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 60 transitions. [2024-11-08 10:10:50,228 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-08 10:10:50,228 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:50,228 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:50,245 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-08 10:10:50,432 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-08 10:10:50,433 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:50,433 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:50,433 INFO L85 PathProgramCache]: Analyzing trace with hash -434144652, now seen corresponding path program 2 times [2024-11-08 10:10:50,433 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:50,434 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [683072997] [2024-11-08 10:10:50,434 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:50,434 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:50,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:50,507 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:50,508 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:50,509 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:50,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:50,511 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 10:10:50,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:50,514 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-08 10:10:50,514 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:50,514 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [683072997] [2024-11-08 10:10:50,514 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [683072997] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:10:50,514 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1627059889] [2024-11-08 10:10:50,515 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 10:10:50,515 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:10:50,515 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:10:50,517 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:10:50,518 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-08 10:10:50,582 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 10:10:50,582 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:10:50,583 INFO L255 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-08 10:10:50,586 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:10:50,644 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-08 10:10:50,645 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:10:50,702 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-08 10:10:50,703 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1627059889] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:10:50,703 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:10:50,703 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2024-11-08 10:10:50,703 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [267309264] [2024-11-08 10:10:50,703 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:10:50,704 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-08 10:10:50,704 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:50,704 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-08 10:10:50,705 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2024-11-08 10:10:50,705 INFO L87 Difference]: Start difference. First operand 46 states and 60 transitions. Second operand has 11 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 11 states have internal predecessors, (39), 3 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-08 10:10:50,798 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:50,799 INFO L93 Difference]: Finished difference Result 88 states and 112 transitions. [2024-11-08 10:10:50,800 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-08 10:10:50,800 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 11 states have internal predecessors, (39), 3 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 38 [2024-11-08 10:10:50,801 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:50,802 INFO L225 Difference]: With dead ends: 88 [2024-11-08 10:10:50,802 INFO L226 Difference]: Without dead ends: 68 [2024-11-08 10:10:50,802 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 75 SyntacticMatches, 3 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=89, Unknown=0, NotChecked=0, Total=132 [2024-11-08 10:10:50,803 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 21 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 76 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 95 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 76 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 10:10:50,803 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 82 Invalid, 95 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 76 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 10:10:50,804 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2024-11-08 10:10:50,813 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 56. [2024-11-08 10:10:50,813 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 49 states have (on average 1.2448979591836735) internal successors, (61), 49 states have internal predecessors, (61), 5 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-08 10:10:50,814 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 71 transitions. [2024-11-08 10:10:50,814 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 71 transitions. Word has length 38 [2024-11-08 10:10:50,814 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:50,815 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 71 transitions. [2024-11-08 10:10:50,815 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 11 states have internal predecessors, (39), 3 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-08 10:10:50,815 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 71 transitions. [2024-11-08 10:10:50,816 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-11-08 10:10:50,816 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:50,816 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:50,833 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-08 10:10:51,017 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-08 10:10:51,017 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:51,018 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:51,018 INFO L85 PathProgramCache]: Analyzing trace with hash -1249498774, now seen corresponding path program 3 times [2024-11-08 10:10:51,018 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:51,018 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [664687872] [2024-11-08 10:10:51,018 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:51,018 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:51,030 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:51,095 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:51,097 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:51,098 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:51,099 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:51,100 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 10:10:51,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:51,103 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-08 10:10:51,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:51,105 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-08 10:10:51,105 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:51,105 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [664687872] [2024-11-08 10:10:51,106 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [664687872] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:10:51,106 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2092468797] [2024-11-08 10:10:51,106 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 10:10:51,106 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:10:51,106 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:10:51,108 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:10:51,110 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-08 10:10:51,173 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-08 10:10:51,174 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:10:51,175 INFO L255 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-08 10:10:51,188 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:10:51,252 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 1 proven. 8 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-08 10:10:51,253 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:10:51,327 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 1 proven. 8 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-08 10:10:51,328 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2092468797] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:10:51,328 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:10:51,328 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2024-11-08 10:10:51,328 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [44078038] [2024-11-08 10:10:51,328 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:10:51,329 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-08 10:10:51,330 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:51,331 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-08 10:10:51,331 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2024-11-08 10:10:51,331 INFO L87 Difference]: Start difference. First operand 56 states and 71 transitions. Second operand has 11 states, 11 states have (on average 3.8181818181818183) internal successors, (42), 11 states have internal predecessors, (42), 4 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-08 10:10:51,490 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:51,490 INFO L93 Difference]: Finished difference Result 66 states and 81 transitions. [2024-11-08 10:10:51,490 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-08 10:10:51,491 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.8181818181818183) internal successors, (42), 11 states have internal predecessors, (42), 4 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 46 [2024-11-08 10:10:51,491 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:51,492 INFO L225 Difference]: With dead ends: 66 [2024-11-08 10:10:51,492 INFO L226 Difference]: Without dead ends: 58 [2024-11-08 10:10:51,492 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 92 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=62, Invalid=148, Unknown=0, NotChecked=0, Total=210 [2024-11-08 10:10:51,493 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 37 mSDsluCounter, 127 mSDsCounter, 0 mSdLazyCounter, 166 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 166 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 10:10:51,493 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 151 Invalid, 182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 166 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 10:10:51,494 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2024-11-08 10:10:51,500 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 39. [2024-11-08 10:10:51,500 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 33 states have (on average 1.2121212121212122) internal successors, (40), 33 states have internal predecessors, (40), 4 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-08 10:10:51,501 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 48 transitions. [2024-11-08 10:10:51,501 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 48 transitions. Word has length 46 [2024-11-08 10:10:51,501 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:51,502 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 48 transitions. [2024-11-08 10:10:51,502 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.8181818181818183) internal successors, (42), 11 states have internal predecessors, (42), 4 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-08 10:10:51,502 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 48 transitions. [2024-11-08 10:10:51,503 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-11-08 10:10:51,503 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:51,503 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:51,520 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-08 10:10:51,707 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-08 10:10:51,708 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:51,708 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:51,708 INFO L85 PathProgramCache]: Analyzing trace with hash 1662533230, now seen corresponding path program 4 times [2024-11-08 10:10:51,708 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:51,708 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [453683970] [2024-11-08 10:10:51,708 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:51,709 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:51,734 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:52,776 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:52,777 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:52,779 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:52,780 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:52,782 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 10:10:52,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:52,787 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-08 10:10:52,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:52,794 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:10:52,794 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:52,794 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [453683970] [2024-11-08 10:10:52,794 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [453683970] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:10:52,795 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1060875073] [2024-11-08 10:10:52,795 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-08 10:10:52,795 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:10:52,795 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:10:52,797 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:10:52,798 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-08 10:10:52,867 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-08 10:10:52,868 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:10:52,869 INFO L255 TraceCheckSpWp]: Trace formula consists of 159 conjuncts, 42 conjuncts are in the unsatisfiable core [2024-11-08 10:10:52,874 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:10:53,248 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-08 10:10:53,371 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 21 [2024-11-08 10:10:53,376 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:10:53,377 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 31 treesize of output 15 [2024-11-08 10:10:53,570 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:10:53,571 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 13 [2024-11-08 10:10:53,599 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 6 proven. 19 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-08 10:10:53,599 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:10:55,322 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 47 treesize of output 43 [2024-11-08 10:10:55,343 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:10:55,343 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 323 treesize of output 299 [2024-11-08 10:10:55,708 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:10:55,708 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 51 treesize of output 49 [2024-11-08 10:10:55,883 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 2 proven. 14 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:10:55,883 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1060875073] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:10:55,883 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:10:55,883 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 19, 17] total 50 [2024-11-08 10:10:55,884 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1783504369] [2024-11-08 10:10:55,884 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:10:55,884 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2024-11-08 10:10:55,885 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:55,885 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2024-11-08 10:10:55,886 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=278, Invalid=2172, Unknown=0, NotChecked=0, Total=2450 [2024-11-08 10:10:55,887 INFO L87 Difference]: Start difference. First operand 39 states and 48 transitions. Second operand has 50 states, 50 states have (on average 1.74) internal successors, (87), 50 states have internal predecessors, (87), 10 states have call successors, (10), 1 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-08 10:10:58,706 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:58,707 INFO L93 Difference]: Finished difference Result 96 states and 120 transitions. [2024-11-08 10:10:58,707 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2024-11-08 10:10:58,708 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 50 states have (on average 1.74) internal successors, (87), 50 states have internal predecessors, (87), 10 states have call successors, (10), 1 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 50 [2024-11-08 10:10:58,708 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:58,709 INFO L225 Difference]: With dead ends: 96 [2024-11-08 10:10:58,711 INFO L226 Difference]: Without dead ends: 91 [2024-11-08 10:10:58,714 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 156 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 76 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1830 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=797, Invalid=5209, Unknown=0, NotChecked=0, Total=6006 [2024-11-08 10:10:58,715 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 115 mSDsluCounter, 415 mSDsCounter, 0 mSdLazyCounter, 1487 mSolverCounterSat, 61 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 116 SdHoareTripleChecker+Valid, 442 SdHoareTripleChecker+Invalid, 1548 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 61 IncrementalHoareTripleChecker+Valid, 1487 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2024-11-08 10:10:58,715 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [116 Valid, 442 Invalid, 1548 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [61 Valid, 1487 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2024-11-08 10:10:58,716 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2024-11-08 10:10:58,732 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 72. [2024-11-08 10:10:58,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 63 states have (on average 1.2698412698412698) internal successors, (80), 63 states have internal predecessors, (80), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 10:10:58,737 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 94 transitions. [2024-11-08 10:10:58,737 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 94 transitions. Word has length 50 [2024-11-08 10:10:58,738 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:58,738 INFO L471 AbstractCegarLoop]: Abstraction has 72 states and 94 transitions. [2024-11-08 10:10:58,738 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 50 states, 50 states have (on average 1.74) internal successors, (87), 50 states have internal predecessors, (87), 10 states have call successors, (10), 1 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-08 10:10:58,738 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 94 transitions. [2024-11-08 10:10:58,739 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-11-08 10:10:58,739 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:58,739 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:58,757 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-08 10:10:58,940 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-08 10:10:58,940 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:58,941 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:58,941 INFO L85 PathProgramCache]: Analyzing trace with hash -331611476, now seen corresponding path program 1 times [2024-11-08 10:10:58,941 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:58,941 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1809168213] [2024-11-08 10:10:58,941 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:58,942 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:58,968 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:00,077 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:00,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:00,079 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:00,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:00,083 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 10:11:00,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:00,086 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-08 10:11:00,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:00,092 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:11:00,092 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:00,093 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1809168213] [2024-11-08 10:11:00,093 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1809168213] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:00,093 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1413592272] [2024-11-08 10:11:00,093 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:00,093 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:00,093 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:00,095 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:11:00,097 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-08 10:11:00,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:00,156 INFO L255 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-08 10:11:00,159 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:00,531 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-08 10:11:00,643 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:00,643 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 19 [2024-11-08 10:11:00,649 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 20 [2024-11-08 10:11:00,829 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:00,829 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 13 [2024-11-08 10:11:00,863 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:11:00,863 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:01,128 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 47 treesize of output 43 [2024-11-08 10:11:01,140 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:01,141 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 656 treesize of output 608 [2024-11-08 10:11:01,431 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:01,432 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 56 treesize of output 53 [2024-11-08 10:11:01,580 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 2 proven. 14 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:11:01,580 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1413592272] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:11:01,580 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:11:01,580 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 17, 17] total 48 [2024-11-08 10:11:01,580 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2003210484] [2024-11-08 10:11:01,580 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:01,581 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 48 states [2024-11-08 10:11:01,581 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:01,582 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2024-11-08 10:11:01,582 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=274, Invalid=1982, Unknown=0, NotChecked=0, Total=2256 [2024-11-08 10:11:01,583 INFO L87 Difference]: Start difference. First operand 72 states and 94 transitions. Second operand has 48 states, 48 states have (on average 1.75) internal successors, (84), 48 states have internal predecessors, (84), 10 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-08 10:11:02,821 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:02,821 INFO L93 Difference]: Finished difference Result 99 states and 126 transitions. [2024-11-08 10:11:02,822 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-08 10:11:02,822 INFO L78 Accepts]: Start accepts. Automaton has has 48 states, 48 states have (on average 1.75) internal successors, (84), 48 states have internal predecessors, (84), 10 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 50 [2024-11-08 10:11:02,822 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:02,823 INFO L225 Difference]: With dead ends: 99 [2024-11-08 10:11:02,823 INFO L226 Difference]: Without dead ends: 95 [2024-11-08 10:11:02,824 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 81 SyntacticMatches, 1 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1355 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=610, Invalid=3550, Unknown=0, NotChecked=0, Total=4160 [2024-11-08 10:11:02,825 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 120 mSDsluCounter, 305 mSDsCounter, 0 mSdLazyCounter, 928 mSolverCounterSat, 54 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 121 SdHoareTripleChecker+Valid, 336 SdHoareTripleChecker+Invalid, 982 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 54 IncrementalHoareTripleChecker+Valid, 928 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:02,825 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [121 Valid, 336 Invalid, 982 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [54 Valid, 928 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-08 10:11:02,826 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2024-11-08 10:11:02,835 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 78. [2024-11-08 10:11:02,835 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 68 states have (on average 1.2941176470588236) internal successors, (88), 68 states have internal predecessors, (88), 8 states have call successors, (8), 1 states have call predecessors, (8), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-08 10:11:02,836 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 104 transitions. [2024-11-08 10:11:02,836 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 104 transitions. Word has length 50 [2024-11-08 10:11:02,837 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:02,837 INFO L471 AbstractCegarLoop]: Abstraction has 78 states and 104 transitions. [2024-11-08 10:11:02,837 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 48 states, 48 states have (on average 1.75) internal successors, (84), 48 states have internal predecessors, (84), 10 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-08 10:11:02,837 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 104 transitions. [2024-11-08 10:11:02,838 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-11-08 10:11:02,838 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:02,839 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:02,856 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-08 10:11:03,042 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-08 10:11:03,043 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:03,043 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:03,043 INFO L85 PathProgramCache]: Analyzing trace with hash 1153060140, now seen corresponding path program 2 times [2024-11-08 10:11:03,043 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:03,043 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1525574827] [2024-11-08 10:11:03,044 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:03,044 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:03,069 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:04,183 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:04,184 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:04,186 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:04,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:04,189 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 10:11:04,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:04,192 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-08 10:11:04,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:04,198 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:11:04,200 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:04,200 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1525574827] [2024-11-08 10:11:04,200 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1525574827] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:04,201 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1456425024] [2024-11-08 10:11:04,201 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 10:11:04,201 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:04,201 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:04,203 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:11:04,204 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-08 10:11:04,269 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 10:11:04,269 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:11:04,271 INFO L255 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-08 10:11:04,274 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:04,686 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-08 10:11:04,790 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:04,791 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 31 treesize of output 15 [2024-11-08 10:11:04,796 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 11 [2024-11-08 10:11:04,988 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:04,988 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 13 [2024-11-08 10:11:05,017 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:11:05,017 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:05,337 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 47 treesize of output 43 [2024-11-08 10:11:05,345 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:05,345 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 656 treesize of output 608 [2024-11-08 10:11:05,636 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:05,636 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 51 treesize of output 49 [2024-11-08 10:11:05,767 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 2 proven. 14 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:11:05,767 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1456425024] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:11:05,767 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:11:05,767 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 18, 18] total 50 [2024-11-08 10:11:05,768 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2138891378] [2024-11-08 10:11:05,768 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:05,768 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2024-11-08 10:11:05,768 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:05,769 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2024-11-08 10:11:05,770 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=249, Invalid=2201, Unknown=0, NotChecked=0, Total=2450 [2024-11-08 10:11:05,770 INFO L87 Difference]: Start difference. First operand 78 states and 104 transitions. Second operand has 50 states, 50 states have (on average 1.68) internal successors, (84), 50 states have internal predecessors, (84), 10 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-08 10:11:08,439 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:08,439 INFO L93 Difference]: Finished difference Result 195 states and 251 transitions. [2024-11-08 10:11:08,440 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 50 states. [2024-11-08 10:11:08,440 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 50 states have (on average 1.68) internal successors, (84), 50 states have internal predecessors, (84), 10 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 50 [2024-11-08 10:11:08,441 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:08,442 INFO L225 Difference]: With dead ends: 195 [2024-11-08 10:11:08,443 INFO L226 Difference]: Without dead ends: 190 [2024-11-08 10:11:08,445 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 79 SyntacticMatches, 2 SemanticMatches, 88 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2277 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=1122, Invalid=6888, Unknown=0, NotChecked=0, Total=8010 [2024-11-08 10:11:08,446 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 176 mSDsluCounter, 401 mSDsCounter, 0 mSdLazyCounter, 1149 mSolverCounterSat, 131 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 177 SdHoareTripleChecker+Valid, 426 SdHoareTripleChecker+Invalid, 1280 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 131 IncrementalHoareTripleChecker+Valid, 1149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:08,446 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [177 Valid, 426 Invalid, 1280 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [131 Valid, 1149 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-11-08 10:11:08,447 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 190 states. [2024-11-08 10:11:08,467 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 190 to 82. [2024-11-08 10:11:08,469 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 71 states have (on average 1.3098591549295775) internal successors, (93), 71 states have internal predecessors, (93), 9 states have call successors, (9), 1 states have call predecessors, (9), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-08 10:11:08,470 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 111 transitions. [2024-11-08 10:11:08,471 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 111 transitions. Word has length 50 [2024-11-08 10:11:08,471 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:08,472 INFO L471 AbstractCegarLoop]: Abstraction has 82 states and 111 transitions. [2024-11-08 10:11:08,472 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 50 states, 50 states have (on average 1.68) internal successors, (84), 50 states have internal predecessors, (84), 10 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-08 10:11:08,472 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 111 transitions. [2024-11-08 10:11:08,473 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-11-08 10:11:08,475 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:08,476 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:08,493 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-08 10:11:08,679 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-08 10:11:08,680 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:08,680 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:08,680 INFO L85 PathProgramCache]: Analyzing trace with hash -841084566, now seen corresponding path program 2 times [2024-11-08 10:11:08,680 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:08,680 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1409343719] [2024-11-08 10:11:08,680 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:08,681 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:08,694 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:09,642 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:09,643 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:09,644 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:09,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:09,647 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 10:11:09,647 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:09,649 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-08 10:11:09,651 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:09,654 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:11:09,654 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:09,655 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1409343719] [2024-11-08 10:11:09,655 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1409343719] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:09,655 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1487090855] [2024-11-08 10:11:09,655 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 10:11:09,655 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:09,655 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:09,657 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:11:09,659 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-08 10:11:09,726 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 10:11:09,726 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:11:09,728 INFO L255 TraceCheckSpWp]: Trace formula consists of 151 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-08 10:11:09,730 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:10,049 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-08 10:11:10,175 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 24 [2024-11-08 10:11:10,202 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:10,202 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 19 [2024-11-08 10:11:10,390 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:10,390 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 13 [2024-11-08 10:11:10,413 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:11:10,413 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:10,643 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 47 treesize of output 43 [2024-11-08 10:11:10,651 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:10,651 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 299 treesize of output 275 [2024-11-08 10:11:10,912 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:10,913 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 56 treesize of output 53 [2024-11-08 10:11:11,024 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 2 proven. 14 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:11:11,025 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1487090855] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:11:11,025 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:11:11,025 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 18, 18] total 51 [2024-11-08 10:11:11,025 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1673192565] [2024-11-08 10:11:11,025 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:11,026 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 51 states [2024-11-08 10:11:11,026 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:11,028 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2024-11-08 10:11:11,028 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=271, Invalid=2279, Unknown=0, NotChecked=0, Total=2550 [2024-11-08 10:11:11,029 INFO L87 Difference]: Start difference. First operand 82 states and 111 transitions. Second operand has 51 states, 51 states have (on average 1.6470588235294117) internal successors, (84), 51 states have internal predecessors, (84), 10 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-08 10:11:12,253 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:12,253 INFO L93 Difference]: Finished difference Result 124 states and 159 transitions. [2024-11-08 10:11:12,253 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-08 10:11:12,253 INFO L78 Accepts]: Start accepts. Automaton has has 51 states, 51 states have (on average 1.6470588235294117) internal successors, (84), 51 states have internal predecessors, (84), 10 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 50 [2024-11-08 10:11:12,254 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:12,254 INFO L225 Difference]: With dead ends: 124 [2024-11-08 10:11:12,254 INFO L226 Difference]: Without dead ends: 120 [2024-11-08 10:11:12,256 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 78 SyntacticMatches, 2 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1469 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=649, Invalid=4181, Unknown=0, NotChecked=0, Total=4830 [2024-11-08 10:11:12,256 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 134 mSDsluCounter, 314 mSDsCounter, 0 mSdLazyCounter, 918 mSolverCounterSat, 70 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 135 SdHoareTripleChecker+Valid, 344 SdHoareTripleChecker+Invalid, 988 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 70 IncrementalHoareTripleChecker+Valid, 918 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:12,256 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [135 Valid, 344 Invalid, 988 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [70 Valid, 918 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-08 10:11:12,257 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2024-11-08 10:11:12,267 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 76. [2024-11-08 10:11:12,267 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 76 states, 66 states have (on average 1.303030303030303) internal successors, (86), 66 states have internal predecessors, (86), 8 states have call successors, (8), 1 states have call predecessors, (8), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-08 10:11:12,268 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 102 transitions. [2024-11-08 10:11:12,268 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 102 transitions. Word has length 50 [2024-11-08 10:11:12,268 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:12,268 INFO L471 AbstractCegarLoop]: Abstraction has 76 states and 102 transitions. [2024-11-08 10:11:12,269 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 51 states, 51 states have (on average 1.6470588235294117) internal successors, (84), 51 states have internal predecessors, (84), 10 states have call successors, (10), 1 states have call predecessors, (10), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-08 10:11:12,269 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 102 transitions. [2024-11-08 10:11:12,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-11-08 10:11:12,270 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:12,270 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:12,285 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-08 10:11:12,470 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-08 10:11:12,471 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:12,471 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:12,471 INFO L85 PathProgramCache]: Analyzing trace with hash 19833936, now seen corresponding path program 5 times [2024-11-08 10:11:12,471 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:12,471 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1923827595] [2024-11-08 10:11:12,471 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:12,471 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:12,487 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:12,581 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:12,583 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:12,584 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:12,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:12,586 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 10:11:12,587 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:12,588 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-08 10:11:12,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:12,590 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 6 proven. 11 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-08 10:11:12,591 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:12,591 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1923827595] [2024-11-08 10:11:12,591 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1923827595] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:12,591 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1786177408] [2024-11-08 10:11:12,591 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-08 10:11:12,591 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:12,591 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:12,594 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:11:12,595 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-08 10:11:12,677 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2024-11-08 10:11:12,677 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:11:12,679 INFO L255 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-08 10:11:12,680 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:12,762 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 9 proven. 8 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-08 10:11:12,762 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:12,839 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 9 proven. 8 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-08 10:11:12,840 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1786177408] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:11:12,840 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:11:12,840 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2024-11-08 10:11:12,840 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [675231985] [2024-11-08 10:11:12,840 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:12,841 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-08 10:11:12,841 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:12,841 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-08 10:11:12,841 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=129, Unknown=0, NotChecked=0, Total=182 [2024-11-08 10:11:12,841 INFO L87 Difference]: Start difference. First operand 76 states and 102 transitions. Second operand has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-08 10:11:12,967 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:12,968 INFO L93 Difference]: Finished difference Result 136 states and 176 transitions. [2024-11-08 10:11:12,968 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-08 10:11:12,968 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 52 [2024-11-08 10:11:12,968 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:12,969 INFO L225 Difference]: With dead ends: 136 [2024-11-08 10:11:12,969 INFO L226 Difference]: Without dead ends: 110 [2024-11-08 10:11:12,969 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 102 SyntacticMatches, 5 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 90 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=72, Invalid=168, Unknown=0, NotChecked=0, Total=240 [2024-11-08 10:11:12,970 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 33 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 136 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 136 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:12,970 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 112 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 136 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 10:11:12,970 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2024-11-08 10:11:12,983 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 90. [2024-11-08 10:11:12,983 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 80 states have (on average 1.25) internal successors, (100), 80 states have internal predecessors, (100), 8 states have call successors, (8), 1 states have call predecessors, (8), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-08 10:11:12,984 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 116 transitions. [2024-11-08 10:11:12,984 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 116 transitions. Word has length 52 [2024-11-08 10:11:12,984 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:12,985 INFO L471 AbstractCegarLoop]: Abstraction has 90 states and 116 transitions. [2024-11-08 10:11:12,985 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-08 10:11:12,985 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 116 transitions. [2024-11-08 10:11:12,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-11-08 10:11:12,986 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:12,986 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 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, 1] [2024-11-08 10:11:13,002 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-08 10:11:13,186 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-08 10:11:13,187 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:13,187 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:13,187 INFO L85 PathProgramCache]: Analyzing trace with hash 1219923716, now seen corresponding path program 3 times [2024-11-08 10:11:13,187 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:13,187 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [219318878] [2024-11-08 10:11:13,187 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:13,188 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:13,201 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:13,297 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:13,299 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:13,300 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:13,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:13,302 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 10:11:13,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:13,304 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-08 10:11:13,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:13,306 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-11-08 10:11:13,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:13,307 INFO L134 CoverageAnalysis]: Checked inductivity of 69 backedges. 1 proven. 24 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-11-08 10:11:13,307 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:13,308 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [219318878] [2024-11-08 10:11:13,308 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [219318878] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:13,308 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1517286428] [2024-11-08 10:11:13,308 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 10:11:13,308 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:13,308 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:13,310 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:11:13,311 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-08 10:11:13,381 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-08 10:11:13,382 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:11:13,382 INFO L255 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-08 10:11:13,384 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:13,466 INFO L134 CoverageAnalysis]: Checked inductivity of 69 backedges. 8 proven. 17 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-11-08 10:11:13,467 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:13,550 INFO L134 CoverageAnalysis]: Checked inductivity of 69 backedges. 8 proven. 17 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-11-08 10:11:13,551 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1517286428] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:11:13,551 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:11:13,551 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2024-11-08 10:11:13,551 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1683664317] [2024-11-08 10:11:13,551 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:13,551 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-08 10:11:13,551 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:13,552 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-08 10:11:13,552 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=129, Unknown=0, NotChecked=0, Total=182 [2024-11-08 10:11:13,552 INFO L87 Difference]: Start difference. First operand 90 states and 116 transitions. Second operand has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 14 states have internal predecessors, (51), 5 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-08 10:11:13,705 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:13,705 INFO L93 Difference]: Finished difference Result 102 states and 128 transitions. [2024-11-08 10:11:13,705 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-08 10:11:13,705 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 14 states have internal predecessors, (51), 5 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 60 [2024-11-08 10:11:13,706 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:13,706 INFO L225 Difference]: With dead ends: 102 [2024-11-08 10:11:13,706 INFO L226 Difference]: Without dead ends: 92 [2024-11-08 10:11:13,707 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 119 SyntacticMatches, 6 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 113 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=100, Invalid=280, Unknown=0, NotChecked=0, Total=380 [2024-11-08 10:11:13,707 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 46 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 212 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 237 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 212 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:13,707 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 161 Invalid, 237 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 212 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 10:11:13,708 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2024-11-08 10:11:13,716 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 49. [2024-11-08 10:11:13,716 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 42 states have (on average 1.2142857142857142) internal successors, (51), 42 states have internal predecessors, (51), 5 states have call successors, (5), 1 states have call predecessors, (5), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-08 10:11:13,717 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 61 transitions. [2024-11-08 10:11:13,717 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 61 transitions. Word has length 60 [2024-11-08 10:11:13,717 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:13,717 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 61 transitions. [2024-11-08 10:11:13,718 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 14 states have internal predecessors, (51), 5 states have call successors, (6), 1 states have call predecessors, (6), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-08 10:11:13,718 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 61 transitions. [2024-11-08 10:11:13,718 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2024-11-08 10:11:13,718 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:13,719 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:13,735 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-08 10:11:13,919 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-08 10:11:13,920 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:13,920 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:13,920 INFO L85 PathProgramCache]: Analyzing trace with hash 1992349514, now seen corresponding path program 6 times [2024-11-08 10:11:13,920 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:13,920 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [911260166] [2024-11-08 10:11:13,920 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:13,920 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:13,939 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:15,566 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:15,567 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:15,568 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:15,569 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:15,570 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-08 10:11:15,570 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:15,572 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-08 10:11:15,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:15,577 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-11-08 10:11:15,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:15,585 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 0 proven. 39 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-08 10:11:15,585 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:15,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [911260166] [2024-11-08 10:11:15,585 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [911260166] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:15,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1867091489] [2024-11-08 10:11:15,586 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-08 10:11:15,586 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:15,586 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:15,589 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-08 10:11:15,591 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-08 10:11:15,677 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2024-11-08 10:11:15,677 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:11:15,679 INFO L255 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 60 conjuncts are in the unsatisfiable core [2024-11-08 10:11:15,687 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:16,639 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-08 10:11:16,801 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 17 [2024-11-08 10:11:16,969 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:16,969 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 61 treesize of output 29 [2024-11-08 10:11:16,974 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 21 [2024-11-08 10:11:17,354 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:17,354 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 41 treesize of output 17 [2024-11-08 10:11:17,502 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 16 proven. 48 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-08 10:11:17,502 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:18,346 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 93 treesize of output 87 [2024-11-08 10:11:18,377 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:18,378 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 328566 treesize of output 308086 [2024-11-08 10:11:19,062 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-08 10:11:19,063 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 81 treesize of output 99 [2024-11-08 10:11:19,454 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 10 proven. 29 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-08 10:11:19,454 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1867091489] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:11:19,454 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:11:19,455 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 30, 27] total 79 [2024-11-08 10:11:19,455 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2104458188] [2024-11-08 10:11:19,455 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:19,455 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 79 states [2024-11-08 10:11:19,455 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:19,456 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 79 interpolants. [2024-11-08 10:11:19,458 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=695, Invalid=5467, Unknown=0, NotChecked=0, Total=6162 [2024-11-08 10:11:19,458 INFO L87 Difference]: Start difference. First operand 49 states and 61 transitions. Second operand has 79 states, 78 states have (on average 1.5256410256410255) internal successors, (119), 77 states have internal predecessors, (119), 13 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-08 10:11:41,892 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0, 1] [2024-11-08 10:11:49,301 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0, 1] [2024-11-08 10:11:59,267 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0, 1]