./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/array-cav19/array_init_nondet_vars.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_init_nondet_vars.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 b36a429fc2ac304c1da00c90b438bd7c9bbfb7e9d7c6704fc9e7805ab1ca424f --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-08 10:10:10,473 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-08 10:10:10,520 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:10,532 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-08 10:10:10,533 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-08 10:10:10,563 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-08 10:10:10,568 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-08 10:10:10,568 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-08 10:10:10,568 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-08 10:10:10,568 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-08 10:10:10,569 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-08 10:10:10,569 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-08 10:10:10,569 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-08 10:10:10,569 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-08 10:10:10,570 INFO L153 SettingsManager]: * Use SBE=true [2024-11-08 10:10:10,570 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-08 10:10:10,570 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-08 10:10:10,571 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-08 10:10:10,571 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-08 10:10:10,571 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-08 10:10:10,572 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-08 10:10:10,572 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-08 10:10:10,572 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-08 10:10:10,573 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-08 10:10:10,573 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-08 10:10:10,573 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-08 10:10:10,573 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-08 10:10:10,574 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-08 10:10:10,574 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-08 10:10:10,574 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-08 10:10:10,575 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-08 10:10:10,575 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-08 10:10:10,575 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 10:10:10,575 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-08 10:10:10,576 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-08 10:10:10,576 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-08 10:10:10,576 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-08 10:10:10,576 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-08 10:10:10,576 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-08 10:10:10,577 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-08 10:10:10,577 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-08 10:10:10,577 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-08 10:10:10,578 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 -> b36a429fc2ac304c1da00c90b438bd7c9bbfb7e9d7c6704fc9e7805ab1ca424f [2024-11-08 10:10:10,788 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-08 10:10:10,815 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-08 10:10:10,817 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-08 10:10:10,819 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-08 10:10:10,819 INFO L274 PluginConnector]: CDTParser initialized [2024-11-08 10:10:10,820 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-cav19/array_init_nondet_vars.c [2024-11-08 10:10:12,027 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-08 10:10:12,203 INFO L384 CDTParser]: Found 1 translation units. [2024-11-08 10:10:12,203 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-cav19/array_init_nondet_vars.c [2024-11-08 10:10:12,209 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/585fd4a59/b6d62d1ad5de449f893073c7a0064639/FLAG05c993173 [2024-11-08 10:10:12,617 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/585fd4a59/b6d62d1ad5de449f893073c7a0064639 [2024-11-08 10:10:12,619 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-08 10:10:12,620 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-08 10:10:12,621 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-08 10:10:12,621 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-08 10:10:12,626 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-08 10:10:12,626 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 10:10:12" (1/1) ... [2024-11-08 10:10:12,627 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6a2686e5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:12, skipping insertion in model container [2024-11-08 10:10:12,627 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 10:10:12" (1/1) ... [2024-11-08 10:10:12,642 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-08 10:10:12,778 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_init_nondet_vars.c[413,426] [2024-11-08 10:10:12,796 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 10:10:12,803 INFO L200 MainTranslator]: Completed pre-run [2024-11-08 10:10:12,812 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_init_nondet_vars.c[413,426] [2024-11-08 10:10:12,816 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 10:10:12,830 INFO L204 MainTranslator]: Completed translation [2024-11-08 10:10:12,830 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:12 WrapperNode [2024-11-08 10:10:12,830 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-08 10:10:12,831 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-08 10:10:12,831 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-08 10:10:12,831 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-08 10:10:12,836 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:12" (1/1) ... [2024-11-08 10:10:12,841 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:12" (1/1) ... [2024-11-08 10:10:12,868 INFO L138 Inliner]: procedures = 15, calls = 16, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 57 [2024-11-08 10:10:12,868 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-08 10:10:12,869 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-08 10:10:12,869 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-08 10:10:12,869 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-08 10:10:12,877 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:12" (1/1) ... [2024-11-08 10:10:12,878 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:12" (1/1) ... [2024-11-08 10:10:12,879 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:12" (1/1) ... [2024-11-08 10:10:12,888 INFO L175 MemorySlicer]: Split 4 memory accesses to 2 slices as follows [2, 2]. 50 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0]. The 1 writes are split as follows [0, 1]. [2024-11-08 10:10:12,888 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:12" (1/1) ... [2024-11-08 10:10:12,888 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:12" (1/1) ... [2024-11-08 10:10:12,892 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:12" (1/1) ... [2024-11-08 10:10:12,903 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:12" (1/1) ... [2024-11-08 10:10:12,904 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:12" (1/1) ... [2024-11-08 10:10:12,905 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:12" (1/1) ... [2024-11-08 10:10:12,906 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-08 10:10:12,907 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-08 10:10:12,907 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-08 10:10:12,907 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-08 10:10:12,908 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:12" (1/1) ... [2024-11-08 10:10:12,915 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 10:10:12,924 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:10:12,939 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:12,948 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:12,980 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-08 10:10:12,980 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-08 10:10:12,981 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-08 10:10:12,981 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-08 10:10:12,981 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-08 10:10:12,981 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-08 10:10:12,981 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-08 10:10:12,982 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-08 10:10:12,983 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-08 10:10:12,983 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-08 10:10:12,983 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-08 10:10:12,983 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-08 10:10:12,983 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-08 10:10:13,043 INFO L238 CfgBuilder]: Building ICFG [2024-11-08 10:10:13,045 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-08 10:10:13,201 INFO L? ?]: Removed 10 outVars from TransFormulas that were not future-live. [2024-11-08 10:10:13,203 INFO L287 CfgBuilder]: Performing block encoding [2024-11-08 10:10:13,221 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-08 10:10:13,221 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-08 10:10:13,221 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 10:10:13 BoogieIcfgContainer [2024-11-08 10:10:13,221 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-08 10:10:13,223 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-08 10:10:13,223 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-08 10:10:13,226 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-08 10:10:13,226 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.11 10:10:12" (1/3) ... [2024-11-08 10:10:13,228 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@53b0aad5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 10:10:13, skipping insertion in model container [2024-11-08 10:10:13,228 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 10:10:12" (2/3) ... [2024-11-08 10:10:13,228 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@53b0aad5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 10:10:13, skipping insertion in model container [2024-11-08 10:10:13,229 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 10:10:13" (3/3) ... [2024-11-08 10:10:13,230 INFO L112 eAbstractionObserver]: Analyzing ICFG array_init_nondet_vars.c [2024-11-08 10:10:13,244 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-08 10:10:13,244 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-08 10:10:13,299 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-08 10:10:13,305 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;@129215f2, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-08 10:10:13,305 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-08 10:10:13,309 INFO L276 IsEmpty]: Start isEmpty. Operand has 25 states, 19 states have (on average 1.368421052631579) internal successors, (26), 20 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:13,314 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-08 10:10:13,315 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:13,316 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:13,317 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:13,322 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:13,323 INFO L85 PathProgramCache]: Analyzing trace with hash -687560493, now seen corresponding path program 1 times [2024-11-08 10:10:13,331 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:13,332 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [20966362] [2024-11-08 10:10:13,332 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:13,333 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:13,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:13,457 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:13,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:13,465 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:13,467 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:13,471 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:13,472 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:13,472 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [20966362] [2024-11-08 10:10:13,472 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [20966362] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 10:10:13,473 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 10:10:13,473 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-08 10:10:13,474 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [495674559] [2024-11-08 10:10:13,475 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 10:10:13,478 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-08 10:10:13,478 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:13,496 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-08 10:10:13,497 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 10:10:13,499 INFO L87 Difference]: Start difference. First operand has 25 states, 19 states have (on average 1.368421052631579) internal successors, (26), 20 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) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 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:13,512 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:13,512 INFO L93 Difference]: Finished difference Result 47 states and 63 transitions. [2024-11-08 10:10:13,513 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-08 10:10:13,514 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 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 19 [2024-11-08 10:10:13,514 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:13,521 INFO L225 Difference]: With dead ends: 47 [2024-11-08 10:10:13,521 INFO L226 Difference]: Without dead ends: 21 [2024-11-08 10:10:13,524 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:13,526 INFO L432 NwaCegarLoop]: 28 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, 28 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:13,527 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 28 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:13,540 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2024-11-08 10:10:13,552 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2024-11-08 10:10:13,553 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 16 states have (on average 1.125) internal successors, (18), 16 states have internal predecessors, (18), 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:13,554 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 24 transitions. [2024-11-08 10:10:13,555 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 24 transitions. Word has length 19 [2024-11-08 10:10:13,555 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:13,555 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 24 transitions. [2024-11-08 10:10:13,555 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 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:13,556 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 24 transitions. [2024-11-08 10:10:13,557 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-08 10:10:13,557 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:13,557 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:13,557 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-08 10:10:13,558 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:13,558 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:13,558 INFO L85 PathProgramCache]: Analyzing trace with hash -1294753969, now seen corresponding path program 1 times [2024-11-08 10:10:13,558 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:13,559 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1192957761] [2024-11-08 10:10:13,559 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:13,559 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:13,600 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:13,792 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:13,794 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:13,801 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:13,802 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:13,808 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:13,808 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:13,808 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1192957761] [2024-11-08 10:10:13,809 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1192957761] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 10:10:13,809 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 10:10:13,809 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 10:10:13,809 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1395841131] [2024-11-08 10:10:13,809 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 10:10:13,810 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 10:10:13,810 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:13,811 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 10:10:13,811 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2024-11-08 10:10:13,811 INFO L87 Difference]: Start difference. First operand 21 states and 24 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 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:13,852 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:13,853 INFO L93 Difference]: Finished difference Result 39 states and 44 transitions. [2024-11-08 10:10:13,853 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 10:10:13,853 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 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 19 [2024-11-08 10:10:13,853 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:13,854 INFO L225 Difference]: With dead ends: 39 [2024-11-08 10:10:13,854 INFO L226 Difference]: Without dead ends: 31 [2024-11-08 10:10:13,854 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 6 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:13,855 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 7 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 49 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 10:10:13,856 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 49 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 10:10:13,856 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-08 10:10:13,861 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 22. [2024-11-08 10:10:13,861 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 17 states have (on average 1.1176470588235294) internal successors, (19), 17 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-08 10:10:13,861 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 25 transitions. [2024-11-08 10:10:13,862 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 25 transitions. Word has length 19 [2024-11-08 10:10:13,862 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:13,862 INFO L471 AbstractCegarLoop]: Abstraction has 22 states and 25 transitions. [2024-11-08 10:10:13,862 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 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:13,862 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 25 transitions. [2024-11-08 10:10:13,863 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-08 10:10:13,863 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:13,863 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] [2024-11-08 10:10:13,863 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-08 10:10:13,863 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:13,864 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:13,864 INFO L85 PathProgramCache]: Analyzing trace with hash -554531054, now seen corresponding path program 1 times [2024-11-08 10:10:13,864 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:13,864 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1128947956] [2024-11-08 10:10:13,864 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:13,865 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:13,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:14,239 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:14,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:14,245 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:14,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:14,287 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:10:14,290 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:14,314 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-08 10:10:14,315 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:14,315 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1128947956] [2024-11-08 10:10:14,315 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1128947956] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:10:14,316 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [276969191] [2024-11-08 10:10:14,316 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:14,316 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:10:14,316 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:10:14,321 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:14,324 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:14,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:14,384 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-08 10:10:14,389 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:10:14,615 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:14,733 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 22 treesize of output 10 [2024-11-08 10:10:14,748 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-08 10:10:14,749 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:10:14,792 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 19 treesize of output 17 [2024-11-08 10:10:14,799 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 23 treesize of output 19 [2024-11-08 10:10:14,916 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-08 10:10:14,918 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [276969191] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:10:14,918 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:10:14,918 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11, 10] total 19 [2024-11-08 10:10:14,918 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [586787334] [2024-11-08 10:10:14,918 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:10:14,919 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-08 10:10:14,919 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:14,920 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-08 10:10:14,922 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=282, Unknown=0, NotChecked=0, Total=342 [2024-11-08 10:10:14,923 INFO L87 Difference]: Start difference. First operand 22 states and 25 transitions. Second operand has 19 states, 18 states have (on average 1.8333333333333333) internal successors, (33), 15 states have internal predecessors, (33), 4 states have call successors, (5), 1 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-08 10:10:15,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:15,116 INFO L93 Difference]: Finished difference Result 47 states and 53 transitions. [2024-11-08 10:10:15,116 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-08 10:10:15,116 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 1.8333333333333333) internal successors, (33), 15 states have internal predecessors, (33), 4 states have call successors, (5), 1 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 4 states have call successors, (5) Word has length 27 [2024-11-08 10:10:15,116 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:15,117 INFO L225 Difference]: With dead ends: 47 [2024-11-08 10:10:15,117 INFO L226 Difference]: Without dead ends: 45 [2024-11-08 10:10:15,118 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 50 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 69 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=96, Invalid=366, Unknown=0, NotChecked=0, Total=462 [2024-11-08 10:10:15,119 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 59 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 154 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 159 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 154 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 10:10:15,121 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 159 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 154 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 10:10:15,121 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-11-08 10:10:15,126 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 29. [2024-11-08 10:10:15,126 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 23 states have (on average 1.1304347826086956) internal successors, (26), 23 states have internal predecessors, (26), 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:15,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 34 transitions. [2024-11-08 10:10:15,128 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 34 transitions. Word has length 27 [2024-11-08 10:10:15,129 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:15,129 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 34 transitions. [2024-11-08 10:10:15,129 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 1.8333333333333333) internal successors, (33), 15 states have internal predecessors, (33), 4 states have call successors, (5), 1 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-08 10:10:15,129 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 34 transitions. [2024-11-08 10:10:15,130 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-08 10:10:15,131 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:15,131 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 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:15,144 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-08 10:10:15,335 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:10:15,336 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:15,337 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:15,340 INFO L85 PathProgramCache]: Analyzing trace with hash -1909003512, now seen corresponding path program 1 times [2024-11-08 10:10:15,340 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:15,341 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1043199150] [2024-11-08 10:10:15,341 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:15,341 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:15,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:15,419 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:15,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:15,421 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:15,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:15,424 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:10:15,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:15,427 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 1 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:15,427 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:15,428 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1043199150] [2024-11-08 10:10:15,428 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1043199150] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:10:15,429 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [167423706] [2024-11-08 10:10:15,429 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:15,429 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:10:15,429 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:10:15,431 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:15,432 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:15,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:15,475 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-08 10:10:15,476 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:10:15,524 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:15,524 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:10:15,569 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:15,569 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [167423706] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:10:15,569 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:10:15,569 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2024-11-08 10:10:15,569 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1616232607] [2024-11-08 10:10:15,569 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:10:15,570 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-08 10:10:15,570 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:15,570 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-08 10:10:15,572 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2024-11-08 10:10:15,572 INFO L87 Difference]: Start difference. First operand 29 states and 34 transitions. Second operand has 11 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 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:15,622 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:15,622 INFO L93 Difference]: Finished difference Result 53 states and 59 transitions. [2024-11-08 10:10:15,623 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-08 10:10:15,623 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 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 31 [2024-11-08 10:10:15,623 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:15,624 INFO L225 Difference]: With dead ends: 53 [2024-11-08 10:10:15,624 INFO L226 Difference]: Without dead ends: 41 [2024-11-08 10:10:15,624 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 61 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:15,625 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 12 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 70 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 73 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 70 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 10:10:15,625 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 116 Invalid, 73 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 70 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 10:10:15,625 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-11-08 10:10:15,628 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 26. [2024-11-08 10:10:15,628 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 20 states have (on average 1.1) internal successors, (22), 20 states have internal predecessors, (22), 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:15,629 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 30 transitions. [2024-11-08 10:10:15,629 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 30 transitions. Word has length 31 [2024-11-08 10:10:15,629 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:15,629 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 30 transitions. [2024-11-08 10:10:15,629 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 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:15,629 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 30 transitions. [2024-11-08 10:10:15,630 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-08 10:10:15,630 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:15,630 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:15,662 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-08 10:10:15,834 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2024-11-08 10:10:15,835 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:15,835 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:15,835 INFO L85 PathProgramCache]: Analyzing trace with hash -1118110763, now seen corresponding path program 2 times [2024-11-08 10:10:15,836 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:15,836 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [680039894] [2024-11-08 10:10:15,836 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:15,836 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:15,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:16,127 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:16,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:16,129 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:16,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:16,157 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:10:16,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:16,173 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 10:10:16,175 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:16,178 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 12 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:16,179 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:16,179 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [680039894] [2024-11-08 10:10:16,179 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [680039894] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:10:16,179 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [929524125] [2024-11-08 10:10:16,179 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 10:10:16,180 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:10:16,180 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:10:16,183 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:16,184 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:16,230 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 10:10:16,230 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:10:16,232 INFO L255 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 36 conjuncts are in the unsatisfiable core [2024-11-08 10:10:16,234 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:10:16,374 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:16,558 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 30 treesize of output 14 [2024-11-08 10:10:16,672 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 22 treesize of output 10 [2024-11-08 10:10:16,687 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 3 proven. 15 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:16,687 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:10:25,033 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [929524125] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:10:25,033 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 10:10:25,033 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 17] total 25 [2024-11-08 10:10:25,034 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1881452988] [2024-11-08 10:10:25,034 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 10:10:25,034 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-08 10:10:25,034 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:25,038 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-08 10:10:25,038 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=145, Invalid=665, Unknown=2, NotChecked=0, Total=812 [2024-11-08 10:10:25,039 INFO L87 Difference]: Start difference. First operand 26 states and 30 transitions. Second operand has 25 states, 24 states have (on average 1.5) internal successors, (36), 20 states have internal predecessors, (36), 6 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (8), 8 states have call predecessors, (8), 6 states have call successors, (8) [2024-11-08 10:10:29,075 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] [2024-11-08 10:10:33,362 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] [2024-11-08 10:10:41,491 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] [2024-11-08 10:10:41,491 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:41,491 INFO L93 Difference]: Finished difference Result 75 states and 84 transitions. [2024-11-08 10:10:41,494 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-08 10:10:41,495 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 24 states have (on average 1.5) internal successors, (36), 20 states have internal predecessors, (36), 6 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (8), 8 states have call predecessors, (8), 6 states have call successors, (8) Word has length 35 [2024-11-08 10:10:41,495 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:41,495 INFO L225 Difference]: With dead ends: 75 [2024-11-08 10:10:41,496 INFO L226 Difference]: Without dead ends: 73 [2024-11-08 10:10:41,496 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 34 SyntacticMatches, 2 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 388 ImplicationChecksByTransitivity, 12.9s TimeCoverageRelationStatistics Valid=342, Invalid=1377, Unknown=3, NotChecked=0, Total=1722 [2024-11-08 10:10:41,497 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 226 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 249 mSolverCounterSat, 34 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 12.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 226 SdHoareTripleChecker+Valid, 172 SdHoareTripleChecker+Invalid, 286 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 249 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 12.2s IncrementalHoareTripleChecker+Time [2024-11-08 10:10:41,497 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [226 Valid, 172 Invalid, 286 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 249 Invalid, 3 Unknown, 0 Unchecked, 12.2s Time] [2024-11-08 10:10:41,498 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2024-11-08 10:10:41,507 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 41. [2024-11-08 10:10:41,507 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 32 states have internal predecessors, (35), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 10:10:41,508 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2024-11-08 10:10:41,508 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 35 [2024-11-08 10:10:41,508 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:41,508 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2024-11-08 10:10:41,509 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 24 states have (on average 1.5) internal successors, (36), 20 states have internal predecessors, (36), 6 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (8), 8 states have call predecessors, (8), 6 states have call successors, (8) [2024-11-08 10:10:41,509 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2024-11-08 10:10:41,511 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-08 10:10:41,511 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:41,512 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:41,525 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:41,712 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:10:41,712 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:41,714 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:41,714 INFO L85 PathProgramCache]: Analyzing trace with hash 1711359563, now seen corresponding path program 2 times [2024-11-08 10:10:41,715 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:41,715 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [553586168] [2024-11-08 10:10:41,715 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:41,715 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:41,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:42,004 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:42,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:42,006 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:42,008 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:42,034 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:10:42,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:42,040 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 10:10:42,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:42,050 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 9 proven. 11 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:42,051 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:42,051 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [553586168] [2024-11-08 10:10:42,051 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [553586168] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:10:42,051 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1528467549] [2024-11-08 10:10:42,051 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 10:10:42,051 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:10:42,051 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:10:42,056 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:42,059 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:42,104 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 10:10:42,104 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:10:42,105 INFO L255 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-08 10:10:42,107 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:10:42,216 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 1 [2024-11-08 10:10:42,355 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 28 treesize of output 10 [2024-11-08 10:10:42,374 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 9 proven. 11 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:42,374 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:10:42,505 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 19 treesize of output 17 [2024-11-08 10:10:42,507 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 23 treesize of output 19 [2024-11-08 10:10:42,653 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 9 proven. 11 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:42,653 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1528467549] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:10:42,653 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:10:42,654 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14, 14] total 32 [2024-11-08 10:10:42,654 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [313876493] [2024-11-08 10:10:42,654 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:10:42,654 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2024-11-08 10:10:42,654 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:42,655 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2024-11-08 10:10:42,655 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=158, Invalid=834, Unknown=0, NotChecked=0, Total=992 [2024-11-08 10:10:42,655 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 32 states, 32 states have (on average 1.75) internal successors, (56), 27 states have internal predecessors, (56), 7 states have call successors, (8), 1 states have call predecessors, (8), 2 states have return successors, (9), 9 states have call predecessors, (9), 7 states have call successors, (9) [2024-11-08 10:10:43,179 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:10:43,180 INFO L93 Difference]: Finished difference Result 74 states and 84 transitions. [2024-11-08 10:10:43,180 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-11-08 10:10:43,180 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 32 states have (on average 1.75) internal successors, (56), 27 states have internal predecessors, (56), 7 states have call successors, (8), 1 states have call predecessors, (8), 2 states have return successors, (9), 9 states have call predecessors, (9), 7 states have call successors, (9) Word has length 39 [2024-11-08 10:10:43,181 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:10:43,182 INFO L225 Difference]: With dead ends: 74 [2024-11-08 10:10:43,182 INFO L226 Difference]: Without dead ends: 72 [2024-11-08 10:10:43,183 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 65 SyntacticMatches, 2 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 539 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=439, Invalid=1723, Unknown=0, NotChecked=0, Total=2162 [2024-11-08 10:10:43,183 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 191 mSDsluCounter, 177 mSDsCounter, 0 mSdLazyCounter, 281 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 192 SdHoareTripleChecker+Valid, 196 SdHoareTripleChecker+Invalid, 315 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 281 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-08 10:10:43,186 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [192 Valid, 196 Invalid, 315 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 281 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-08 10:10:43,187 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2024-11-08 10:10:43,195 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 54. [2024-11-08 10:10:43,196 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 44 states have (on average 1.0909090909090908) internal successors, (48), 45 states have internal predecessors, (48), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 10:10:43,200 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 62 transitions. [2024-11-08 10:10:43,201 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 62 transitions. Word has length 39 [2024-11-08 10:10:43,201 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:10:43,201 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 62 transitions. [2024-11-08 10:10:43,201 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 32 states have (on average 1.75) internal successors, (56), 27 states have internal predecessors, (56), 7 states have call successors, (8), 1 states have call predecessors, (8), 2 states have return successors, (9), 9 states have call predecessors, (9), 7 states have call successors, (9) [2024-11-08 10:10:43,202 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 62 transitions. [2024-11-08 10:10:43,202 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-08 10:10:43,205 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:10:43,205 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:10:43,220 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:43,406 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:10:43,406 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:10:43,407 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:10:43,407 INFO L85 PathProgramCache]: Analyzing trace with hash -181817714, now seen corresponding path program 3 times [2024-11-08 10:10:43,408 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:10:43,408 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [141896720] [2024-11-08 10:10:43,408 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:10:43,408 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:10:43,421 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:43,661 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:10:43,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:43,664 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:10:43,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:43,686 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:10:43,688 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:43,689 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 10:10:43,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:43,698 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-08 10:10:43,700 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:10:43,702 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 9 proven. 26 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2024-11-08 10:10:43,702 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:10:43,702 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [141896720] [2024-11-08 10:10:43,702 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [141896720] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:10:43,702 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [675631527] [2024-11-08 10:10:43,702 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 10:10:43,702 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:10:43,702 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:10:43,704 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:43,705 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:43,754 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-08 10:10:43,755 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:10:43,756 INFO L255 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 38 conjuncts are in the unsatisfiable core [2024-11-08 10:10:43,758 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:10:43,869 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 1 [2024-11-08 10:10:44,026 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 38 treesize of output 16 [2024-11-08 10:10:44,195 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 28 treesize of output 10 [2024-11-08 10:10:44,214 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 19 proven. 26 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-08 10:10:44,215 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:10:56,438 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [675631527] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:10:56,439 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 10:10:56,439 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 18] total 29 [2024-11-08 10:10:56,439 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1036337207] [2024-11-08 10:10:56,439 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 10:10:56,439 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2024-11-08 10:10:56,439 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:10:56,440 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2024-11-08 10:10:56,440 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=151, Invalid=839, Unknown=2, NotChecked=0, Total=992 [2024-11-08 10:10:56,441 INFO L87 Difference]: Start difference. First operand 54 states and 62 transitions. Second operand has 29 states, 29 states have (on average 1.6896551724137931) internal successors, (49), 25 states have internal predecessors, (49), 7 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (9), 9 states have call predecessors, (9), 7 states have call successors, (9) [2024-11-08 10:11:00,919 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] [2024-11-08 10:11:05,069 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:05,069 INFO L93 Difference]: Finished difference Result 110 states and 119 transitions. [2024-11-08 10:11:05,069 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-08 10:11:05,069 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 29 states have (on average 1.6896551724137931) internal successors, (49), 25 states have internal predecessors, (49), 7 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (9), 9 states have call predecessors, (9), 7 states have call successors, (9) Word has length 47 [2024-11-08 10:11:05,070 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:05,070 INFO L225 Difference]: With dead ends: 110 [2024-11-08 10:11:05,070 INFO L226 Difference]: Without dead ends: 108 [2024-11-08 10:11:05,071 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 48 SyntacticMatches, 5 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 678 ImplicationChecksByTransitivity, 16.8s TimeCoverageRelationStatistics Valid=370, Invalid=1883, Unknown=3, NotChecked=0, Total=2256 [2024-11-08 10:11:05,071 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 180 mSDsluCounter, 265 mSDsCounter, 0 mSdLazyCounter, 465 mSolverCounterSat, 32 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 180 SdHoareTripleChecker+Valid, 287 SdHoareTripleChecker+Invalid, 498 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 465 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.3s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:05,072 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [180 Valid, 287 Invalid, 498 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 465 Invalid, 1 Unknown, 0 Unchecked, 4.3s Time] [2024-11-08 10:11:05,072 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2024-11-08 10:11:05,095 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 66. [2024-11-08 10:11:05,099 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 53 states have (on average 1.0943396226415094) internal successors, (58), 54 states have internal predecessors, (58), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-08 10:11:05,100 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 74 transitions. [2024-11-08 10:11:05,100 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 74 transitions. Word has length 47 [2024-11-08 10:11:05,100 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:05,100 INFO L471 AbstractCegarLoop]: Abstraction has 66 states and 74 transitions. [2024-11-08 10:11:05,100 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 1.6896551724137931) internal successors, (49), 25 states have internal predecessors, (49), 7 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (9), 9 states have call predecessors, (9), 7 states have call successors, (9) [2024-11-08 10:11:05,100 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 74 transitions. [2024-11-08 10:11:05,101 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-08 10:11:05,101 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:05,101 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:05,126 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:11:05,302 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:05,302 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:05,303 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:05,303 INFO L85 PathProgramCache]: Analyzing trace with hash -581569404, now seen corresponding path program 4 times [2024-11-08 10:11:05,303 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:05,303 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [764682574] [2024-11-08 10:11:05,303 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:05,303 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:05,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:05,645 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:05,647 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:05,648 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:05,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:05,685 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:11:05,687 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:05,691 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 10:11:05,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:05,695 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-08 10:11:05,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:05,706 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 12 proven. 29 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2024-11-08 10:11:05,706 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:05,706 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [764682574] [2024-11-08 10:11:05,706 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [764682574] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:05,706 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1839166256] [2024-11-08 10:11:05,706 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-08 10:11:05,706 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:05,707 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:05,708 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:05,709 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:05,760 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-08 10:11:05,760 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:11:05,764 INFO L255 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-08 10:11:05,770 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:05,952 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:06,111 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 22 treesize of output 10 [2024-11-08 10:11:06,131 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 12 proven. 29 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2024-11-08 10:11:06,131 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:06,220 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 19 treesize of output 17 [2024-11-08 10:11:06,221 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 23 treesize of output 19 [2024-11-08 10:11:06,392 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 12 proven. 29 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2024-11-08 10:11:06,393 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1839166256] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:11:06,393 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:11:06,393 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 14] total 35 [2024-11-08 10:11:06,393 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2063521396] [2024-11-08 10:11:06,393 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:06,394 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2024-11-08 10:11:06,394 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:06,394 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2024-11-08 10:11:06,395 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=154, Invalid=1036, Unknown=0, NotChecked=0, Total=1190 [2024-11-08 10:11:06,395 INFO L87 Difference]: Start difference. First operand 66 states and 74 transitions. Second operand has 35 states, 34 states have (on average 2.2941176470588234) internal successors, (78), 29 states have internal predecessors, (78), 11 states have call successors, (12), 1 states have call predecessors, (12), 2 states have return successors, (13), 13 states have call predecessors, (13), 11 states have call successors, (13) [2024-11-08 10:11:06,825 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:06,825 INFO L93 Difference]: Finished difference Result 101 states and 109 transitions. [2024-11-08 10:11:06,826 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-08 10:11:06,826 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 34 states have (on average 2.2941176470588234) internal successors, (78), 29 states have internal predecessors, (78), 11 states have call successors, (12), 1 states have call predecessors, (12), 2 states have return successors, (13), 13 states have call predecessors, (13), 11 states have call successors, (13) Word has length 51 [2024-11-08 10:11:06,826 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:06,827 INFO L225 Difference]: With dead ends: 101 [2024-11-08 10:11:06,827 INFO L226 Difference]: Without dead ends: 99 [2024-11-08 10:11:06,827 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 423 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=230, Invalid=1330, Unknown=0, NotChecked=0, Total=1560 [2024-11-08 10:11:06,828 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 58 mSDsluCounter, 449 mSDsCounter, 0 mSdLazyCounter, 691 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 482 SdHoareTripleChecker+Invalid, 697 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 691 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:06,828 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 482 Invalid, 697 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 691 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-08 10:11:06,828 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2024-11-08 10:11:06,835 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 67. [2024-11-08 10:11:06,835 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 54 states have (on average 1.0925925925925926) internal successors, (59), 55 states have internal predecessors, (59), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-08 10:11:06,835 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 75 transitions. [2024-11-08 10:11:06,836 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 75 transitions. Word has length 51 [2024-11-08 10:11:06,836 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:06,836 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 75 transitions. [2024-11-08 10:11:06,836 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 34 states have (on average 2.2941176470588234) internal successors, (78), 29 states have internal predecessors, (78), 11 states have call successors, (12), 1 states have call predecessors, (12), 2 states have return successors, (13), 13 states have call predecessors, (13), 11 states have call successors, (13) [2024-11-08 10:11:06,836 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 75 transitions. [2024-11-08 10:11:06,837 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-08 10:11:06,837 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:06,837 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:06,853 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-08 10:11:07,041 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:07,042 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:07,042 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:07,042 INFO L85 PathProgramCache]: Analyzing trace with hash -685431891, now seen corresponding path program 5 times [2024-11-08 10:11:07,042 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:07,042 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1574917923] [2024-11-08 10:11:07,042 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:07,042 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:07,051 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:07,140 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:07,141 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:07,142 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:07,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:07,143 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:11:07,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:07,145 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 10:11:07,146 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:07,147 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 19 proven. 19 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:11:07,147 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:07,147 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1574917923] [2024-11-08 10:11:07,147 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1574917923] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:07,147 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1643715540] [2024-11-08 10:11:07,147 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-08 10:11:07,147 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:07,147 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:07,149 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:07,150 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:07,201 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2024-11-08 10:11:07,201 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:11:07,202 INFO L255 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-08 10:11:07,203 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:07,308 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 32 proven. 6 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:11:07,308 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:07,408 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 32 proven. 6 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-08 10:11:07,408 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1643715540] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:11:07,408 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:11:07,408 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 23 [2024-11-08 10:11:07,409 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [895291225] [2024-11-08 10:11:07,409 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:07,409 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-08 10:11:07,409 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:07,410 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-08 10:11:07,410 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=137, Invalid=369, Unknown=0, NotChecked=0, Total=506 [2024-11-08 10:11:07,410 INFO L87 Difference]: Start difference. First operand 67 states and 75 transitions. Second operand has 23 states, 23 states have (on average 3.391304347826087) internal successors, (78), 23 states have internal predecessors, (78), 6 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-11-08 10:11:07,554 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:07,554 INFO L93 Difference]: Finished difference Result 133 states and 141 transitions. [2024-11-08 10:11:07,554 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-08 10:11:07,554 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 3.391304347826087) internal successors, (78), 23 states have internal predecessors, (78), 6 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) Word has length 51 [2024-11-08 10:11:07,555 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:07,555 INFO L225 Difference]: With dead ends: 133 [2024-11-08 10:11:07,555 INFO L226 Difference]: Without dead ends: 109 [2024-11-08 10:11:07,556 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 96 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 275 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=221, Invalid=649, Unknown=0, NotChecked=0, Total=870 [2024-11-08 10:11:07,556 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 112 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 120 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 113 SdHoareTripleChecker+Valid, 178 SdHoareTripleChecker+Invalid, 143 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 120 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:07,557 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [113 Valid, 178 Invalid, 143 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 120 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 10:11:07,557 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2024-11-08 10:11:07,571 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 83. [2024-11-08 10:11:07,571 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 70 states have (on average 1.0714285714285714) internal successors, (75), 71 states have internal predecessors, (75), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-08 10:11:07,573 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 91 transitions. [2024-11-08 10:11:07,573 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 91 transitions. Word has length 51 [2024-11-08 10:11:07,573 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:07,573 INFO L471 AbstractCegarLoop]: Abstraction has 83 states and 91 transitions. [2024-11-08 10:11:07,574 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 3.391304347826087) internal successors, (78), 23 states have internal predecessors, (78), 6 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-11-08 10:11:07,574 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 91 transitions. [2024-11-08 10:11:07,574 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2024-11-08 10:11:07,574 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:07,575 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:07,590 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-08 10:11:07,778 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:07,779 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:07,779 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:07,779 INFO L85 PathProgramCache]: Analyzing trace with hash -1453174918, now seen corresponding path program 6 times [2024-11-08 10:11:07,779 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:07,779 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1441748746] [2024-11-08 10:11:07,779 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:07,780 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:07,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:07,893 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:07,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:07,895 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:07,896 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:07,896 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:11:07,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:07,898 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 10:11:07,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:07,900 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-08 10:11:07,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:07,901 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 9 proven. 24 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-08 10:11:07,901 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:07,901 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1441748746] [2024-11-08 10:11:07,902 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1441748746] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:07,902 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1314940648] [2024-11-08 10:11:07,902 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-08 10:11:07,902 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:07,902 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:07,903 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:07,905 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:07,954 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2024-11-08 10:11:07,955 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:11:07,956 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-08 10:11:07,957 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:08,044 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 18 proven. 15 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-08 10:11:08,044 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:08,126 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 18 proven. 15 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-08 10:11:08,126 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1314940648] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:11:08,127 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:11:08,127 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2024-11-08 10:11:08,127 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [296749075] [2024-11-08 10:11:08,127 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:08,127 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-08 10:11:08,127 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:08,128 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-08 10:11:08,128 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=197, Unknown=0, NotChecked=0, Total=272 [2024-11-08 10:11:08,128 INFO L87 Difference]: Start difference. First operand 83 states and 91 transitions. Second operand has 17 states, 17 states have (on average 3.2941176470588234) internal successors, (56), 17 states have internal predecessors, (56), 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:08,221 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:08,221 INFO L93 Difference]: Finished difference Result 103 states and 110 transitions. [2024-11-08 10:11:08,221 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-08 10:11:08,221 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 3.2941176470588234) internal successors, (56), 17 states have internal predecessors, (56), 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 55 [2024-11-08 10:11:08,222 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:08,222 INFO L225 Difference]: With dead ends: 103 [2024-11-08 10:11:08,222 INFO L226 Difference]: Without dead ends: 86 [2024-11-08 10:11:08,223 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 107 SyntacticMatches, 7 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 156 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=108, Invalid=272, Unknown=0, NotChecked=0, Total=380 [2024-11-08 10:11:08,223 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 35 mSDsluCounter, 127 mSDsCounter, 0 mSdLazyCounter, 106 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 116 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 106 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:08,223 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 149 Invalid, 116 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 10:11:08,224 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2024-11-08 10:11:08,231 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 72. [2024-11-08 10:11:08,231 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 59 states have (on average 1.0677966101694916) internal successors, (63), 60 states have internal predecessors, (63), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-08 10:11:08,231 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 79 transitions. [2024-11-08 10:11:08,232 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 79 transitions. Word has length 55 [2024-11-08 10:11:08,232 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:08,232 INFO L471 AbstractCegarLoop]: Abstraction has 72 states and 79 transitions. [2024-11-08 10:11:08,232 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 3.2941176470588234) internal successors, (56), 17 states have internal predecessors, (56), 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:08,232 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 79 transitions. [2024-11-08 10:11:08,233 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-11-08 10:11:08,233 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:08,233 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 4, 4, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:08,246 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-08 10:11:08,434 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-08 10:11:08,434 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:08,435 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:08,435 INFO L85 PathProgramCache]: Analyzing trace with hash -1754460089, now seen corresponding path program 7 times [2024-11-08 10:11:08,435 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:08,435 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1826963585] [2024-11-08 10:11:08,435 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:08,435 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:08,449 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:08,837 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:08,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:08,839 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:08,840 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:08,860 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:11:08,862 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:08,863 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 10:11:08,864 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:08,866 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-08 10:11:08,867 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:08,878 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-08 10:11:08,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:08,884 INFO L134 CoverageAnalysis]: Checked inductivity of 96 backedges. 12 proven. 48 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-08 10:11:08,885 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:08,885 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1826963585] [2024-11-08 10:11:08,885 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1826963585] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:08,885 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [232248590] [2024-11-08 10:11:08,885 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-08 10:11:08,885 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:08,885 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:08,886 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:08,887 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:08,939 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:08,940 INFO L255 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-08 10:11:08,942 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:09,132 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:09,298 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-08 10:11:09,298 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 34 treesize of output 14 [2024-11-08 10:11:09,495 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 22 treesize of output 10 [2024-11-08 10:11:09,513 INFO L134 CoverageAnalysis]: Checked inductivity of 96 backedges. 26 proven. 48 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2024-11-08 10:11:09,513 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:13,650 WARN L851 $PredicateComparison]: unable to prove that (forall ((|ULTIMATE.start_main_~k~0#1| Int)) (< 4 (select (store (select |c_#memory_int#1| |c_ULTIMATE.start_main_~#a~0#1.base|) (+ (* |c_ULTIMATE.start_main_~i~0#1| 4) |c_ULTIMATE.start_main_~#a~0#1.offset|) (+ |c_ULTIMATE.start_main_~j~0#1| |ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~i~0#1|)) (+ |c_ULTIMATE.start_main_~#a~0#1.offset| 12)))) is different from false [2024-11-08 10:11:13,659 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [232248590] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:13,659 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 10:11:13,659 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 33 [2024-11-08 10:11:13,659 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2128297414] [2024-11-08 10:11:13,659 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:13,659 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2024-11-08 10:11:13,660 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:13,660 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2024-11-08 10:11:13,660 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=203, Invalid=1206, Unknown=1, NotChecked=72, Total=1482 [2024-11-08 10:11:13,661 INFO L87 Difference]: Start difference. First operand 72 states and 79 transitions. Second operand has 33 states, 31 states have (on average 2.032258064516129) internal successors, (63), 29 states have internal predecessors, (63), 10 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (11), 11 states have call predecessors, (11), 10 states have call successors, (11) [2024-11-08 10:11:17,714 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] [2024-11-08 10:11:21,748 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] [2024-11-08 10:11:22,084 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:22,084 INFO L93 Difference]: Finished difference Result 94 states and 99 transitions. [2024-11-08 10:11:22,085 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-08 10:11:22,085 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 31 states have (on average 2.032258064516129) internal successors, (63), 29 states have internal predecessors, (63), 10 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (11), 11 states have call predecessors, (11), 10 states have call successors, (11) Word has length 59 [2024-11-08 10:11:22,085 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:22,085 INFO L225 Difference]: With dead ends: 94 [2024-11-08 10:11:22,085 INFO L226 Difference]: Without dead ends: 92 [2024-11-08 10:11:22,086 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 67 SyntacticMatches, 1 SemanticMatches, 46 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 650 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=331, Invalid=1834, Unknown=1, NotChecked=90, Total=2256 [2024-11-08 10:11:22,086 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 110 mSDsluCounter, 180 mSDsCounter, 0 mSdLazyCounter, 457 mSolverCounterSat, 10 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 110 SdHoareTripleChecker+Valid, 201 SdHoareTripleChecker+Invalid, 469 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 457 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.2s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:22,086 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [110 Valid, 201 Invalid, 469 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 457 Invalid, 2 Unknown, 0 Unchecked, 8.2s Time] [2024-11-08 10:11:22,087 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2024-11-08 10:11:22,094 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 79. [2024-11-08 10:11:22,095 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 66 states have (on average 1.0454545454545454) internal successors, (69), 66 states have internal predecessors, (69), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 10:11:22,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 83 transitions. [2024-11-08 10:11:22,095 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 83 transitions. Word has length 59 [2024-11-08 10:11:22,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:22,096 INFO L471 AbstractCegarLoop]: Abstraction has 79 states and 83 transitions. [2024-11-08 10:11:22,096 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 31 states have (on average 2.032258064516129) internal successors, (63), 29 states have internal predecessors, (63), 10 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (11), 11 states have call predecessors, (11), 10 states have call successors, (11) [2024-11-08 10:11:22,096 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 83 transitions. [2024-11-08 10:11:22,096 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2024-11-08 10:11:22,097 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:22,097 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 4, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:22,110 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-08 10:11:22,300 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:22,301 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:22,301 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:22,301 INFO L85 PathProgramCache]: Analyzing trace with hash 120574397, now seen corresponding path program 8 times [2024-11-08 10:11:22,302 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:22,302 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1158034498] [2024-11-08 10:11:22,302 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:22,302 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:22,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:22,683 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:22,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:22,685 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:22,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:22,725 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:11:22,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:22,727 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 10:11:22,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:22,730 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-08 10:11:22,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:22,732 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-08 10:11:22,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:22,745 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 15 proven. 55 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-08 10:11:22,745 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:22,745 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1158034498] [2024-11-08 10:11:22,746 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1158034498] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:22,746 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [266983041] [2024-11-08 10:11:22,746 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-08 10:11:22,746 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:22,746 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:22,747 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:22,748 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:22,804 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-08 10:11:22,805 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:11:22,806 INFO L255 TraceCheckSpWp]: Trace formula consists of 175 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-08 10:11:22,807 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:23,005 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 1 [2024-11-08 10:11:23,171 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 28 treesize of output 10 [2024-11-08 10:11:23,190 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 15 proven. 55 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-08 10:11:23,190 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:23,293 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 19 treesize of output 17 [2024-11-08 10:11:23,299 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 23 treesize of output 19 [2024-11-08 10:11:23,416 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 15 proven. 55 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-08 10:11:23,416 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [266983041] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:11:23,416 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:11:23,416 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 16, 16] total 31 [2024-11-08 10:11:23,416 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [476494620] [2024-11-08 10:11:23,416 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:23,416 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2024-11-08 10:11:23,416 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:23,417 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2024-11-08 10:11:23,417 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=827, Unknown=0, NotChecked=0, Total=930 [2024-11-08 10:11:23,417 INFO L87 Difference]: Start difference. First operand 79 states and 83 transitions. Second operand has 31 states, 31 states have (on average 2.5161290322580645) internal successors, (78), 27 states have internal predecessors, (78), 9 states have call successors, (10), 1 states have call predecessors, (10), 2 states have return successors, (11), 11 states have call predecessors, (11), 9 states have call successors, (11) [2024-11-08 10:11:23,866 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:23,866 INFO L93 Difference]: Finished difference Result 91 states and 95 transitions. [2024-11-08 10:11:23,866 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-08 10:11:23,867 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 31 states have (on average 2.5161290322580645) internal successors, (78), 27 states have internal predecessors, (78), 9 states have call successors, (10), 1 states have call predecessors, (10), 2 states have return successors, (11), 11 states have call predecessors, (11), 9 states have call successors, (11) Word has length 63 [2024-11-08 10:11:23,867 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:23,867 INFO L225 Difference]: With dead ends: 91 [2024-11-08 10:11:23,867 INFO L226 Difference]: Without dead ends: 74 [2024-11-08 10:11:23,868 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 159 GetRequests, 118 SyntacticMatches, 6 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 368 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=170, Invalid=1162, Unknown=0, NotChecked=0, Total=1332 [2024-11-08 10:11:23,868 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 83 mSDsluCounter, 319 mSDsCounter, 0 mSdLazyCounter, 559 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 84 SdHoareTripleChecker+Valid, 345 SdHoareTripleChecker+Invalid, 575 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 559 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:23,868 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [84 Valid, 345 Invalid, 575 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 559 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-08 10:11:23,868 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2024-11-08 10:11:23,874 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 64. [2024-11-08 10:11:23,874 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 51 states have (on average 1.0392156862745099) internal successors, (53), 51 states have internal predecessors, (53), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 10:11:23,874 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 67 transitions. [2024-11-08 10:11:23,874 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 67 transitions. Word has length 63 [2024-11-08 10:11:23,875 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:23,875 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 67 transitions. [2024-11-08 10:11:23,875 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 31 states have (on average 2.5161290322580645) internal successors, (78), 27 states have internal predecessors, (78), 9 states have call successors, (10), 1 states have call predecessors, (10), 2 states have return successors, (11), 11 states have call predecessors, (11), 9 states have call successors, (11) [2024-11-08 10:11:23,875 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 67 transitions. [2024-11-08 10:11:23,875 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2024-11-08 10:11:23,875 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:23,876 INFO L215 NwaCegarLoop]: trace histogram [7, 7, 7, 5, 5, 5, 5, 5, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:23,888 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:24,079 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,SelfDestructingSolverStorable11 [2024-11-08 10:11:24,080 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:24,080 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:24,080 INFO L85 PathProgramCache]: Analyzing trace with hash -700161792, now seen corresponding path program 9 times [2024-11-08 10:11:24,080 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:24,080 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [407003405] [2024-11-08 10:11:24,080 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:24,080 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:24,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:24,451 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:24,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:24,455 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:24,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:24,490 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:11:24,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:24,493 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 10:11:24,494 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:24,495 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-08 10:11:24,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:24,497 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-08 10:11:24,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:24,508 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-08 10:11:24,509 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:24,511 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 15 proven. 78 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2024-11-08 10:11:24,511 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:24,511 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [407003405] [2024-11-08 10:11:24,512 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [407003405] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:24,512 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [998715823] [2024-11-08 10:11:24,512 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-08 10:11:24,512 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:24,512 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:24,514 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:24,515 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:24,597 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-11-08 10:11:24,597 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:11:24,598 INFO L255 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-08 10:11:24,603 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:24,806 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 1 [2024-11-08 10:11:24,989 INFO L349 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2024-11-08 10:11:24,990 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 16 [2024-11-08 10:11:25,182 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 28 treesize of output 10 [2024-11-08 10:11:25,204 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 33 proven. 78 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-08 10:11:25,204 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:29,320 WARN L851 $PredicateComparison]: unable to prove that (forall ((|ULTIMATE.start_main_~k~0#1| Int)) (< 5 (select (store (select |c_#memory_int#1| |c_ULTIMATE.start_main_~#a~0#1.base|) (+ (* |c_ULTIMATE.start_main_~i~0#1| 4) |c_ULTIMATE.start_main_~#a~0#1.offset|) (+ |c_ULTIMATE.start_main_~j~0#1| |ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~i~0#1|)) (+ |c_ULTIMATE.start_main_~#a~0#1.offset| 16)))) is different from false [2024-11-08 10:11:29,330 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [998715823] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:29,330 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 10:11:29,330 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 34 [2024-11-08 10:11:29,330 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [697624670] [2024-11-08 10:11:29,330 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:29,330 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2024-11-08 10:11:29,331 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:29,331 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2024-11-08 10:11:29,332 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=145, Invalid=1048, Unknown=1, NotChecked=66, Total=1260 [2024-11-08 10:11:29,332 INFO L87 Difference]: Start difference. First operand 64 states and 67 transitions. Second operand has 34 states, 34 states have (on average 2.264705882352941) internal successors, (77), 30 states have internal predecessors, (77), 11 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (13), 13 states have call predecessors, (13), 11 states have call successors, (13) [2024-11-08 10:11:29,807 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:29,807 INFO L93 Difference]: Finished difference Result 78 states and 81 transitions. [2024-11-08 10:11:29,808 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-08 10:11:29,808 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 34 states have (on average 2.264705882352941) internal successors, (77), 30 states have internal predecessors, (77), 11 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (13), 13 states have call predecessors, (13), 11 states have call successors, (13) Word has length 71 [2024-11-08 10:11:29,808 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:29,809 INFO L225 Difference]: With dead ends: 78 [2024-11-08 10:11:29,809 INFO L226 Difference]: Without dead ends: 76 [2024-11-08 10:11:29,809 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 83 SyntacticMatches, 6 SemanticMatches, 43 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 560 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=249, Invalid=1646, Unknown=1, NotChecked=84, Total=1980 [2024-11-08 10:11:29,810 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 102 mSDsluCounter, 272 mSDsCounter, 0 mSdLazyCounter, 627 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 102 SdHoareTripleChecker+Valid, 297 SdHoareTripleChecker+Invalid, 635 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 627 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:29,810 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [102 Valid, 297 Invalid, 635 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 627 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-08 10:11:29,810 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2024-11-08 10:11:29,829 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 68. [2024-11-08 10:11:29,830 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 55 states have (on average 1.0363636363636364) internal successors, (57), 55 states have internal predecessors, (57), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-08 10:11:29,830 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 71 transitions. [2024-11-08 10:11:29,831 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 71 transitions. Word has length 71 [2024-11-08 10:11:29,832 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:29,832 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 71 transitions. [2024-11-08 10:11:29,833 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 34 states have (on average 2.264705882352941) internal successors, (77), 30 states have internal predecessors, (77), 11 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (13), 13 states have call predecessors, (13), 11 states have call successors, (13) [2024-11-08 10:11:29,833 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 71 transitions. [2024-11-08 10:11:29,834 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2024-11-08 10:11:29,834 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:29,834 INFO L215 NwaCegarLoop]: trace histogram [7, 7, 7, 5, 5, 5, 5, 5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:29,847 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-08 10:11:30,034 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-08 10:11:30,035 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:30,035 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:30,035 INFO L85 PathProgramCache]: Analyzing trace with hash 1947082230, now seen corresponding path program 10 times [2024-11-08 10:11:30,036 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:30,036 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [521557013] [2024-11-08 10:11:30,036 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:30,036 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:30,051 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:30,402 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:30,403 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:30,404 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:30,404 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:30,432 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:11:30,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:30,435 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 10:11:30,436 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:30,437 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-08 10:11:30,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:30,438 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-08 10:11:30,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:30,440 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-08 10:11:30,441 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:30,447 INFO L134 CoverageAnalysis]: Checked inductivity of 161 backedges. 18 proven. 89 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2024-11-08 10:11:30,447 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:30,447 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [521557013] [2024-11-08 10:11:30,447 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [521557013] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:30,447 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1054291522] [2024-11-08 10:11:30,457 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-08 10:11:30,457 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:30,457 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:30,461 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:11:30,462 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-08 10:11:30,526 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-08 10:11:30,526 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:11:30,527 INFO L255 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 46 conjuncts are in the unsatisfiable core [2024-11-08 10:11:30,529 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:30,816 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:31,112 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 22 treesize of output 10 [2024-11-08 10:11:31,133 INFO L134 CoverageAnalysis]: Checked inductivity of 161 backedges. 18 proven. 89 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2024-11-08 10:11:31,133 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:31,260 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 19 treesize of output 17 [2024-11-08 10:11:31,262 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 23 treesize of output 19 [2024-11-08 10:11:31,378 INFO L134 CoverageAnalysis]: Checked inductivity of 161 backedges. 18 proven. 89 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2024-11-08 10:11:31,378 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1054291522] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:11:31,378 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:11:31,378 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 20, 19] total 38 [2024-11-08 10:11:31,379 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1235338450] [2024-11-08 10:11:31,379 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:31,379 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 38 states [2024-11-08 10:11:31,379 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:31,380 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2024-11-08 10:11:31,380 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=147, Invalid=1259, Unknown=0, NotChecked=0, Total=1406 [2024-11-08 10:11:31,380 INFO L87 Difference]: Start difference. First operand 68 states and 71 transitions. Second operand has 38 states, 37 states have (on average 2.4864864864864864) internal successors, (92), 34 states have internal predecessors, (92), 12 states have call successors, (13), 1 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 12 states have call successors, (13) [2024-11-08 10:11:32,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:32,125 INFO L93 Difference]: Finished difference Result 111 states and 117 transitions. [2024-11-08 10:11:32,125 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-08 10:11:32,126 INFO L78 Accepts]: Start accepts. Automaton has has 38 states, 37 states have (on average 2.4864864864864864) internal successors, (92), 34 states have internal predecessors, (92), 12 states have call successors, (13), 1 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 12 states have call successors, (13) Word has length 75 [2024-11-08 10:11:32,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:32,126 INFO L225 Difference]: With dead ends: 111 [2024-11-08 10:11:32,126 INFO L226 Difference]: Without dead ends: 109 [2024-11-08 10:11:32,127 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 189 GetRequests, 139 SyntacticMatches, 6 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 557 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=249, Invalid=1821, Unknown=0, NotChecked=0, Total=2070 [2024-11-08 10:11:32,127 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 145 mSDsluCounter, 506 mSDsCounter, 0 mSdLazyCounter, 1168 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 146 SdHoareTripleChecker+Valid, 535 SdHoareTripleChecker+Invalid, 1183 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 1168 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:32,127 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [146 Valid, 535 Invalid, 1183 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 1168 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-08 10:11:32,128 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2024-11-08 10:11:32,139 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 77. [2024-11-08 10:11:32,139 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 63 states have (on average 1.0476190476190477) internal successors, (66), 63 states have internal predecessors, (66), 8 states have call successors, (8), 5 states have call predecessors, (8), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-08 10:11:32,139 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 82 transitions. [2024-11-08 10:11:32,140 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 82 transitions. Word has length 75 [2024-11-08 10:11:32,140 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:32,141 INFO L471 AbstractCegarLoop]: Abstraction has 77 states and 82 transitions. [2024-11-08 10:11:32,141 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 38 states, 37 states have (on average 2.4864864864864864) internal successors, (92), 34 states have internal predecessors, (92), 12 states have call successors, (13), 1 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 12 states have call successors, (13) [2024-11-08 10:11:32,141 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 82 transitions. [2024-11-08 10:11:32,141 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2024-11-08 10:11:32,142 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:32,142 INFO L215 NwaCegarLoop]: trace histogram [7, 7, 7, 6, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:32,161 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-08 10:11:32,342 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-08 10:11:32,343 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:32,343 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:32,343 INFO L85 PathProgramCache]: Analyzing trace with hash 1814327276, now seen corresponding path program 11 times [2024-11-08 10:11:32,343 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:32,343 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1465504134] [2024-11-08 10:11:32,343 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:32,344 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:32,354 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:32,512 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:32,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:32,513 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:32,514 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:32,514 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:11:32,515 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:32,516 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 10:11:32,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:32,517 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-08 10:11:32,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:32,519 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-08 10:11:32,519 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:32,520 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-08 10:11:32,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:32,522 INFO L134 CoverageAnalysis]: Checked inductivity of 179 backedges. 33 proven. 62 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-08 10:11:32,522 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:32,522 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1465504134] [2024-11-08 10:11:32,522 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1465504134] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:32,522 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [825652047] [2024-11-08 10:11:32,522 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-08 10:11:32,522 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:32,522 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:32,524 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:11:32,525 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-08 10:11:32,590 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2024-11-08 10:11:32,590 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:11:32,591 INFO L255 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-08 10:11:32,592 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:32,741 INFO L134 CoverageAnalysis]: Checked inductivity of 179 backedges. 50 proven. 45 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-08 10:11:32,742 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:32,867 INFO L134 CoverageAnalysis]: Checked inductivity of 179 backedges. 50 proven. 45 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-08 10:11:32,867 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [825652047] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:11:32,867 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:11:32,867 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 15] total 23 [2024-11-08 10:11:32,869 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1913518325] [2024-11-08 10:11:32,869 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:32,869 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-08 10:11:32,869 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:32,870 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-08 10:11:32,870 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=131, Invalid=375, Unknown=0, NotChecked=0, Total=506 [2024-11-08 10:11:32,870 INFO L87 Difference]: Start difference. First operand 77 states and 82 transitions. Second operand has 23 states, 23 states have (on average 3.391304347826087) internal successors, (78), 23 states have internal predecessors, (78), 7 states have call successors, (8), 1 states have call predecessors, (8), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2024-11-08 10:11:32,975 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:32,975 INFO L93 Difference]: Finished difference Result 117 states and 123 transitions. [2024-11-08 10:11:32,975 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-08 10:11:32,975 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 3.391304347826087) internal successors, (78), 23 states have internal predecessors, (78), 7 states have call successors, (8), 1 states have call predecessors, (8), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) Word has length 79 [2024-11-08 10:11:32,976 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:32,976 INFO L225 Difference]: With dead ends: 117 [2024-11-08 10:11:32,976 INFO L226 Difference]: Without dead ends: 89 [2024-11-08 10:11:32,977 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 190 GetRequests, 153 SyntacticMatches, 11 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 333 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=201, Invalid=555, Unknown=0, NotChecked=0, Total=756 [2024-11-08 10:11:32,977 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 54 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 114 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:32,977 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 128 Invalid, 114 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-08 10:11:32,978 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2024-11-08 10:11:32,984 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 72. [2024-11-08 10:11:32,984 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 58 states have (on average 1.0344827586206897) internal successors, (60), 58 states have internal predecessors, (60), 8 states have call successors, (8), 5 states have call predecessors, (8), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-08 10:11:32,984 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 76 transitions. [2024-11-08 10:11:32,984 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 76 transitions. Word has length 79 [2024-11-08 10:11:32,984 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:32,984 INFO L471 AbstractCegarLoop]: Abstraction has 72 states and 76 transitions. [2024-11-08 10:11:32,985 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 3.391304347826087) internal successors, (78), 23 states have internal predecessors, (78), 7 states have call successors, (8), 1 states have call predecessors, (8), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2024-11-08 10:11:32,985 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 76 transitions. [2024-11-08 10:11:32,985 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2024-11-08 10:11:32,985 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:32,985 INFO L215 NwaCegarLoop]: trace histogram [8, 8, 8, 6, 6, 6, 6, 6, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:32,999 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-08 10:11:33,186 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-08 10:11:33,187 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:33,187 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:33,187 INFO L85 PathProgramCache]: Analyzing trace with hash -502341447, now seen corresponding path program 12 times [2024-11-08 10:11:33,187 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:33,187 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1535618147] [2024-11-08 10:11:33,187 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:33,187 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:33,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:33,694 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:33,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:33,696 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:33,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:33,725 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:11:33,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:33,728 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 10:11:33,729 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:33,731 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-08 10:11:33,732 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:33,733 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-08 10:11:33,734 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:33,735 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-08 10:11:33,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:33,747 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 55 [2024-11-08 10:11:33,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:33,750 INFO L134 CoverageAnalysis]: Checked inductivity of 210 backedges. 18 proven. 116 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2024-11-08 10:11:33,750 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:33,750 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1535618147] [2024-11-08 10:11:33,751 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1535618147] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:33,751 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [517814920] [2024-11-08 10:11:33,751 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-08 10:11:33,751 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:33,751 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:33,756 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:11:33,761 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-08 10:11:33,855 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2024-11-08 10:11:33,855 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-08 10:11:33,857 INFO L255 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 39 conjuncts are in the unsatisfiable core [2024-11-08 10:11:33,858 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:33,983 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 1 [2024-11-08 10:11:34,155 INFO L349 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2024-11-08 10:11:34,156 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 16 [2024-11-08 10:11:34,377 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 28 treesize of output 10 [2024-11-08 10:11:34,396 INFO L134 CoverageAnalysis]: Checked inductivity of 210 backedges. 40 proven. 116 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2024-11-08 10:11:34,396 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:50,669 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [517814920] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:50,669 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 10:11:50,669 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 32 [2024-11-08 10:11:50,669 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1101270085] [2024-11-08 10:11:50,670 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:50,670 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2024-11-08 10:11:50,670 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:50,671 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2024-11-08 10:11:50,671 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=132, Invalid=986, Unknown=4, NotChecked=0, Total=1122 [2024-11-08 10:11:50,671 INFO L87 Difference]: Start difference. First operand 72 states and 76 transitions. Second operand has 32 states, 32 states have (on average 2.40625) internal successors, (77), 29 states have internal predecessors, (77), 8 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (10), 10 states have call predecessors, (10), 8 states have call successors, (10) [2024-11-08 10:11:51,250 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 10:11:51,250 INFO L93 Difference]: Finished difference Result 90 states and 93 transitions. [2024-11-08 10:11:51,251 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-08 10:11:51,251 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 32 states have (on average 2.40625) internal successors, (77), 29 states have internal predecessors, (77), 8 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (10), 10 states have call predecessors, (10), 8 states have call successors, (10) Word has length 83 [2024-11-08 10:11:51,251 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 10:11:51,252 INFO L225 Difference]: With dead ends: 90 [2024-11-08 10:11:51,252 INFO L226 Difference]: Without dead ends: 88 [2024-11-08 10:11:51,252 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 104 SyntacticMatches, 7 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 633 ImplicationChecksByTransitivity, 16.9s TimeCoverageRelationStatistics Valid=242, Invalid=1646, Unknown=4, NotChecked=0, Total=1892 [2024-11-08 10:11:51,253 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 79 mSDsluCounter, 340 mSDsCounter, 0 mSdLazyCounter, 784 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 368 SdHoareTripleChecker+Invalid, 801 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 784 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-08 10:11:51,253 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 368 Invalid, 801 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 784 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-08 10:11:51,253 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2024-11-08 10:11:51,260 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 80. [2024-11-08 10:11:51,260 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 65 states have (on average 1.0307692307692307) internal successors, (67), 65 states have internal predecessors, (67), 8 states have call successors, (8), 6 states have call predecessors, (8), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-08 10:11:51,261 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 83 transitions. [2024-11-08 10:11:51,261 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 83 transitions. Word has length 83 [2024-11-08 10:11:51,261 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 10:11:51,261 INFO L471 AbstractCegarLoop]: Abstraction has 80 states and 83 transitions. [2024-11-08 10:11:51,261 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 32 states have (on average 2.40625) internal successors, (77), 29 states have internal predecessors, (77), 8 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (10), 10 states have call predecessors, (10), 8 states have call successors, (10) [2024-11-08 10:11:51,261 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 83 transitions. [2024-11-08 10:11:51,262 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-08 10:11:51,262 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 10:11:51,262 INFO L215 NwaCegarLoop]: trace histogram [8, 8, 8, 6, 6, 6, 6, 6, 6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 10:11:51,276 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2024-11-08 10:11:51,462 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:51,463 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 10:11:51,463 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 10:11:51,463 INFO L85 PathProgramCache]: Analyzing trace with hash -1833952977, now seen corresponding path program 13 times [2024-11-08 10:11:51,464 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 10:11:51,464 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1094708245] [2024-11-08 10:11:51,464 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 10:11:51,464 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 10:11:51,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:51,950 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 10:11:51,951 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:51,951 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-08 10:11:51,952 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:51,982 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-08 10:11:51,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:51,985 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-08 10:11:51,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:51,987 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-08 10:11:51,988 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:51,989 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-08 10:11:51,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:51,990 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-08 10:11:51,991 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:51,992 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 55 [2024-11-08 10:11:51,993 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:52,000 INFO L134 CoverageAnalysis]: Checked inductivity of 228 backedges. 21 proven. 131 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2024-11-08 10:11:52,000 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 10:11:52,000 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1094708245] [2024-11-08 10:11:52,001 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1094708245] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 10:11:52,001 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [508956097] [2024-11-08 10:11:52,001 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-08 10:11:52,001 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 10:11:52,001 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 10:11:52,002 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-08 10:11:52,003 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-08 10:11:52,074 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 10:11:52,076 INFO L255 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 50 conjuncts are in the unsatisfiable core [2024-11-08 10:11:52,078 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 10:11:52,434 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:52,796 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 22 treesize of output 10 [2024-11-08 10:11:52,831 INFO L134 CoverageAnalysis]: Checked inductivity of 228 backedges. 21 proven. 131 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2024-11-08 10:11:52,831 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 10:11:52,998 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 19 treesize of output 17 [2024-11-08 10:11:53,000 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 23 treesize of output 19 [2024-11-08 10:11:53,334 INFO L134 CoverageAnalysis]: Checked inductivity of 228 backedges. 21 proven. 131 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2024-11-08 10:11:53,334 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [508956097] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 10:11:53,334 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 10:11:53,334 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 22, 21] total 50 [2024-11-08 10:11:53,335 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [34191293] [2024-11-08 10:11:53,335 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 10:11:53,335 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2024-11-08 10:11:53,335 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 10:11:53,336 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2024-11-08 10:11:53,336 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=218, Invalid=2232, Unknown=0, NotChecked=0, Total=2450 [2024-11-08 10:11:53,337 INFO L87 Difference]: Start difference. First operand 80 states and 83 transitions. Second operand has 50 states, 49 states have (on average 2.5510204081632653) internal successors, (125), 44 states have internal predecessors, (125), 20 states have call successors, (21), 1 states have call predecessors, (21), 2 states have return successors, (22), 22 states have call predecessors, (22), 20 states have call successors, (22)