./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound20.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 61a67961 Calling Ultimate with: /root/.sdkman/candidates/java/current/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 /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound20.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 9e9911e775b3214ba13077b05d83e9364947724e9afa3bb89f51b07ee325bd90 --- Real Ultimate output --- This is Ultimate 0.2.5-wip.fs.cvc5-61a6796-m [2024-10-14 02:18:29,647 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-14 02:18:29,709 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-14 02:18:29,714 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-14 02:18:29,714 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-14 02:18:29,745 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-14 02:18:29,745 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-14 02:18:29,745 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-14 02:18:29,746 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-14 02:18:29,746 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-14 02:18:29,746 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-14 02:18:29,747 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-14 02:18:29,747 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-14 02:18:29,747 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-14 02:18:29,748 INFO L153 SettingsManager]: * Use SBE=true [2024-10-14 02:18:29,748 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-14 02:18:29,748 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-14 02:18:29,748 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-14 02:18:29,749 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-14 02:18:29,749 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-14 02:18:29,749 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-14 02:18:29,749 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-14 02:18:29,750 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-14 02:18:29,750 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-14 02:18:29,750 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-14 02:18:29,750 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-14 02:18:29,750 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-14 02:18:29,751 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-14 02:18:29,751 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-14 02:18:29,751 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-14 02:18:29,751 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-14 02:18:29,751 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-14 02:18:29,752 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-14 02:18:29,752 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-14 02:18:29,752 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-14 02:18:29,752 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-14 02:18:29,752 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-14 02:18:29,752 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-14 02:18:29,752 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-14 02:18:29,752 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-14 02:18:29,753 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-14 02:18:29,753 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-14 02:18:29,753 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 -> 9e9911e775b3214ba13077b05d83e9364947724e9afa3bb89f51b07ee325bd90 [2024-10-14 02:18:29,965 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-14 02:18:29,990 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-14 02:18:29,992 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-14 02:18:29,993 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-14 02:18:29,994 INFO L274 PluginConnector]: CDTParser initialized [2024-10-14 02:18:29,995 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound20.c [2024-10-14 02:18:31,182 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-14 02:18:31,352 INFO L384 CDTParser]: Found 1 translation units. [2024-10-14 02:18:31,354 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound20.c [2024-10-14 02:18:31,360 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b42b88485/9b62e6bf73b14565bc66a833b4f2e653/FLAGa395ed104 [2024-10-14 02:18:31,774 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b42b88485/9b62e6bf73b14565bc66a833b4f2e653 [2024-10-14 02:18:31,776 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-14 02:18:31,777 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-14 02:18:31,778 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-14 02:18:31,778 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-14 02:18:31,783 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-14 02:18:31,783 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:31,784 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5abeb812 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31, skipping insertion in model container [2024-10-14 02:18:31,784 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:31,802 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-14 02:18:31,915 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound20.c[490,503] [2024-10-14 02:18:31,931 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-14 02:18:31,937 INFO L200 MainTranslator]: Completed pre-run [2024-10-14 02:18:31,950 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound20.c[490,503] [2024-10-14 02:18:31,960 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-14 02:18:31,974 INFO L204 MainTranslator]: Completed translation [2024-10-14 02:18:31,975 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31 WrapperNode [2024-10-14 02:18:31,975 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-14 02:18:31,976 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-14 02:18:31,977 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-14 02:18:31,977 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-14 02:18:31,982 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:31,990 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:32,016 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 86 [2024-10-14 02:18:32,017 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-14 02:18:32,017 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-14 02:18:32,017 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-14 02:18:32,018 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-14 02:18:32,026 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:32,026 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:32,032 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:32,048 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-10-14 02:18:32,049 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:32,049 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:32,051 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:32,056 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:32,059 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:32,064 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:32,065 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-14 02:18:32,066 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-14 02:18:32,066 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-14 02:18:32,066 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-14 02:18:32,067 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31" (1/1) ... [2024-10-14 02:18:32,073 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-14 02:18:32,082 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:18:32,094 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-10-14 02:18:32,096 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-10-14 02:18:32,130 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-14 02:18:32,130 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-10-14 02:18:32,132 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-10-14 02:18:32,132 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-14 02:18:32,133 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-14 02:18:32,133 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-14 02:18:32,133 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-14 02:18:32,134 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-14 02:18:32,184 INFO L238 CfgBuilder]: Building ICFG [2024-10-14 02:18:32,185 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-14 02:18:32,309 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-10-14 02:18:32,309 INFO L287 CfgBuilder]: Performing block encoding [2024-10-14 02:18:32,331 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-14 02:18:32,332 INFO L314 CfgBuilder]: Removed 2 assume(true) statements. [2024-10-14 02:18:32,332 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.10 02:18:32 BoogieIcfgContainer [2024-10-14 02:18:32,332 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-14 02:18:32,334 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-14 02:18:32,334 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-14 02:18:32,337 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-14 02:18:32,337 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.10 02:18:31" (1/3) ... [2024-10-14 02:18:32,338 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7efb7daf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.10 02:18:32, skipping insertion in model container [2024-10-14 02:18:32,338 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.10 02:18:31" (2/3) ... [2024-10-14 02:18:32,338 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7efb7daf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.10 02:18:32, skipping insertion in model container [2024-10-14 02:18:32,338 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.10 02:18:32" (3/3) ... [2024-10-14 02:18:32,339 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound20.c [2024-10-14 02:18:32,351 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-14 02:18:32,351 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-14 02:18:32,397 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-14 02:18:32,404 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;@475a3700, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-14 02:18:32,404 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-14 02:18:32,409 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 19 states have internal predecessors, (26), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-10-14 02:18:32,415 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-10-14 02:18:32,416 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:32,416 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:32,417 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:32,421 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:32,422 INFO L85 PathProgramCache]: Analyzing trace with hash -689848145, now seen corresponding path program 1 times [2024-10-14 02:18:32,428 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:32,429 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1218510002] [2024-10-14 02:18:32,429 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:32,429 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:32,513 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:32,574 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-14 02:18:32,580 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:32,587 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-14 02:18:32,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:32,594 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-14 02:18:32,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:32,602 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-14 02:18:32,604 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:32,610 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-14 02:18:32,611 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:18:32,611 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1218510002] [2024-10-14 02:18:32,612 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1218510002] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-14 02:18:32,612 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-14 02:18:32,612 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-14 02:18:32,617 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1743159330] [2024-10-14 02:18:32,618 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-14 02:18:32,621 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-14 02:18:32,621 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:18:32,639 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-14 02:18:32,639 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-14 02:18:32,641 INFO L87 Difference]: Start difference. First operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 19 states have internal predecessors, (26), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-14 02:18:32,671 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:18:32,671 INFO L93 Difference]: Finished difference Result 60 states and 99 transitions. [2024-10-14 02:18:32,672 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-14 02:18:32,673 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 27 [2024-10-14 02:18:32,674 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:18:32,678 INFO L225 Difference]: With dead ends: 60 [2024-10-14 02:18:32,679 INFO L226 Difference]: Without dead ends: 29 [2024-10-14 02:18:32,682 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-14 02:18:32,685 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-14 02:18:32,687 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 40 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-14 02:18:32,699 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2024-10-14 02:18:32,717 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2024-10-14 02:18:32,718 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 16 states have (on average 1.3125) internal successors, (21), 18 states have internal predecessors, (21), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-10-14 02:18:32,719 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 40 transitions. [2024-10-14 02:18:32,721 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 40 transitions. Word has length 27 [2024-10-14 02:18:32,722 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:18:32,722 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 40 transitions. [2024-10-14 02:18:32,722 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-14 02:18:32,722 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 40 transitions. [2024-10-14 02:18:32,723 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-10-14 02:18:32,724 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:32,724 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:32,725 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-14 02:18:32,725 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:32,726 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:32,726 INFO L85 PathProgramCache]: Analyzing trace with hash -1989097615, now seen corresponding path program 1 times [2024-10-14 02:18:32,726 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:32,727 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1660612284] [2024-10-14 02:18:32,727 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:32,727 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:32,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:32,880 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-14 02:18:32,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:32,889 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-14 02:18:32,891 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:32,898 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-14 02:18:32,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:32,904 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-14 02:18:32,905 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:32,912 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-14 02:18:32,912 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:18:32,912 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1660612284] [2024-10-14 02:18:32,913 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1660612284] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-14 02:18:32,913 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-14 02:18:32,913 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-10-14 02:18:32,913 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [623459222] [2024-10-14 02:18:32,913 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-14 02:18:32,914 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-14 02:18:32,916 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:18:32,917 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-14 02:18:32,917 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-14 02:18:32,918 INFO L87 Difference]: Start difference. First operand 29 states and 40 transitions. Second operand has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-14 02:18:32,944 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:18:32,944 INFO L93 Difference]: Finished difference Result 39 states and 51 transitions. [2024-10-14 02:18:32,945 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-14 02:18:32,945 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2024-10-14 02:18:32,946 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:18:32,947 INFO L225 Difference]: With dead ends: 39 [2024-10-14 02:18:32,948 INFO L226 Difference]: Without dead ends: 31 [2024-10-14 02:18:32,948 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-14 02:18:32,950 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 7 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-14 02:18:32,950 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 97 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-14 02:18:32,952 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-10-14 02:18:32,957 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2024-10-14 02:18:32,957 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 18 states have (on average 1.2777777777777777) internal successors, (23), 19 states have internal predecessors, (23), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-10-14 02:18:32,958 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 42 transitions. [2024-10-14 02:18:32,958 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 42 transitions. Word has length 28 [2024-10-14 02:18:32,960 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:18:32,960 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 42 transitions. [2024-10-14 02:18:32,960 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-14 02:18:32,960 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 42 transitions. [2024-10-14 02:18:32,961 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-10-14 02:18:32,961 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:32,961 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:32,961 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-14 02:18:32,961 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:32,962 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:32,962 INFO L85 PathProgramCache]: Analyzing trace with hash -1539070609, now seen corresponding path program 1 times [2024-10-14 02:18:32,962 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:32,962 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1440337531] [2024-10-14 02:18:32,962 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:32,962 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:32,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:33,103 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-14 02:18:33,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:33,108 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-14 02:18:33,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:33,143 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-14 02:18:33,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:33,149 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-14 02:18:33,151 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:33,157 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-14 02:18:33,157 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:18:33,158 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1440337531] [2024-10-14 02:18:33,158 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1440337531] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:18:33,158 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1800279907] [2024-10-14 02:18:33,158 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:33,158 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:33,158 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:18:33,160 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-10-14 02:18:33,162 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-10-14 02:18:33,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:33,220 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-14 02:18:33,227 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:18:33,379 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-14 02:18:33,380 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-14 02:18:33,380 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1800279907] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-14 02:18:33,380 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-14 02:18:33,380 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2024-10-14 02:18:33,380 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [876607319] [2024-10-14 02:18:33,380 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-14 02:18:33,381 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-14 02:18:33,381 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:18:33,381 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-14 02:18:33,381 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2024-10-14 02:18:33,382 INFO L87 Difference]: Start difference. First operand 31 states and 42 transitions. Second operand has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-14 02:18:33,475 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:18:33,475 INFO L93 Difference]: Finished difference Result 48 states and 66 transitions. [2024-10-14 02:18:33,476 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-14 02:18:33,476 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2024-10-14 02:18:33,477 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:18:33,478 INFO L225 Difference]: With dead ends: 48 [2024-10-14 02:18:33,478 INFO L226 Difference]: Without dead ends: 46 [2024-10-14 02:18:33,479 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=89, Unknown=0, NotChecked=0, Total=110 [2024-10-14 02:18:33,480 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 9 mSDsluCounter, 108 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-14 02:18:33,480 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 138 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-14 02:18:33,481 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-10-14 02:18:33,493 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 44. [2024-10-14 02:18:33,493 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 25 states have (on average 1.32) internal successors, (33), 27 states have internal predecessors, (33), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-10-14 02:18:33,494 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 62 transitions. [2024-10-14 02:18:33,496 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 62 transitions. Word has length 29 [2024-10-14 02:18:33,496 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:18:33,497 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 62 transitions. [2024-10-14 02:18:33,497 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-14 02:18:33,497 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 62 transitions. [2024-10-14 02:18:33,498 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-10-14 02:18:33,498 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:33,498 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:33,521 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-14 02:18:33,698 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-10-14 02:18:33,699 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:33,700 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:33,700 INFO L85 PathProgramCache]: Analyzing trace with hash -1634889762, now seen corresponding path program 1 times [2024-10-14 02:18:33,700 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:33,700 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1043220605] [2024-10-14 02:18:33,700 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:33,700 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:33,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:18:33,723 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [158436596] [2024-10-14 02:18:33,724 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:33,724 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:33,724 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:18:33,731 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-10-14 02:18:33,735 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-10-14 02:18:33,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:33,780 INFO L255 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-14 02:18:33,781 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:18:33,827 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-14 02:18:33,828 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-14 02:18:33,829 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:18:33,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1043220605] [2024-10-14 02:18:33,830 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:18:33,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [158436596] [2024-10-14 02:18:33,831 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [158436596] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-14 02:18:33,831 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-14 02:18:33,831 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-14 02:18:33,831 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [92767703] [2024-10-14 02:18:33,831 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-14 02:18:33,834 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-14 02:18:33,834 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:18:33,834 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-14 02:18:33,835 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-14 02:18:33,835 INFO L87 Difference]: Start difference. First operand 44 states and 62 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-14 02:18:33,891 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:18:33,891 INFO L93 Difference]: Finished difference Result 65 states and 94 transitions. [2024-10-14 02:18:33,892 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-14 02:18:33,892 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 31 [2024-10-14 02:18:33,892 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:18:33,895 INFO L225 Difference]: With dead ends: 65 [2024-10-14 02:18:33,896 INFO L226 Difference]: Without dead ends: 63 [2024-10-14 02:18:33,897 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-14 02:18:33,898 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 5 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-14 02:18:33,899 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 132 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-14 02:18:33,900 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-10-14 02:18:33,912 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 54. [2024-10-14 02:18:33,913 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 32 states have (on average 1.3125) internal successors, (42), 36 states have internal predecessors, (42), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 13 states have call predecessors, (16), 16 states have call successors, (16) [2024-10-14 02:18:33,915 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 75 transitions. [2024-10-14 02:18:33,917 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 75 transitions. Word has length 31 [2024-10-14 02:18:33,917 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:18:33,917 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 75 transitions. [2024-10-14 02:18:33,917 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-14 02:18:33,918 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 75 transitions. [2024-10-14 02:18:33,919 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-10-14 02:18:33,919 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:33,919 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:33,933 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-10-14 02:18:34,123 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-10-14 02:18:34,124 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:34,124 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:34,124 INFO L85 PathProgramCache]: Analyzing trace with hash -254153455, now seen corresponding path program 1 times [2024-10-14 02:18:34,124 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:34,124 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1870906558] [2024-10-14 02:18:34,125 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:34,125 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:34,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:34,186 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-14 02:18:34,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:34,188 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-14 02:18:34,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:34,209 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-14 02:18:34,210 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:34,212 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-14 02:18:34,213 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:34,215 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-10-14 02:18:34,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:34,217 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-10-14 02:18:34,217 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:18:34,217 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1870906558] [2024-10-14 02:18:34,217 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1870906558] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:18:34,217 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [519581480] [2024-10-14 02:18:34,217 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:34,217 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:34,218 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:18:34,220 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-10-14 02:18:34,221 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-10-14 02:18:34,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:34,261 INFO L255 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-14 02:18:34,263 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:18:34,341 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-14 02:18:34,341 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-14 02:18:34,341 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [519581480] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-14 02:18:34,345 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-14 02:18:34,345 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2024-10-14 02:18:34,345 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1508542090] [2024-10-14 02:18:34,345 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-14 02:18:34,346 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-14 02:18:34,346 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:18:34,346 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-14 02:18:34,346 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2024-10-14 02:18:34,346 INFO L87 Difference]: Start difference. First operand 54 states and 75 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-14 02:18:34,407 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:18:34,407 INFO L93 Difference]: Finished difference Result 62 states and 82 transitions. [2024-10-14 02:18:34,408 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-14 02:18:34,409 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2024-10-14 02:18:34,409 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:18:34,409 INFO L225 Difference]: With dead ends: 62 [2024-10-14 02:18:34,409 INFO L226 Difference]: Without dead ends: 58 [2024-10-14 02:18:34,410 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2024-10-14 02:18:34,410 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 9 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-14 02:18:34,410 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 135 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-14 02:18:34,411 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2024-10-14 02:18:34,419 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2024-10-14 02:18:34,421 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 35 states have (on average 1.2571428571428571) internal successors, (44), 38 states have internal predecessors, (44), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-10-14 02:18:34,422 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 75 transitions. [2024-10-14 02:18:34,423 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 75 transitions. Word has length 34 [2024-10-14 02:18:34,424 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:18:34,424 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 75 transitions. [2024-10-14 02:18:34,424 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-14 02:18:34,424 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 75 transitions. [2024-10-14 02:18:34,425 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-10-14 02:18:34,425 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:34,425 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:34,445 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-10-14 02:18:34,625 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-10-14 02:18:34,626 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:34,626 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:34,626 INFO L85 PathProgramCache]: Analyzing trace with hash 753217482, now seen corresponding path program 1 times [2024-10-14 02:18:34,626 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:34,626 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [919524767] [2024-10-14 02:18:34,626 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:34,626 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:34,638 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:34,689 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-14 02:18:34,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:34,692 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-14 02:18:34,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:34,694 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-14 02:18:34,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:34,696 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-14 02:18:34,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:34,699 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-14 02:18:34,699 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:18:34,699 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [919524767] [2024-10-14 02:18:34,699 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [919524767] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-14 02:18:34,699 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-14 02:18:34,699 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-10-14 02:18:34,699 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1931922171] [2024-10-14 02:18:34,699 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-14 02:18:34,700 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-14 02:18:34,700 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:18:34,700 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-14 02:18:34,700 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-14 02:18:34,700 INFO L87 Difference]: Start difference. First operand 57 states and 75 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-14 02:18:34,747 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:18:34,747 INFO L93 Difference]: Finished difference Result 83 states and 110 transitions. [2024-10-14 02:18:34,748 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-14 02:18:34,748 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 34 [2024-10-14 02:18:34,748 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:18:34,749 INFO L225 Difference]: With dead ends: 83 [2024-10-14 02:18:34,749 INFO L226 Difference]: Without dead ends: 57 [2024-10-14 02:18:34,749 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-14 02:18:34,750 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 10 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-14 02:18:34,750 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 120 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-14 02:18:34,751 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2024-10-14 02:18:34,759 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2024-10-14 02:18:34,762 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 35 states have (on average 1.2285714285714286) internal successors, (43), 38 states have internal predecessors, (43), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-10-14 02:18:34,764 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2024-10-14 02:18:34,764 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 74 transitions. Word has length 34 [2024-10-14 02:18:34,764 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:18:34,764 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 74 transitions. [2024-10-14 02:18:34,764 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-14 02:18:34,764 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 74 transitions. [2024-10-14 02:18:34,765 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-10-14 02:18:34,765 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:34,765 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:34,766 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-10-14 02:18:34,766 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:34,766 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:34,766 INFO L85 PathProgramCache]: Analyzing trace with hash 439925314, now seen corresponding path program 1 times [2024-10-14 02:18:34,766 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:34,767 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1348101474] [2024-10-14 02:18:34,767 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:34,767 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:34,782 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:18:34,783 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [622840853] [2024-10-14 02:18:34,783 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:34,784 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:34,784 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:18:34,785 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-10-14 02:18:34,786 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-10-14 02:18:34,837 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:34,838 INFO L255 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-14 02:18:34,839 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:18:34,975 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-10-14 02:18:34,976 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-14 02:18:34,977 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:18:34,977 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1348101474] [2024-10-14 02:18:34,977 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:18:34,977 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [622840853] [2024-10-14 02:18:34,977 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [622840853] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-14 02:18:34,977 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-14 02:18:34,977 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-14 02:18:34,977 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [13587828] [2024-10-14 02:18:34,978 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-14 02:18:34,978 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-14 02:18:34,978 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:18:34,979 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-14 02:18:34,979 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-14 02:18:34,979 INFO L87 Difference]: Start difference. First operand 57 states and 74 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-14 02:18:35,039 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:18:35,039 INFO L93 Difference]: Finished difference Result 64 states and 80 transitions. [2024-10-14 02:18:35,039 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-14 02:18:35,040 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 46 [2024-10-14 02:18:35,040 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:18:35,041 INFO L225 Difference]: With dead ends: 64 [2024-10-14 02:18:35,041 INFO L226 Difference]: Without dead ends: 62 [2024-10-14 02:18:35,041 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-14 02:18:35,041 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-14 02:18:35,042 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 123 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-14 02:18:35,042 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2024-10-14 02:18:35,053 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 61. [2024-10-14 02:18:35,053 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 38 states have (on average 1.2105263157894737) internal successors, (46), 41 states have internal predecessors, (46), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-10-14 02:18:35,055 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 77 transitions. [2024-10-14 02:18:35,055 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 77 transitions. Word has length 46 [2024-10-14 02:18:35,055 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:18:35,055 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 77 transitions. [2024-10-14 02:18:35,055 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-14 02:18:35,055 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 77 transitions. [2024-10-14 02:18:35,056 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2024-10-14 02:18:35,056 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:35,056 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:35,071 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-14 02:18:35,257 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:35,257 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:35,257 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:35,257 INFO L85 PathProgramCache]: Analyzing trace with hash -982723610, now seen corresponding path program 1 times [2024-10-14 02:18:35,258 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:35,258 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1630779659] [2024-10-14 02:18:35,258 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:35,258 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:35,279 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:18:35,281 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1419287431] [2024-10-14 02:18:35,281 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:35,281 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:35,281 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:18:35,286 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-10-14 02:18:35,287 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-10-14 02:18:35,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:35,344 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-10-14 02:18:35,345 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:18:35,413 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-14 02:18:35,413 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:18:35,487 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2024-10-14 02:18:35,488 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:18:35,488 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1630779659] [2024-10-14 02:18:35,488 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:18:35,488 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1419287431] [2024-10-14 02:18:35,488 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1419287431] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-14 02:18:35,488 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-14 02:18:35,488 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-10-14 02:18:35,488 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [856516526] [2024-10-14 02:18:35,489 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-14 02:18:35,489 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-14 02:18:35,489 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:18:35,489 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-14 02:18:35,489 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-10-14 02:18:35,490 INFO L87 Difference]: Start difference. First operand 61 states and 77 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-10-14 02:18:35,529 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:18:35,530 INFO L93 Difference]: Finished difference Result 67 states and 82 transitions. [2024-10-14 02:18:35,530 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-14 02:18:35,530 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 54 [2024-10-14 02:18:35,530 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:18:35,531 INFO L225 Difference]: With dead ends: 67 [2024-10-14 02:18:35,531 INFO L226 Difference]: Without dead ends: 65 [2024-10-14 02:18:35,531 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 99 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-10-14 02:18:35,531 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 5 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-14 02:18:35,532 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 117 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-14 02:18:35,532 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2024-10-14 02:18:35,537 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 57. [2024-10-14 02:18:35,538 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 36 states have (on average 1.1944444444444444) internal successors, (43), 37 states have internal predecessors, (43), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-10-14 02:18:35,538 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 70 transitions. [2024-10-14 02:18:35,538 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 70 transitions. Word has length 54 [2024-10-14 02:18:35,539 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:18:35,539 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 70 transitions. [2024-10-14 02:18:35,539 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-10-14 02:18:35,539 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 70 transitions. [2024-10-14 02:18:35,539 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2024-10-14 02:18:35,539 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:35,539 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:35,552 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-10-14 02:18:35,743 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:35,743 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:35,743 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:35,743 INFO L85 PathProgramCache]: Analyzing trace with hash -1428774585, now seen corresponding path program 1 times [2024-10-14 02:18:35,743 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:35,744 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1419806636] [2024-10-14 02:18:35,744 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:35,744 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:35,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:35,823 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-14 02:18:35,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:35,827 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-14 02:18:35,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:35,829 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-14 02:18:35,830 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:35,832 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-14 02:18:35,833 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:35,834 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-14 02:18:35,836 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:35,837 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-14 02:18:35,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:35,840 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-14 02:18:35,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:35,847 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-14 02:18:35,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:35,850 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-14 02:18:35,850 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:18:35,850 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1419806636] [2024-10-14 02:18:35,850 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1419806636] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:18:35,850 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2002750526] [2024-10-14 02:18:35,850 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:35,850 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:35,851 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:18:35,852 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-10-14 02:18:35,853 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-10-14 02:18:35,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:35,898 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-14 02:18:35,900 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:18:35,964 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-14 02:18:35,965 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:18:36,029 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-14 02:18:36,030 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2002750526] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:18:36,030 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-14 02:18:36,031 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 12 [2024-10-14 02:18:36,031 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2145704976] [2024-10-14 02:18:36,031 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-14 02:18:36,031 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-10-14 02:18:36,031 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:18:36,032 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-14 02:18:36,032 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2024-10-14 02:18:36,032 INFO L87 Difference]: Start difference. First operand 57 states and 70 transitions. Second operand has 12 states, 12 states have (on average 3.4166666666666665) internal successors, (41), 12 states have internal predecessors, (41), 6 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 5 states have call predecessors, (24), 5 states have call successors, (24) [2024-10-14 02:18:36,191 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:18:36,192 INFO L93 Difference]: Finished difference Result 210 states and 249 transitions. [2024-10-14 02:18:36,192 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-10-14 02:18:36,192 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.4166666666666665) internal successors, (41), 12 states have internal predecessors, (41), 6 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 5 states have call predecessors, (24), 5 states have call successors, (24) Word has length 55 [2024-10-14 02:18:36,193 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:18:36,195 INFO L225 Difference]: With dead ends: 210 [2024-10-14 02:18:36,195 INFO L226 Difference]: Without dead ends: 202 [2024-10-14 02:18:36,195 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 120 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=72, Invalid=138, Unknown=0, NotChecked=0, Total=210 [2024-10-14 02:18:36,195 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 80 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 80 SdHoareTripleChecker+Valid, 192 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-14 02:18:36,196 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [80 Valid, 192 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-14 02:18:36,196 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 202 states. [2024-10-14 02:18:36,216 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 202 to 194. [2024-10-14 02:18:36,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 194 states, 124 states have (on average 1.1935483870967742) internal successors, (148), 128 states have internal predecessors, (148), 44 states have call successors, (44), 25 states have call predecessors, (44), 25 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2024-10-14 02:18:36,218 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 194 states to 194 states and 232 transitions. [2024-10-14 02:18:36,218 INFO L78 Accepts]: Start accepts. Automaton has 194 states and 232 transitions. Word has length 55 [2024-10-14 02:18:36,218 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:18:36,218 INFO L471 AbstractCegarLoop]: Abstraction has 194 states and 232 transitions. [2024-10-14 02:18:36,218 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.4166666666666665) internal successors, (41), 12 states have internal predecessors, (41), 6 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 5 states have call predecessors, (24), 5 states have call successors, (24) [2024-10-14 02:18:36,218 INFO L276 IsEmpty]: Start isEmpty. Operand 194 states and 232 transitions. [2024-10-14 02:18:36,219 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-10-14 02:18:36,219 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:36,219 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:36,231 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-10-14 02:18:36,419 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:36,420 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:36,420 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:36,420 INFO L85 PathProgramCache]: Analyzing trace with hash -1348925863, now seen corresponding path program 1 times [2024-10-14 02:18:36,420 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:36,420 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [16923233] [2024-10-14 02:18:36,420 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:36,421 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:36,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:36,498 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-14 02:18:36,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:36,515 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-14 02:18:36,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:36,517 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-14 02:18:36,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:36,520 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-14 02:18:36,520 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:36,524 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-14 02:18:36,526 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:36,527 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-14 02:18:36,528 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:36,529 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-14 02:18:36,534 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:36,535 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-14 02:18:36,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:36,540 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-14 02:18:36,540 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:18:36,540 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [16923233] [2024-10-14 02:18:36,541 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [16923233] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:18:36,541 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [197613674] [2024-10-14 02:18:36,541 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:36,541 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:36,541 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:18:36,543 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-10-14 02:18:36,544 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-10-14 02:18:36,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:36,590 INFO L255 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-14 02:18:36,591 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:18:36,632 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-14 02:18:36,632 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:18:36,699 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-14 02:18:36,700 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [197613674] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:18:36,700 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-14 02:18:36,700 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2024-10-14 02:18:36,700 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [810836973] [2024-10-14 02:18:36,700 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-14 02:18:36,700 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-10-14 02:18:36,700 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:18:36,700 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-10-14 02:18:36,701 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-10-14 02:18:36,701 INFO L87 Difference]: Start difference. First operand 194 states and 232 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-10-14 02:18:36,839 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:18:36,839 INFO L93 Difference]: Finished difference Result 278 states and 363 transitions. [2024-10-14 02:18:36,839 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-14 02:18:36,839 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 56 [2024-10-14 02:18:36,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:18:36,841 INFO L225 Difference]: With dead ends: 278 [2024-10-14 02:18:36,841 INFO L226 Difference]: Without dead ends: 258 [2024-10-14 02:18:36,841 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 122 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=134, Unknown=0, NotChecked=0, Total=182 [2024-10-14 02:18:36,842 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 60 mSDsluCounter, 195 mSDsCounter, 0 mSdLazyCounter, 73 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 241 SdHoareTripleChecker+Invalid, 111 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 73 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-14 02:18:36,842 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 241 Invalid, 111 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 73 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-14 02:18:36,844 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 258 states. [2024-10-14 02:18:36,873 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 258 to 234. [2024-10-14 02:18:36,874 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 234 states, 151 states have (on average 1.2251655629139073) internal successors, (185), 154 states have internal predecessors, (185), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2024-10-14 02:18:36,875 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 234 states to 234 states and 298 transitions. [2024-10-14 02:18:36,875 INFO L78 Accepts]: Start accepts. Automaton has 234 states and 298 transitions. Word has length 56 [2024-10-14 02:18:36,875 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:18:36,875 INFO L471 AbstractCegarLoop]: Abstraction has 234 states and 298 transitions. [2024-10-14 02:18:36,875 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-10-14 02:18:36,875 INFO L276 IsEmpty]: Start isEmpty. Operand 234 states and 298 transitions. [2024-10-14 02:18:36,876 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2024-10-14 02:18:36,876 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:36,876 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:36,889 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-10-14 02:18:37,076 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:37,077 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:37,077 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:37,077 INFO L85 PathProgramCache]: Analyzing trace with hash -848672706, now seen corresponding path program 1 times [2024-10-14 02:18:37,078 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:37,078 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1760851687] [2024-10-14 02:18:37,078 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:37,078 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:37,085 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:37,138 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-14 02:18:37,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:37,141 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-14 02:18:37,142 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:37,143 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-14 02:18:37,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:37,145 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-14 02:18:37,145 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:37,146 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-14 02:18:37,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:37,148 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-14 02:18:37,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:37,150 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-14 02:18:37,150 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:37,152 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-14 02:18:37,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:37,154 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-14 02:18:37,154 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:18:37,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1760851687] [2024-10-14 02:18:37,154 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1760851687] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:18:37,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [970512881] [2024-10-14 02:18:37,154 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:37,155 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:37,155 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:18:37,156 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-10-14 02:18:37,157 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-10-14 02:18:37,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:37,207 INFO L255 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-14 02:18:37,209 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:18:37,257 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-14 02:18:37,257 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:18:37,318 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-14 02:18:37,318 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [970512881] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:18:37,319 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-14 02:18:37,319 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5, 6] total 12 [2024-10-14 02:18:37,319 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [904822612] [2024-10-14 02:18:37,319 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-14 02:18:37,319 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-10-14 02:18:37,319 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:18:37,320 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-14 02:18:37,320 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2024-10-14 02:18:37,320 INFO L87 Difference]: Start difference. First operand 234 states and 298 transitions. Second operand has 12 states, 12 states have (on average 3.5833333333333335) internal successors, (43), 12 states have internal predecessors, (43), 6 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 5 states have call predecessors, (24), 5 states have call successors, (24) [2024-10-14 02:18:37,460 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:18:37,460 INFO L93 Difference]: Finished difference Result 343 states and 447 transitions. [2024-10-14 02:18:37,461 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-14 02:18:37,461 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.5833333333333335) internal successors, (43), 12 states have internal predecessors, (43), 6 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 5 states have call predecessors, (24), 5 states have call successors, (24) Word has length 58 [2024-10-14 02:18:37,461 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:18:37,462 INFO L225 Difference]: With dead ends: 343 [2024-10-14 02:18:37,462 INFO L226 Difference]: Without dead ends: 247 [2024-10-14 02:18:37,463 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 140 GetRequests, 126 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2024-10-14 02:18:37,463 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 90 mSDsluCounter, 149 mSDsCounter, 0 mSdLazyCounter, 100 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 90 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 124 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 100 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-14 02:18:37,463 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [90 Valid, 184 Invalid, 124 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 100 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-14 02:18:37,464 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 247 states. [2024-10-14 02:18:37,481 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 247 to 243. [2024-10-14 02:18:37,481 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 243 states, 160 states have (on average 1.175) internal successors, (188), 163 states have internal predecessors, (188), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2024-10-14 02:18:37,482 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 301 transitions. [2024-10-14 02:18:37,482 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 301 transitions. Word has length 58 [2024-10-14 02:18:37,483 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:18:37,483 INFO L471 AbstractCegarLoop]: Abstraction has 243 states and 301 transitions. [2024-10-14 02:18:37,483 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.5833333333333335) internal successors, (43), 12 states have internal predecessors, (43), 6 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 5 states have call predecessors, (24), 5 states have call successors, (24) [2024-10-14 02:18:37,483 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 301 transitions. [2024-10-14 02:18:37,483 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2024-10-14 02:18:37,483 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:37,483 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:37,496 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-10-14 02:18:37,684 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-10-14 02:18:37,684 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:37,685 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:37,685 INFO L85 PathProgramCache]: Analyzing trace with hash -421956392, now seen corresponding path program 1 times [2024-10-14 02:18:37,685 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:37,685 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1442258464] [2024-10-14 02:18:37,685 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:37,685 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:37,701 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:18:37,701 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1775830578] [2024-10-14 02:18:37,702 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:37,702 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:37,702 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:18:37,704 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-10-14 02:18:37,705 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-10-14 02:18:37,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:18:37,753 INFO L255 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-10-14 02:18:37,754 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:18:37,965 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 19 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-10-14 02:18:37,965 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:18:38,061 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2024-10-14 02:18:38,061 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:18:38,061 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1442258464] [2024-10-14 02:18:38,061 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:18:38,061 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1775830578] [2024-10-14 02:18:38,061 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1775830578] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:18:38,061 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-14 02:18:38,061 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6] total 12 [2024-10-14 02:18:38,061 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1030581673] [2024-10-14 02:18:38,061 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-14 02:18:38,062 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-10-14 02:18:38,062 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:18:38,062 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-14 02:18:38,062 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2024-10-14 02:18:38,062 INFO L87 Difference]: Start difference. First operand 243 states and 301 transitions. Second operand has 12 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 9 states have internal predecessors, (39), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2024-10-14 02:18:38,216 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:18:38,216 INFO L93 Difference]: Finished difference Result 282 states and 354 transitions. [2024-10-14 02:18:38,217 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-14 02:18:38,217 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 9 states have internal predecessors, (39), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) Word has length 63 [2024-10-14 02:18:38,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:18:38,218 INFO L225 Difference]: With dead ends: 282 [2024-10-14 02:18:38,218 INFO L226 Difference]: Without dead ends: 277 [2024-10-14 02:18:38,219 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 112 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=143, Unknown=0, NotChecked=0, Total=182 [2024-10-14 02:18:38,219 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 31 mSDsluCounter, 263 mSDsCounter, 0 mSdLazyCounter, 159 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 307 SdHoareTripleChecker+Invalid, 171 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 159 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-14 02:18:38,219 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 307 Invalid, 171 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 159 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-14 02:18:38,220 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 277 states. [2024-10-14 02:18:38,244 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 277 to 275. [2024-10-14 02:18:38,244 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 275 states, 182 states have (on average 1.1868131868131868) internal successors, (216), 186 states have internal predecessors, (216), 65 states have call successors, (65), 27 states have call predecessors, (65), 27 states have return successors, (61), 61 states have call predecessors, (61), 61 states have call successors, (61) [2024-10-14 02:18:38,245 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 275 states to 275 states and 342 transitions. [2024-10-14 02:18:38,245 INFO L78 Accepts]: Start accepts. Automaton has 275 states and 342 transitions. Word has length 63 [2024-10-14 02:18:38,246 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:18:38,246 INFO L471 AbstractCegarLoop]: Abstraction has 275 states and 342 transitions. [2024-10-14 02:18:38,246 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 3.5454545454545454) internal successors, (39), 9 states have internal predecessors, (39), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2024-10-14 02:18:38,246 INFO L276 IsEmpty]: Start isEmpty. Operand 275 states and 342 transitions. [2024-10-14 02:18:38,246 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-10-14 02:18:38,246 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:38,246 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:38,259 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-10-14 02:18:38,447 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:38,447 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:38,447 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:38,447 INFO L85 PathProgramCache]: Analyzing trace with hash -245166072, now seen corresponding path program 2 times [2024-10-14 02:18:38,447 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:38,447 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [284806554] [2024-10-14 02:18:38,447 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:38,447 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:38,457 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:18:38,458 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [319786593] [2024-10-14 02:18:38,458 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-14 02:18:38,458 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:38,458 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:18:38,459 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-10-14 02:18:38,460 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-10-14 02:18:38,508 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-14 02:18:38,508 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-14 02:18:38,509 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-10-14 02:18:38,511 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:18:38,829 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 17 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2024-10-14 02:18:38,829 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:18:39,100 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-10-14 02:18:39,101 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:18:39,101 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [284806554] [2024-10-14 02:18:39,101 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:18:39,101 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [319786593] [2024-10-14 02:18:39,101 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [319786593] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:18:39,101 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-14 02:18:39,101 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 15 [2024-10-14 02:18:39,102 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1748100863] [2024-10-14 02:18:39,102 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-14 02:18:39,102 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-10-14 02:18:39,102 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:18:39,102 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-10-14 02:18:39,103 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=172, Unknown=0, NotChecked=0, Total=210 [2024-10-14 02:18:39,103 INFO L87 Difference]: Start difference. First operand 275 states and 342 transitions. Second operand has 15 states, 15 states have (on average 2.6) internal successors, (39), 13 states have internal predecessors, (39), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2024-10-14 02:18:40,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:18:40,346 INFO L93 Difference]: Finished difference Result 439 states and 594 transitions. [2024-10-14 02:18:40,346 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-10-14 02:18:40,346 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.6) internal successors, (39), 13 states have internal predecessors, (39), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) Word has length 68 [2024-10-14 02:18:40,346 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:18:40,348 INFO L225 Difference]: With dead ends: 439 [2024-10-14 02:18:40,348 INFO L226 Difference]: Without dead ends: 437 [2024-10-14 02:18:40,349 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 119 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 161 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=198, Invalid=672, Unknown=0, NotChecked=0, Total=870 [2024-10-14 02:18:40,349 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 115 mSDsluCounter, 345 mSDsCounter, 0 mSdLazyCounter, 272 mSolverCounterSat, 83 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 120 SdHoareTripleChecker+Valid, 388 SdHoareTripleChecker+Invalid, 355 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 83 IncrementalHoareTripleChecker+Valid, 272 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-10-14 02:18:40,349 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [120 Valid, 388 Invalid, 355 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [83 Valid, 272 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-10-14 02:18:40,350 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 437 states. [2024-10-14 02:18:40,410 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 437 to 392. [2024-10-14 02:18:40,411 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 392 states, 257 states have (on average 1.245136186770428) internal successors, (320), 261 states have internal predecessors, (320), 101 states have call successors, (101), 33 states have call predecessors, (101), 33 states have return successors, (97), 97 states have call predecessors, (97), 97 states have call successors, (97) [2024-10-14 02:18:40,412 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 392 states to 392 states and 518 transitions. [2024-10-14 02:18:40,412 INFO L78 Accepts]: Start accepts. Automaton has 392 states and 518 transitions. Word has length 68 [2024-10-14 02:18:40,413 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:18:40,413 INFO L471 AbstractCegarLoop]: Abstraction has 392 states and 518 transitions. [2024-10-14 02:18:40,413 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.6) internal successors, (39), 13 states have internal predecessors, (39), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 8 states have call predecessors, (20), 8 states have call successors, (20) [2024-10-14 02:18:40,413 INFO L276 IsEmpty]: Start isEmpty. Operand 392 states and 518 transitions. [2024-10-14 02:18:40,416 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-10-14 02:18:40,416 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:18:40,416 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:18:40,430 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-10-14 02:18:40,616 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-10-14 02:18:40,617 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:18:40,617 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:18:40,617 INFO L85 PathProgramCache]: Analyzing trace with hash -441972072, now seen corresponding path program 3 times [2024-10-14 02:18:40,617 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:18:40,617 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [142581812] [2024-10-14 02:18:40,617 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:18:40,617 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:18:40,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:18:40,627 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1465907878] [2024-10-14 02:18:40,628 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-14 02:18:40,628 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:18:40,628 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:18:40,629 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-10-14 02:18:40,630 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-10-14 02:18:40,675 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-10-14 02:18:40,675 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-14 02:18:40,676 INFO L255 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 59 conjuncts are in the unsatisfiable core [2024-10-14 02:18:40,678 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:18:41,454 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 42 proven. 23 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-10-14 02:18:41,454 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:18:55,690 WARN L286 SmtUtils]: Spent 12.29s on a formula simplification that was a NOOP. DAG size: 45 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-10-14 02:19:28,711 WARN L286 SmtUtils]: Spent 25.70s on a formula simplification that was a NOOP. DAG size: 16 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-10-14 02:19:31,114 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:19:31,114 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [142581812] [2024-10-14 02:19:31,114 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:19:31,114 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1465907878] [2024-10-14 02:19:31,114 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1465907878] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:19:31,114 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-14 02:19:31,114 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-10-14 02:19:31,114 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1921937589] [2024-10-14 02:19:31,114 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-14 02:19:31,115 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-14 02:19:31,115 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:19:31,116 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-14 02:19:31,117 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=536, Unknown=0, NotChecked=0, Total=650 [2024-10-14 02:19:31,117 INFO L87 Difference]: Start difference. First operand 392 states and 518 transitions. Second operand has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-10-14 02:19:31,911 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:19:31,912 INFO L93 Difference]: Finished difference Result 415 states and 538 transitions. [2024-10-14 02:19:31,914 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-10-14 02:19:31,914 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) Word has length 73 [2024-10-14 02:19:31,915 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:19:31,917 INFO L225 Difference]: With dead ends: 415 [2024-10-14 02:19:31,917 INFO L226 Difference]: Without dead ends: 411 [2024-10-14 02:19:31,918 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 100 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 14.9s TimeCoverageRelationStatistics Valid=167, Invalid=703, Unknown=0, NotChecked=0, Total=870 [2024-10-14 02:19:31,918 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 39 mSDsluCounter, 232 mSDsCounter, 0 mSdLazyCounter, 335 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 263 SdHoareTripleChecker+Invalid, 350 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 335 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-10-14 02:19:31,919 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 263 Invalid, 350 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 335 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-10-14 02:19:31,919 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 411 states. [2024-10-14 02:19:31,962 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 411 to 410. [2024-10-14 02:19:31,963 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 410 states, 271 states have (on average 1.2287822878228782) internal successors, (333), 274 states have internal predecessors, (333), 101 states have call successors, (101), 38 states have call predecessors, (101), 37 states have return successors, (97), 97 states have call predecessors, (97), 97 states have call successors, (97) [2024-10-14 02:19:31,964 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 410 states to 410 states and 531 transitions. [2024-10-14 02:19:31,965 INFO L78 Accepts]: Start accepts. Automaton has 410 states and 531 transitions. Word has length 73 [2024-10-14 02:19:31,965 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:19:31,965 INFO L471 AbstractCegarLoop]: Abstraction has 410 states and 531 transitions. [2024-10-14 02:19:31,965 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 13 states have internal predecessors, (29), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-10-14 02:19:31,965 INFO L276 IsEmpty]: Start isEmpty. Operand 410 states and 531 transitions. [2024-10-14 02:19:31,966 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2024-10-14 02:19:31,966 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:19:31,966 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:19:31,979 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-10-14 02:19:32,170 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-10-14 02:19:32,171 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:19:32,171 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:19:32,171 INFO L85 PathProgramCache]: Analyzing trace with hash 2054740817, now seen corresponding path program 1 times [2024-10-14 02:19:32,171 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:19:32,171 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [800977752] [2024-10-14 02:19:32,171 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:19:32,171 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:19:32,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:19:32,189 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1000250548] [2024-10-14 02:19:32,190 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:19:32,190 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:19:32,190 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:19:32,194 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-10-14 02:19:32,195 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-10-14 02:19:32,250 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:32,251 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-10-14 02:19:32,252 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:19:32,632 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 19 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2024-10-14 02:19:32,633 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:19:33,331 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2024-10-14 02:19:33,331 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:19:33,331 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [800977752] [2024-10-14 02:19:33,331 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:19:33,331 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1000250548] [2024-10-14 02:19:33,331 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1000250548] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:19:33,331 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-14 02:19:33,331 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-10-14 02:19:33,331 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1517748125] [2024-10-14 02:19:33,331 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-14 02:19:33,332 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-10-14 02:19:33,332 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:19:33,332 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-14 02:19:33,332 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2024-10-14 02:19:33,333 INFO L87 Difference]: Start difference. First operand 410 states and 531 transitions. Second operand has 21 states, 19 states have (on average 2.263157894736842) internal successors, (43), 18 states have internal predecessors, (43), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-10-14 02:19:36,322 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:19:36,323 INFO L93 Difference]: Finished difference Result 607 states and 850 transitions. [2024-10-14 02:19:36,324 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-10-14 02:19:36,325 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.263157894736842) internal successors, (43), 18 states have internal predecessors, (43), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 79 [2024-10-14 02:19:36,325 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:19:36,333 INFO L225 Difference]: With dead ends: 607 [2024-10-14 02:19:36,333 INFO L226 Difference]: Without dead ends: 596 [2024-10-14 02:19:36,336 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 137 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 267 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=296, Invalid=1264, Unknown=0, NotChecked=0, Total=1560 [2024-10-14 02:19:36,336 INFO L432 NwaCegarLoop]: 59 mSDtfsCounter, 129 mSDsluCounter, 609 mSDsCounter, 0 mSdLazyCounter, 549 mSolverCounterSat, 124 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 668 SdHoareTripleChecker+Invalid, 673 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 124 IncrementalHoareTripleChecker+Valid, 549 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2024-10-14 02:19:36,336 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 668 Invalid, 673 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [124 Valid, 549 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2024-10-14 02:19:36,337 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 596 states. [2024-10-14 02:19:36,451 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 596 to 552. [2024-10-14 02:19:36,452 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 552 states, 356 states have (on average 1.297752808988764) internal successors, (462), 359 states have internal predecessors, (462), 156 states have call successors, (156), 39 states have call predecessors, (156), 39 states have return successors, (154), 153 states have call predecessors, (154), 154 states have call successors, (154) [2024-10-14 02:19:36,454 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 552 states to 552 states and 772 transitions. [2024-10-14 02:19:36,455 INFO L78 Accepts]: Start accepts. Automaton has 552 states and 772 transitions. Word has length 79 [2024-10-14 02:19:36,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:19:36,455 INFO L471 AbstractCegarLoop]: Abstraction has 552 states and 772 transitions. [2024-10-14 02:19:36,455 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.263157894736842) internal successors, (43), 18 states have internal predecessors, (43), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-10-14 02:19:36,456 INFO L276 IsEmpty]: Start isEmpty. Operand 552 states and 772 transitions. [2024-10-14 02:19:36,456 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-10-14 02:19:36,456 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:19:36,456 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:19:36,469 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-10-14 02:19:36,657 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-10-14 02:19:36,657 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:19:36,657 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:19:36,657 INFO L85 PathProgramCache]: Analyzing trace with hash 653663042, now seen corresponding path program 4 times [2024-10-14 02:19:36,657 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:19:36,657 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [709427746] [2024-10-14 02:19:36,657 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:19:36,658 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:19:36,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,709 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-14 02:19:36,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,711 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-14 02:19:36,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,713 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-14 02:19:36,714 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,715 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-14 02:19:36,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,717 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-14 02:19:36,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,718 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-14 02:19:36,718 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,719 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-14 02:19:36,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,720 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-14 02:19:36,721 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,723 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-10-14 02:19:36,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,725 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-10-14 02:19:36,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,727 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-10-14 02:19:36,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,729 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 69 [2024-10-14 02:19:36,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,733 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 81 [2024-10-14 02:19:36,734 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:36,735 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 43 proven. 0 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-10-14 02:19:36,735 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:19:36,735 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [709427746] [2024-10-14 02:19:36,735 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [709427746] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-14 02:19:36,735 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-14 02:19:36,735 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-14 02:19:36,735 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [691797438] [2024-10-14 02:19:36,736 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-14 02:19:36,736 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-14 02:19:36,736 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:19:36,736 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-14 02:19:36,736 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-14 02:19:36,736 INFO L87 Difference]: Start difference. First operand 552 states and 772 transitions. Second operand has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2024-10-14 02:19:36,883 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:19:36,883 INFO L93 Difference]: Finished difference Result 889 states and 1328 transitions. [2024-10-14 02:19:36,883 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-14 02:19:36,884 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) Word has length 90 [2024-10-14 02:19:36,884 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:19:36,887 INFO L225 Difference]: With dead ends: 889 [2024-10-14 02:19:36,887 INFO L226 Difference]: Without dead ends: 625 [2024-10-14 02:19:36,888 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2024-10-14 02:19:36,888 INFO L432 NwaCegarLoop]: 53 mSDtfsCounter, 12 mSDsluCounter, 128 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 181 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-14 02:19:36,888 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 181 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-14 02:19:36,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 625 states. [2024-10-14 02:19:36,983 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 625 to 530. [2024-10-14 02:19:36,983 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 530 states, 338 states have (on average 1.2781065088757397) internal successors, (432), 341 states have internal predecessors, (432), 152 states have call successors, (152), 39 states have call predecessors, (152), 39 states have return successors, (150), 149 states have call predecessors, (150), 150 states have call successors, (150) [2024-10-14 02:19:36,985 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 530 states to 530 states and 734 transitions. [2024-10-14 02:19:36,985 INFO L78 Accepts]: Start accepts. Automaton has 530 states and 734 transitions. Word has length 90 [2024-10-14 02:19:36,986 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:19:36,986 INFO L471 AbstractCegarLoop]: Abstraction has 530 states and 734 transitions. [2024-10-14 02:19:36,986 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 3 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2024-10-14 02:19:36,986 INFO L276 IsEmpty]: Start isEmpty. Operand 530 states and 734 transitions. [2024-10-14 02:19:36,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2024-10-14 02:19:36,986 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:19:36,986 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:19:36,986 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15 [2024-10-14 02:19:36,987 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:19:36,987 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:19:36,987 INFO L85 PathProgramCache]: Analyzing trace with hash -1858222944, now seen corresponding path program 1 times [2024-10-14 02:19:36,987 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:19:36,987 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1858203888] [2024-10-14 02:19:36,987 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:19:36,987 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:19:36,999 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:19:37,000 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1330616780] [2024-10-14 02:19:37,000 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:19:37,000 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:19:37,000 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:19:37,002 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-10-14 02:19:37,002 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-10-14 02:19:37,057 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:37,058 INFO L255 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 38 conjuncts are in the unsatisfiable core [2024-10-14 02:19:37,060 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:19:37,976 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 51 proven. 32 refuted. 0 times theorem prover too weak. 205 trivial. 0 not checked. [2024-10-14 02:19:37,976 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:19:38,167 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:19:38,168 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1858203888] [2024-10-14 02:19:38,168 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:19:38,168 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1330616780] [2024-10-14 02:19:38,168 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1330616780] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:19:38,168 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-14 02:19:38,168 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-10-14 02:19:38,168 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1672852322] [2024-10-14 02:19:38,168 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-14 02:19:38,169 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-14 02:19:38,169 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:19:38,169 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-14 02:19:38,169 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2024-10-14 02:19:38,170 INFO L87 Difference]: Start difference. First operand 530 states and 734 transitions. Second operand has 16 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2024-10-14 02:19:39,005 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:19:39,005 INFO L93 Difference]: Finished difference Result 539 states and 742 transitions. [2024-10-14 02:19:39,006 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-10-14 02:19:39,006 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) Word has length 96 [2024-10-14 02:19:39,006 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:19:39,009 INFO L225 Difference]: With dead ends: 539 [2024-10-14 02:19:39,009 INFO L226 Difference]: Without dead ends: 537 [2024-10-14 02:19:39,010 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 83 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=84, Invalid=422, Unknown=0, NotChecked=0, Total=506 [2024-10-14 02:19:39,011 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 37 mSDsluCounter, 421 mSDsCounter, 0 mSdLazyCounter, 528 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 465 SdHoareTripleChecker+Invalid, 538 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 528 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-10-14 02:19:39,011 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 465 Invalid, 538 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 528 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-10-14 02:19:39,012 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 537 states. [2024-10-14 02:19:39,113 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 537 to 534. [2024-10-14 02:19:39,114 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 534 states, 341 states have (on average 1.2727272727272727) internal successors, (434), 344 states have internal predecessors, (434), 152 states have call successors, (152), 40 states have call predecessors, (152), 40 states have return successors, (150), 149 states have call predecessors, (150), 150 states have call successors, (150) [2024-10-14 02:19:39,116 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 534 states to 534 states and 736 transitions. [2024-10-14 02:19:39,116 INFO L78 Accepts]: Start accepts. Automaton has 534 states and 736 transitions. Word has length 96 [2024-10-14 02:19:39,117 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:19:39,117 INFO L471 AbstractCegarLoop]: Abstraction has 534 states and 736 transitions. [2024-10-14 02:19:39,117 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2024-10-14 02:19:39,118 INFO L276 IsEmpty]: Start isEmpty. Operand 534 states and 736 transitions. [2024-10-14 02:19:39,118 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2024-10-14 02:19:39,119 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:19:39,119 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:19:39,133 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-10-14 02:19:39,323 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,SelfDestructingSolverStorable16 [2024-10-14 02:19:39,324 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:19:39,324 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:19:39,324 INFO L85 PathProgramCache]: Analyzing trace with hash 973829189, now seen corresponding path program 1 times [2024-10-14 02:19:39,324 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:19:39,324 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1092913291] [2024-10-14 02:19:39,324 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:19:39,324 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:19:39,333 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,407 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-14 02:19:39,408 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,409 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-14 02:19:39,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,410 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-14 02:19:39,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,411 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-14 02:19:39,412 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,412 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-14 02:19:39,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,413 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-14 02:19:39,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,415 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-14 02:19:39,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,418 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-14 02:19:39,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,420 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-10-14 02:19:39,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,421 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-10-14 02:19:39,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,423 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-10-14 02:19:39,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,426 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 69 [2024-10-14 02:19:39,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,428 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 77 [2024-10-14 02:19:39,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,434 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 82 [2024-10-14 02:19:39,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,436 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 87 [2024-10-14 02:19:39,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,439 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 92 [2024-10-14 02:19:39,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,442 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 102 [2024-10-14 02:19:39,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,445 INFO L134 CoverageAnalysis]: Checked inductivity of 393 backedges. 46 proven. 11 refuted. 0 times theorem prover too weak. 336 trivial. 0 not checked. [2024-10-14 02:19:39,445 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:19:39,445 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1092913291] [2024-10-14 02:19:39,445 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1092913291] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:19:39,445 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2105386676] [2024-10-14 02:19:39,445 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:19:39,456 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:19:39,456 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:19:39,457 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-10-14 02:19:39,459 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-10-14 02:19:39,515 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:39,516 INFO L255 TraceCheckSpWp]: Trace formula consists of 282 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-14 02:19:39,518 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:19:39,543 INFO L134 CoverageAnalysis]: Checked inductivity of 393 backedges. 92 proven. 11 refuted. 0 times theorem prover too weak. 290 trivial. 0 not checked. [2024-10-14 02:19:39,544 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:19:39,622 INFO L134 CoverageAnalysis]: Checked inductivity of 393 backedges. 46 proven. 11 refuted. 0 times theorem prover too weak. 336 trivial. 0 not checked. [2024-10-14 02:19:39,622 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2105386676] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:19:39,622 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-14 02:19:39,623 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 7 [2024-10-14 02:19:39,623 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1973232024] [2024-10-14 02:19:39,623 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-14 02:19:39,623 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-10-14 02:19:39,623 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:19:39,623 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-10-14 02:19:39,623 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-10-14 02:19:39,624 INFO L87 Difference]: Start difference. First operand 534 states and 736 transitions. Second operand has 7 states, 7 states have (on average 4.714285714285714) internal successors, (33), 7 states have internal predecessors, (33), 4 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-10-14 02:19:39,909 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:19:39,909 INFO L93 Difference]: Finished difference Result 730 states and 1052 transitions. [2024-10-14 02:19:39,909 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-14 02:19:39,910 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 4.714285714285714) internal successors, (33), 7 states have internal predecessors, (33), 4 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) Word has length 111 [2024-10-14 02:19:39,910 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:19:39,913 INFO L225 Difference]: With dead ends: 730 [2024-10-14 02:19:39,913 INFO L226 Difference]: Without dead ends: 717 [2024-10-14 02:19:39,913 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 275 GetRequests, 255 SyntacticMatches, 6 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=68, Invalid=172, Unknown=0, NotChecked=0, Total=240 [2024-10-14 02:19:39,914 INFO L432 NwaCegarLoop]: 80 mSDtfsCounter, 31 mSDsluCounter, 308 mSDsCounter, 0 mSdLazyCounter, 136 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 388 SdHoareTripleChecker+Invalid, 150 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 136 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-14 02:19:39,914 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 388 Invalid, 150 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 136 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-14 02:19:39,914 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 717 states. [2024-10-14 02:19:40,026 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 717 to 578. [2024-10-14 02:19:40,027 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 578 states, 377 states have (on average 1.2785145888594165) internal successors, (482), 380 states have internal predecessors, (482), 160 states have call successors, (160), 40 states have call predecessors, (160), 40 states have return successors, (158), 157 states have call predecessors, (158), 158 states have call successors, (158) [2024-10-14 02:19:40,029 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 578 states to 578 states and 800 transitions. [2024-10-14 02:19:40,030 INFO L78 Accepts]: Start accepts. Automaton has 578 states and 800 transitions. Word has length 111 [2024-10-14 02:19:40,031 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:19:40,031 INFO L471 AbstractCegarLoop]: Abstraction has 578 states and 800 transitions. [2024-10-14 02:19:40,031 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 4.714285714285714) internal successors, (33), 7 states have internal predecessors, (33), 4 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-10-14 02:19:40,031 INFO L276 IsEmpty]: Start isEmpty. Operand 578 states and 800 transitions. [2024-10-14 02:19:40,032 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2024-10-14 02:19:40,033 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:19:40,034 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:19:40,048 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-10-14 02:19:40,234 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable17,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:19:40,234 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:19:40,235 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:19:40,235 INFO L85 PathProgramCache]: Analyzing trace with hash 1981200126, now seen corresponding path program 1 times [2024-10-14 02:19:40,235 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:19:40,235 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1676619311] [2024-10-14 02:19:40,236 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:19:40,236 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:19:40,250 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,391 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-14 02:19:40,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,394 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-14 02:19:40,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,395 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-14 02:19:40,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,397 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-14 02:19:40,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,398 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-14 02:19:40,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,400 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-14 02:19:40,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,402 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-14 02:19:40,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,403 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-14 02:19:40,404 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,405 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-10-14 02:19:40,406 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,407 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-10-14 02:19:40,408 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,409 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-10-14 02:19:40,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,410 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 69 [2024-10-14 02:19:40,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,412 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 77 [2024-10-14 02:19:40,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,414 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 82 [2024-10-14 02:19:40,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,416 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 87 [2024-10-14 02:19:40,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,417 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 92 [2024-10-14 02:19:40,418 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,419 INFO L134 CoverageAnalysis]: Checked inductivity of 357 backedges. 32 proven. 37 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-10-14 02:19:40,419 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:19:40,420 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1676619311] [2024-10-14 02:19:40,420 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1676619311] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:19:40,420 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1785741243] [2024-10-14 02:19:40,420 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:19:40,420 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:19:40,420 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:19:40,424 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-10-14 02:19:40,425 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-10-14 02:19:40,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-14 02:19:40,481 INFO L255 TraceCheckSpWp]: Trace formula consists of 298 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-10-14 02:19:40,482 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:19:40,574 INFO L134 CoverageAnalysis]: Checked inductivity of 357 backedges. 32 proven. 229 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2024-10-14 02:19:40,574 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:19:40,728 INFO L134 CoverageAnalysis]: Checked inductivity of 357 backedges. 32 proven. 37 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-10-14 02:19:40,729 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1785741243] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:19:40,729 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-14 02:19:40,729 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9, 10] total 20 [2024-10-14 02:19:40,729 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2122497151] [2024-10-14 02:19:40,729 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-14 02:19:40,729 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-10-14 02:19:40,729 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:19:40,730 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-10-14 02:19:40,730 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=156, Invalid=224, Unknown=0, NotChecked=0, Total=380 [2024-10-14 02:19:40,730 INFO L87 Difference]: Start difference. First operand 578 states and 800 transitions. Second operand has 20 states, 20 states have (on average 3.8) internal successors, (76), 20 states have internal predecessors, (76), 10 states have call successors, (49), 6 states have call predecessors, (49), 5 states have return successors, (48), 9 states have call predecessors, (48), 9 states have call successors, (48) [2024-10-14 02:19:41,500 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:19:41,500 INFO L93 Difference]: Finished difference Result 1897 states and 2637 transitions. [2024-10-14 02:19:41,501 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2024-10-14 02:19:41,501 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 3.8) internal successors, (76), 20 states have internal predecessors, (76), 10 states have call successors, (49), 6 states have call predecessors, (49), 5 states have return successors, (48), 9 states have call predecessors, (48), 9 states have call successors, (48) Word has length 111 [2024-10-14 02:19:41,501 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:19:41,507 INFO L225 Difference]: With dead ends: 1897 [2024-10-14 02:19:41,507 INFO L226 Difference]: Without dead ends: 1588 [2024-10-14 02:19:41,508 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 274 GetRequests, 244 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 139 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=342, Invalid=650, Unknown=0, NotChecked=0, Total=992 [2024-10-14 02:19:41,509 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 253 mSDsluCounter, 262 mSDsCounter, 0 mSdLazyCounter, 217 mSolverCounterSat, 62 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 253 SdHoareTripleChecker+Valid, 301 SdHoareTripleChecker+Invalid, 279 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 217 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-14 02:19:41,509 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [253 Valid, 301 Invalid, 279 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 217 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-14 02:19:41,510 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1588 states. [2024-10-14 02:19:41,775 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1588 to 1514. [2024-10-14 02:19:41,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1514 states, 948 states have (on average 1.2056962025316456) internal successors, (1143), 965 states have internal predecessors, (1143), 429 states have call successors, (429), 136 states have call predecessors, (429), 136 states have return successors, (413), 412 states have call predecessors, (413), 413 states have call successors, (413) [2024-10-14 02:19:41,781 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1514 states to 1514 states and 1985 transitions. [2024-10-14 02:19:41,782 INFO L78 Accepts]: Start accepts. Automaton has 1514 states and 1985 transitions. Word has length 111 [2024-10-14 02:19:41,782 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:19:41,782 INFO L471 AbstractCegarLoop]: Abstraction has 1514 states and 1985 transitions. [2024-10-14 02:19:41,783 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 3.8) internal successors, (76), 20 states have internal predecessors, (76), 10 states have call successors, (49), 6 states have call predecessors, (49), 5 states have return successors, (48), 9 states have call predecessors, (48), 9 states have call successors, (48) [2024-10-14 02:19:41,783 INFO L276 IsEmpty]: Start isEmpty. Operand 1514 states and 1985 transitions. [2024-10-14 02:19:41,783 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2024-10-14 02:19:41,783 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:19:41,784 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:19:41,796 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-10-14 02:19:41,984 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:19:41,984 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:19:41,985 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:19:41,985 INFO L85 PathProgramCache]: Analyzing trace with hash -904635594, now seen corresponding path program 2 times [2024-10-14 02:19:41,985 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:19:41,985 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1661154242] [2024-10-14 02:19:41,985 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:19:41,985 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:19:41,999 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:19:42,002 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1832855444] [2024-10-14 02:19:42,002 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-14 02:19:42,002 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:19:42,002 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:19:42,004 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-14 02:19:42,005 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-10-14 02:19:42,067 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-14 02:19:42,067 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-14 02:19:42,069 INFO L255 TraceCheckSpWp]: Trace formula consists of 290 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-10-14 02:19:42,071 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:19:42,606 INFO L134 CoverageAnalysis]: Checked inductivity of 405 backedges. 58 proven. 56 refuted. 0 times theorem prover too weak. 291 trivial. 0 not checked. [2024-10-14 02:19:42,606 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:19:42,789 INFO L134 CoverageAnalysis]: Checked inductivity of 405 backedges. 78 proven. 7 refuted. 0 times theorem prover too weak. 320 trivial. 0 not checked. [2024-10-14 02:19:42,789 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:19:42,789 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1661154242] [2024-10-14 02:19:42,789 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:19:42,789 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1832855444] [2024-10-14 02:19:42,789 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1832855444] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-14 02:19:42,789 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-14 02:19:42,789 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 8] total 23 [2024-10-14 02:19:42,789 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1997501605] [2024-10-14 02:19:42,789 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-14 02:19:42,790 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-10-14 02:19:42,790 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:19:42,790 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-10-14 02:19:42,790 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2024-10-14 02:19:42,791 INFO L87 Difference]: Start difference. First operand 1514 states and 1985 transitions. Second operand has 23 states, 22 states have (on average 2.727272727272727) internal successors, (60), 20 states have internal predecessors, (60), 9 states have call successors, (29), 3 states have call predecessors, (29), 3 states have return successors, (28), 10 states have call predecessors, (28), 9 states have call successors, (28) [2024-10-14 02:19:45,700 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:19:45,700 INFO L93 Difference]: Finished difference Result 1673 states and 2185 transitions. [2024-10-14 02:19:45,701 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-10-14 02:19:45,701 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 22 states have (on average 2.727272727272727) internal successors, (60), 20 states have internal predecessors, (60), 9 states have call successors, (29), 3 states have call predecessors, (29), 3 states have return successors, (28), 10 states have call predecessors, (28), 9 states have call successors, (28) Word has length 113 [2024-10-14 02:19:45,701 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:19:45,708 INFO L225 Difference]: With dead ends: 1673 [2024-10-14 02:19:45,708 INFO L226 Difference]: Without dead ends: 1658 [2024-10-14 02:19:45,709 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 240 GetRequests, 208 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 178 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=194, Invalid=928, Unknown=0, NotChecked=0, Total=1122 [2024-10-14 02:19:45,709 INFO L432 NwaCegarLoop]: 51 mSDtfsCounter, 80 mSDsluCounter, 500 mSDsCounter, 0 mSdLazyCounter, 584 mSolverCounterSat, 79 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 85 SdHoareTripleChecker+Valid, 551 SdHoareTripleChecker+Invalid, 663 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 79 IncrementalHoareTripleChecker+Valid, 584 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2024-10-14 02:19:45,710 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [85 Valid, 551 Invalid, 663 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [79 Valid, 584 Invalid, 0 Unknown, 0 Unchecked, 1.6s Time] [2024-10-14 02:19:45,711 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1658 states. [2024-10-14 02:19:45,997 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1658 to 1584. [2024-10-14 02:19:45,999 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1584 states, 1010 states have (on average 1.2) internal successors, (1212), 1024 states have internal predecessors, (1212), 422 states have call successors, (422), 151 states have call predecessors, (422), 151 states have return successors, (413), 408 states have call predecessors, (413), 413 states have call successors, (413) [2024-10-14 02:19:46,004 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1584 states to 1584 states and 2047 transitions. [2024-10-14 02:19:46,006 INFO L78 Accepts]: Start accepts. Automaton has 1584 states and 2047 transitions. Word has length 113 [2024-10-14 02:19:46,006 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:19:46,007 INFO L471 AbstractCegarLoop]: Abstraction has 1584 states and 2047 transitions. [2024-10-14 02:19:46,007 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 22 states have (on average 2.727272727272727) internal successors, (60), 20 states have internal predecessors, (60), 9 states have call successors, (29), 3 states have call predecessors, (29), 3 states have return successors, (28), 10 states have call predecessors, (28), 9 states have call successors, (28) [2024-10-14 02:19:46,007 INFO L276 IsEmpty]: Start isEmpty. Operand 1584 states and 2047 transitions. [2024-10-14 02:19:46,009 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2024-10-14 02:19:46,009 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:19:46,009 INFO L215 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:19:46,021 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-10-14 02:19:46,210 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:19:46,210 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:19:46,210 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:19:46,210 INFO L85 PathProgramCache]: Analyzing trace with hash 493843562, now seen corresponding path program 3 times [2024-10-14 02:19:46,210 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:19:46,210 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [286898681] [2024-10-14 02:19:46,210 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:19:46,211 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:19:46,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:19:46,235 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1060641469] [2024-10-14 02:19:46,235 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-14 02:19:46,235 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:19:46,235 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:19:46,240 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-14 02:19:46,243 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-10-14 02:19:46,304 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-10-14 02:19:46,304 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-14 02:19:46,306 INFO L255 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 67 conjuncts are in the unsatisfiable core [2024-10-14 02:19:46,308 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:19:47,105 INFO L134 CoverageAnalysis]: Checked inductivity of 462 backedges. 75 proven. 47 refuted. 0 times theorem prover too weak. 340 trivial. 0 not checked. [2024-10-14 02:19:47,105 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:19:47,774 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:19:47,774 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [286898681] [2024-10-14 02:19:47,774 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:19:47,774 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1060641469] [2024-10-14 02:19:47,774 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1060641469] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:19:47,774 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-14 02:19:47,774 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2024-10-14 02:19:47,774 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2023208096] [2024-10-14 02:19:47,774 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-14 02:19:47,775 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-10-14 02:19:47,775 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:19:47,775 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-10-14 02:19:47,775 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=425, Unknown=0, NotChecked=0, Total=506 [2024-10-14 02:19:47,775 INFO L87 Difference]: Start difference. First operand 1584 states and 2047 transitions. Second operand has 17 states, 16 states have (on average 2.4375) internal successors, (39), 15 states have internal predecessors, (39), 7 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2024-10-14 02:19:48,542 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:19:48,542 INFO L93 Difference]: Finished difference Result 1714 states and 2184 transitions. [2024-10-14 02:19:48,542 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-10-14 02:19:48,543 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 2.4375) internal successors, (39), 15 states have internal predecessors, (39), 7 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) Word has length 118 [2024-10-14 02:19:48,543 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:19:48,549 INFO L225 Difference]: With dead ends: 1714 [2024-10-14 02:19:48,549 INFO L226 Difference]: Without dead ends: 1712 [2024-10-14 02:19:48,549 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 118 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 89 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=133, Invalid=679, Unknown=0, NotChecked=0, Total=812 [2024-10-14 02:19:48,550 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 29 mSDsluCounter, 509 mSDsCounter, 0 mSdLazyCounter, 571 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 556 SdHoareTripleChecker+Invalid, 596 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 571 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-14 02:19:48,550 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 556 Invalid, 596 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 571 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-14 02:19:48,551 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1712 states. [2024-10-14 02:19:48,848 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1712 to 1697. [2024-10-14 02:19:48,850 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1697 states, 1084 states have (on average 1.1918819188191883) internal successors, (1292), 1098 states have internal predecessors, (1292), 442 states have call successors, (442), 170 states have call predecessors, (442), 170 states have return successors, (433), 428 states have call predecessors, (433), 433 states have call successors, (433) [2024-10-14 02:19:48,854 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1697 states to 1697 states and 2167 transitions. [2024-10-14 02:19:48,856 INFO L78 Accepts]: Start accepts. Automaton has 1697 states and 2167 transitions. Word has length 118 [2024-10-14 02:19:48,856 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:19:48,857 INFO L471 AbstractCegarLoop]: Abstraction has 1697 states and 2167 transitions. [2024-10-14 02:19:48,857 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 2.4375) internal successors, (39), 15 states have internal predecessors, (39), 7 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2024-10-14 02:19:48,857 INFO L276 IsEmpty]: Start isEmpty. Operand 1697 states and 2167 transitions. [2024-10-14 02:19:48,858 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2024-10-14 02:19:48,858 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:19:48,858 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:19:48,871 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2024-10-14 02:19:49,059 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:19:49,059 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:19:49,059 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:19:49,059 INFO L85 PathProgramCache]: Analyzing trace with hash -1344061032, now seen corresponding path program 4 times [2024-10-14 02:19:49,060 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:19:49,060 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1445483079] [2024-10-14 02:19:49,060 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:19:49,060 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:19:49,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:19:49,078 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1150590651] [2024-10-14 02:19:49,078 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-10-14 02:19:49,078 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:19:49,078 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:19:49,080 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-14 02:19:49,082 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-10-14 02:19:49,137 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-10-14 02:19:49,137 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-14 02:19:49,139 INFO L255 TraceCheckSpWp]: Trace formula consists of 251 conjuncts, 48 conjuncts are in the unsatisfiable core [2024-10-14 02:19:49,141 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:19:50,357 INFO L134 CoverageAnalysis]: Checked inductivity of 516 backedges. 100 proven. 59 refuted. 0 times theorem prover too weak. 357 trivial. 0 not checked. [2024-10-14 02:19:50,358 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:19:50,455 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:19:50,456 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1445483079] [2024-10-14 02:19:50,456 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:19:50,456 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1150590651] [2024-10-14 02:19:50,456 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1150590651] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:19:50,456 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-14 02:19:50,456 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2024-10-14 02:19:50,456 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1499780985] [2024-10-14 02:19:50,456 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-14 02:19:50,456 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-10-14 02:19:50,456 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:19:50,457 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-10-14 02:19:50,457 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=352, Unknown=0, NotChecked=0, Total=420 [2024-10-14 02:19:50,457 INFO L87 Difference]: Start difference. First operand 1697 states and 2167 transitions. Second operand has 18 states, 17 states have (on average 2.0588235294117645) internal successors, (35), 14 states have internal predecessors, (35), 8 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 7 states have call successors, (19) [2024-10-14 02:19:51,711 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:19:51,711 INFO L93 Difference]: Finished difference Result 1810 states and 2303 transitions. [2024-10-14 02:19:51,712 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-10-14 02:19:51,712 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.0588235294117645) internal successors, (35), 14 states have internal predecessors, (35), 8 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 7 states have call successors, (19) Word has length 119 [2024-10-14 02:19:51,712 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:19:51,720 INFO L225 Difference]: With dead ends: 1810 [2024-10-14 02:19:51,720 INFO L226 Difference]: Without dead ends: 1808 [2024-10-14 02:19:51,721 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 104 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 101 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=122, Invalid=580, Unknown=0, NotChecked=0, Total=702 [2024-10-14 02:19:51,721 INFO L432 NwaCegarLoop]: 50 mSDtfsCounter, 42 mSDsluCounter, 638 mSDsCounter, 0 mSdLazyCounter, 663 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 688 SdHoareTripleChecker+Invalid, 697 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 663 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-10-14 02:19:51,721 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 688 Invalid, 697 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 663 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-10-14 02:19:51,723 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1808 states. [2024-10-14 02:19:52,031 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1808 to 1694. [2024-10-14 02:19:52,033 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1694 states, 1084 states have (on average 1.1900369003690037) internal successors, (1290), 1098 states have internal predecessors, (1290), 438 states have call successors, (438), 171 states have call predecessors, (438), 171 states have return successors, (429), 424 states have call predecessors, (429), 429 states have call successors, (429) [2024-10-14 02:19:52,037 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1694 states to 1694 states and 2157 transitions. [2024-10-14 02:19:52,038 INFO L78 Accepts]: Start accepts. Automaton has 1694 states and 2157 transitions. Word has length 119 [2024-10-14 02:19:52,039 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-14 02:19:52,039 INFO L471 AbstractCegarLoop]: Abstraction has 1694 states and 2157 transitions. [2024-10-14 02:19:52,039 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 2.0588235294117645) internal successors, (35), 14 states have internal predecessors, (35), 8 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 7 states have call successors, (19) [2024-10-14 02:19:52,039 INFO L276 IsEmpty]: Start isEmpty. Operand 1694 states and 2157 transitions. [2024-10-14 02:19:52,040 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2024-10-14 02:19:52,040 INFO L207 NwaCegarLoop]: Found error trace [2024-10-14 02:19:52,040 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-14 02:19:52,052 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2024-10-14 02:19:52,240 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:19:52,241 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-14 02:19:52,241 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-14 02:19:52,241 INFO L85 PathProgramCache]: Analyzing trace with hash -1393224842, now seen corresponding path program 5 times [2024-10-14 02:19:52,241 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-14 02:19:52,241 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1990279750] [2024-10-14 02:19:52,241 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-14 02:19:52,241 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-14 02:19:52,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-14 02:19:52,264 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1922224390] [2024-10-14 02:19:52,264 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-10-14 02:19:52,264 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-14 02:19:52,264 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-14 02:19:52,266 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-14 02:19:52,267 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2024-10-14 02:19:52,413 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2024-10-14 02:19:52,413 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-14 02:19:52,415 INFO L255 TraceCheckSpWp]: Trace formula consists of 308 conjuncts, 63 conjuncts are in the unsatisfiable core [2024-10-14 02:19:52,419 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-14 02:19:53,396 INFO L134 CoverageAnalysis]: Checked inductivity of 523 backedges. 74 proven. 56 refuted. 0 times theorem prover too weak. 393 trivial. 0 not checked. [2024-10-14 02:19:53,396 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-14 02:20:12,081 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-14 02:20:12,081 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1990279750] [2024-10-14 02:20:12,081 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-14 02:20:12,081 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1922224390] [2024-10-14 02:20:12,081 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1922224390] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-14 02:20:12,081 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-10-14 02:20:12,081 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2024-10-14 02:20:12,081 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [247039691] [2024-10-14 02:20:12,081 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-10-14 02:20:12,082 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-10-14 02:20:12,082 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-14 02:20:12,082 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-10-14 02:20:12,082 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=615, Unknown=2, NotChecked=0, Total=756 [2024-10-14 02:20:12,082 INFO L87 Difference]: Start difference. First operand 1694 states and 2157 transitions. Second operand has 18 states, 17 states have (on average 2.2941176470588234) internal successors, (39), 15 states have internal predecessors, (39), 7 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) [2024-10-14 02:20:13,276 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-14 02:20:13,276 INFO L93 Difference]: Finished difference Result 1743 states and 2205 transitions. [2024-10-14 02:20:13,277 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-10-14 02:20:13,277 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.2941176470588234) internal successors, (39), 15 states have internal predecessors, (39), 7 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) Word has length 123 [2024-10-14 02:20:13,277 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-14 02:20:13,283 INFO L225 Difference]: With dead ends: 1743 [2024-10-14 02:20:13,283 INFO L226 Difference]: Without dead ends: 1741 [2024-10-14 02:20:13,283 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 173 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 219 ImplicationChecksByTransitivity, 17.3s TimeCoverageRelationStatistics Valid=213, Invalid=907, Unknown=2, NotChecked=0, Total=1122 [2024-10-14 02:20:13,284 INFO L432 NwaCegarLoop]: 51 mSDtfsCounter, 48 mSDsluCounter, 565 mSDsCounter, 0 mSdLazyCounter, 579 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 616 SdHoareTripleChecker+Invalid, 614 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 579 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-10-14 02:20:13,284 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 616 Invalid, 614 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 579 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-10-14 02:20:13,285 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1741 states.