./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/ps5-ll_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version a046e57d 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/ps5-ll_unwindbound10.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 1c50dd7e64abcc7a7eef6ea31e37156afb1e4322422284686cac6e6613b192c7 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-mul-div-a046e57-m [2024-10-12 19:09:19,639 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-12 19:09:19,716 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-12 19:09:19,723 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-12 19:09:19,724 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-12 19:09:19,747 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-12 19:09:19,748 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-12 19:09:19,749 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-12 19:09:19,749 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-12 19:09:19,750 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-12 19:09:19,763 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-12 19:09:19,763 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-12 19:09:19,764 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-12 19:09:19,765 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-12 19:09:19,765 INFO L153 SettingsManager]: * Use SBE=true [2024-10-12 19:09:19,765 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-12 19:09:19,765 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-12 19:09:19,766 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-12 19:09:19,766 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-12 19:09:19,766 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-12 19:09:19,767 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-12 19:09:19,767 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-12 19:09:19,768 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-12 19:09:19,768 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-12 19:09:19,768 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-12 19:09:19,768 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-12 19:09:19,769 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-12 19:09:19,769 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-12 19:09:19,769 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-12 19:09:19,770 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-12 19:09:19,770 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-12 19:09:19,770 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-12 19:09:19,770 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-12 19:09:19,771 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-12 19:09:19,771 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-12 19:09:19,771 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-12 19:09:19,772 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-12 19:09:19,772 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-12 19:09:19,772 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-12 19:09:19,773 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-12 19:09:19,773 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-12 19:09:19,773 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-12 19:09:19,773 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 -> 1c50dd7e64abcc7a7eef6ea31e37156afb1e4322422284686cac6e6613b192c7 [2024-10-12 19:09:20,017 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-12 19:09:20,040 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-12 19:09:20,044 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-12 19:09:20,046 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-12 19:09:20,046 INFO L274 PluginConnector]: CDTParser initialized [2024-10-12 19:09:20,047 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps5-ll_unwindbound10.c [2024-10-12 19:09:21,500 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-12 19:09:21,697 INFO L384 CDTParser]: Found 1 translation units. [2024-10-12 19:09:21,698 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps5-ll_unwindbound10.c [2024-10-12 19:09:21,704 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/99f6fb0f3/520d4028d2ff4135ad69a388f51495d1/FLAGed22d6ac4 [2024-10-12 19:09:21,719 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/99f6fb0f3/520d4028d2ff4135ad69a388f51495d1 [2024-10-12 19:09:21,722 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-12 19:09:21,724 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-12 19:09:21,725 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-12 19:09:21,725 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-12 19:09:21,733 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-12 19:09:21,734 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:21,734 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@77404e9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21, skipping insertion in model container [2024-10-12 19:09:21,735 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:21,753 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-12 19:09:21,919 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/ps5-ll_unwindbound10.c[458,471] [2024-10-12 19:09:21,940 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-12 19:09:21,948 INFO L200 MainTranslator]: Completed pre-run [2024-10-12 19:09:21,957 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/ps5-ll_unwindbound10.c[458,471] [2024-10-12 19:09:21,964 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-12 19:09:21,980 INFO L204 MainTranslator]: Completed translation [2024-10-12 19:09:21,980 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21 WrapperNode [2024-10-12 19:09:21,980 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-12 19:09:21,981 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-12 19:09:21,981 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-12 19:09:21,982 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-12 19:09:21,989 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:21,995 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:22,013 INFO L138 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 43 [2024-10-12 19:09:22,013 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-12 19:09:22,014 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-12 19:09:22,014 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-12 19:09:22,014 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-12 19:09:22,025 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:22,026 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:22,027 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:22,038 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-12 19:09:22,039 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:22,039 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:22,042 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:22,045 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:22,046 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:22,047 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:22,049 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-12 19:09:22,050 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-12 19:09:22,050 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-12 19:09:22,051 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-12 19:09:22,051 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21" (1/1) ... [2024-10-12 19:09:22,057 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-12 19:09:22,070 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 19:09:22,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-12 19:09:22,099 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-12 19:09:22,148 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-12 19:09:22,149 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-12 19:09:22,149 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-12 19:09:22,149 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-12 19:09:22,149 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-12 19:09:22,150 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-12 19:09:22,216 INFO L238 CfgBuilder]: Building ICFG [2024-10-12 19:09:22,220 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-12 19:09:22,424 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-10-12 19:09:22,425 INFO L287 CfgBuilder]: Performing block encoding [2024-10-12 19:09:22,469 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-12 19:09:22,470 INFO L314 CfgBuilder]: Removed 1 assume(true) statements. [2024-10-12 19:09:22,471 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 07:09:22 BoogieIcfgContainer [2024-10-12 19:09:22,471 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-12 19:09:22,474 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-12 19:09:22,475 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-12 19:09:22,478 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-12 19:09:22,478 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.10 07:09:21" (1/3) ... [2024-10-12 19:09:22,509 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7e8afda and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.10 07:09:22, skipping insertion in model container [2024-10-12 19:09:22,509 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 07:09:21" (2/3) ... [2024-10-12 19:09:22,509 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7e8afda and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.10 07:09:22, skipping insertion in model container [2024-10-12 19:09:22,509 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 07:09:22" (3/3) ... [2024-10-12 19:09:22,511 INFO L112 eAbstractionObserver]: Analyzing ICFG ps5-ll_unwindbound10.c [2024-10-12 19:09:22,529 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-12 19:09:22,529 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-12 19:09:22,596 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-12 19:09:22,605 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;@9816278, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-12 19:09:22,605 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-12 19:09:22,609 INFO L276 IsEmpty]: Start isEmpty. Operand has 17 states, 11 states have (on average 1.5454545454545454) internal successors, (17), 12 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-12 19:09:22,616 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-10-12 19:09:22,617 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 19:09:22,617 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 19:09:22,618 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 19:09:22,624 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 19:09:22,625 INFO L85 PathProgramCache]: Analyzing trace with hash 793793432, now seen corresponding path program 1 times [2024-10-12 19:09:22,634 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 19:09:22,635 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1291719565] [2024-10-12 19:09:22,635 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:22,635 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 19:09:22,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:22,779 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 19:09:22,779 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 19:09:22,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1291719565] [2024-10-12 19:09:22,780 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1291719565] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 19:09:22,780 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 19:09:22,780 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-12 19:09:22,781 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [690593286] [2024-10-12 19:09:22,782 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 19:09:22,784 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-12 19:09:22,784 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 19:09:22,802 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-12 19:09:22,803 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-12 19:09:22,804 INFO L87 Difference]: Start difference. First operand has 17 states, 11 states have (on average 1.5454545454545454) internal successors, (17), 12 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-12 19:09:22,827 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 19:09:22,828 INFO L93 Difference]: Finished difference Result 32 states and 46 transitions. [2024-10-12 19:09:22,828 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-12 19:09:22,829 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-10-12 19:09:22,830 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 19:09:22,835 INFO L225 Difference]: With dead ends: 32 [2024-10-12 19:09:22,835 INFO L226 Difference]: Without dead ends: 15 [2024-10-12 19:09:22,838 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-12 19:09:22,841 INFO L432 NwaCegarLoop]: 18 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, 18 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-12 19:09:22,842 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 18 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 19:09:22,857 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2024-10-12 19:09:22,869 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2024-10-12 19:09:22,871 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-12 19:09:22,871 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 18 transitions. [2024-10-12 19:09:22,873 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 18 transitions. Word has length 8 [2024-10-12 19:09:22,873 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 19:09:22,873 INFO L471 AbstractCegarLoop]: Abstraction has 15 states and 18 transitions. [2024-10-12 19:09:22,873 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-12 19:09:22,874 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 18 transitions. [2024-10-12 19:09:22,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-10-12 19:09:22,874 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 19:09:22,874 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 19:09:22,875 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-12 19:09:22,875 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 19:09:22,875 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 19:09:22,876 INFO L85 PathProgramCache]: Analyzing trace with hash 1922989550, now seen corresponding path program 1 times [2024-10-12 19:09:22,876 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 19:09:22,876 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1126401086] [2024-10-12 19:09:22,876 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:22,876 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 19:09:22,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:23,037 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 19:09:23,037 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 19:09:23,038 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1126401086] [2024-10-12 19:09:23,038 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1126401086] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 19:09:23,038 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 19:09:23,038 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-10-12 19:09:23,038 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [803583194] [2024-10-12 19:09:23,039 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 19:09:23,040 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-12 19:09:23,040 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 19:09:23,041 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-12 19:09:23,041 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-10-12 19:09:23,041 INFO L87 Difference]: Start difference. First operand 15 states and 18 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-12 19:09:23,064 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 19:09:23,064 INFO L93 Difference]: Finished difference Result 25 states and 29 transitions. [2024-10-12 19:09:23,066 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-12 19:09:23,066 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-10-12 19:09:23,066 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 19:09:23,067 INFO L225 Difference]: With dead ends: 25 [2024-10-12 19:09:23,067 INFO L226 Difference]: Without dead ends: 17 [2024-10-12 19:09:23,067 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 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-12 19:09:23,070 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 0 mSDsluCounter, 27 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 19:09:23,071 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 42 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 19:09:23,071 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2024-10-12 19:09:23,077 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2024-10-12 19:09:23,078 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-12 19:09:23,078 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 20 transitions. [2024-10-12 19:09:23,079 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 20 transitions. Word has length 9 [2024-10-12 19:09:23,079 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 19:09:23,079 INFO L471 AbstractCegarLoop]: Abstraction has 17 states and 20 transitions. [2024-10-12 19:09:23,079 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-12 19:09:23,081 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 20 transitions. [2024-10-12 19:09:23,082 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-10-12 19:09:23,082 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 19:09:23,082 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 19:09:23,082 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-12 19:09:23,082 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 19:09:23,083 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 19:09:23,083 INFO L85 PathProgramCache]: Analyzing trace with hash 1924777010, now seen corresponding path program 1 times [2024-10-12 19:09:23,083 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 19:09:23,083 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1332679022] [2024-10-12 19:09:23,083 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:23,084 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 19:09:23,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 19:09:23,116 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2109732834] [2024-10-12 19:09:23,117 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:23,117 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 19:09:23,117 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 19:09:23,119 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-12 19:09:23,120 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-12 19:09:23,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:23,168 INFO L255 TraceCheckSpWp]: Trace formula consists of 48 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 19:09:23,173 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 19:09:23,277 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 19:09:23,278 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-12 19:09:23,278 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 19:09:23,278 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1332679022] [2024-10-12 19:09:23,279 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 19:09:23,280 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2109732834] [2024-10-12 19:09:23,280 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2109732834] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 19:09:23,281 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 19:09:23,281 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-12 19:09:23,281 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1820668932] [2024-10-12 19:09:23,281 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 19:09:23,282 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 19:09:23,282 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 19:09:23,282 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 19:09:23,283 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-12 19:09:23,283 INFO L87 Difference]: Start difference. First operand 17 states and 20 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-12 19:09:23,349 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 19:09:23,349 INFO L93 Difference]: Finished difference Result 27 states and 32 transitions. [2024-10-12 19:09:23,350 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-12 19:09:23,350 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-10-12 19:09:23,350 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 19:09:23,351 INFO L225 Difference]: With dead ends: 27 [2024-10-12 19:09:23,351 INFO L226 Difference]: Without dead ends: 23 [2024-10-12 19:09:23,351 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 5 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-12 19:09:23,352 INFO L432 NwaCegarLoop]: 14 mSDtfsCounter, 4 mSDsluCounter, 38 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 52 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 19:09:23,353 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 52 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 19:09:23,353 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2024-10-12 19:09:23,358 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2024-10-12 19:09:23,358 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 16 states have (on average 1.1875) internal successors, (19), 17 states have internal predecessors, (19), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-12 19:09:23,359 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 26 transitions. [2024-10-12 19:09:23,359 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 26 transitions. Word has length 9 [2024-10-12 19:09:23,359 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 19:09:23,359 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 26 transitions. [2024-10-12 19:09:23,359 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-12 19:09:23,359 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 26 transitions. [2024-10-12 19:09:23,360 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-10-12 19:09:23,360 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 19:09:23,360 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 19:09:23,379 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-12 19:09:23,564 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-12 19:09:23,565 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 19:09:23,565 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 19:09:23,566 INFO L85 PathProgramCache]: Analyzing trace with hash 76913492, now seen corresponding path program 1 times [2024-10-12 19:09:23,566 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 19:09:23,566 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [521112447] [2024-10-12 19:09:23,566 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:23,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 19:09:23,582 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:23,720 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-12 19:09:23,723 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:23,738 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 19:09:23,738 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 19:09:23,738 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [521112447] [2024-10-12 19:09:23,738 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [521112447] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 19:09:23,738 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1140817140] [2024-10-12 19:09:23,738 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:23,739 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 19:09:23,739 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 19:09:23,740 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-12 19:09:23,742 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-12 19:09:23,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:23,786 INFO L255 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-10-12 19:09:23,788 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 19:09:23,822 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 19:09:23,822 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 19:09:23,883 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 19:09:23,884 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1140817140] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 19:09:23,884 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 19:09:23,884 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 4, 5] total 10 [2024-10-12 19:09:23,884 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [508443862] [2024-10-12 19:09:23,885 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 19:09:23,885 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-10-12 19:09:23,887 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 19:09:23,889 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-10-12 19:09:23,889 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-10-12 19:09:23,889 INFO L87 Difference]: Start difference. First operand 23 states and 26 transitions. Second operand has 10 states, 10 states have (on average 3.0) internal successors, (30), 10 states have internal predecessors, (30), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-12 19:09:23,995 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 19:09:23,996 INFO L93 Difference]: Finished difference Result 57 states and 67 transitions. [2024-10-12 19:09:23,996 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-12 19:09:23,997 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.0) internal successors, (30), 10 states have internal predecessors, (30), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 17 [2024-10-12 19:09:23,997 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 19:09:23,999 INFO L225 Difference]: With dead ends: 57 [2024-10-12 19:09:23,999 INFO L226 Difference]: Without dead ends: 49 [2024-10-12 19:09:24,000 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2024-10-12 19:09:24,001 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 29 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 19:09:24,002 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 75 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 19:09:24,003 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-10-12 19:09:24,015 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 45. [2024-10-12 19:09:24,015 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 33 states have internal predecessors, (37), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-12 19:09:24,020 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 54 transitions. [2024-10-12 19:09:24,020 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 54 transitions. Word has length 17 [2024-10-12 19:09:24,021 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 19:09:24,021 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 54 transitions. [2024-10-12 19:09:24,021 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.0) internal successors, (30), 10 states have internal predecessors, (30), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-12 19:09:24,021 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 54 transitions. [2024-10-12 19:09:24,022 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-10-12 19:09:24,022 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 19:09:24,022 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 19:09:24,036 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-12 19:09:24,222 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-12 19:09:24,223 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 19:09:24,223 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 19:09:24,224 INFO L85 PathProgramCache]: Analyzing trace with hash 78700952, now seen corresponding path program 1 times [2024-10-12 19:09:24,224 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 19:09:24,224 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [26492245] [2024-10-12 19:09:24,224 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:24,224 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 19:09:24,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 19:09:24,247 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [540659081] [2024-10-12 19:09:24,248 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:24,248 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 19:09:24,248 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 19:09:24,250 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-12 19:09:24,251 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-12 19:09:24,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:24,298 INFO L255 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-12 19:09:24,300 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 19:09:24,397 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 19:09:24,399 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 19:09:24,523 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-10-12 19:09:24,524 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 19:09:24,524 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [26492245] [2024-10-12 19:09:24,524 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 19:09:24,528 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [540659081] [2024-10-12 19:09:24,528 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [540659081] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-12 19:09:24,529 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-12 19:09:24,529 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-10-12 19:09:24,529 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [814622299] [2024-10-12 19:09:24,529 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 19:09:24,529 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-12 19:09:24,529 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 19:09:24,530 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-12 19:09:24,530 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-10-12 19:09:24,530 INFO L87 Difference]: Start difference. First operand 45 states and 54 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 19:09:24,590 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 19:09:24,591 INFO L93 Difference]: Finished difference Result 59 states and 67 transitions. [2024-10-12 19:09:24,591 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-12 19:09:24,592 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 17 [2024-10-12 19:09:24,592 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 19:09:24,592 INFO L225 Difference]: With dead ends: 59 [2024-10-12 19:09:24,593 INFO L226 Difference]: Without dead ends: 51 [2024-10-12 19:09:24,593 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 25 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-10-12 19:09:24,594 INFO L432 NwaCegarLoop]: 12 mSDtfsCounter, 5 mSDsluCounter, 28 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-12 19:09:24,594 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 40 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-12 19:09:24,595 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2024-10-12 19:09:24,613 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 45. [2024-10-12 19:09:24,614 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 32 states have (on average 1.125) internal successors, (36), 34 states have internal predecessors, (36), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-12 19:09:24,616 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 51 transitions. [2024-10-12 19:09:24,618 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 51 transitions. Word has length 17 [2024-10-12 19:09:24,618 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 19:09:24,619 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 51 transitions. [2024-10-12 19:09:24,619 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 19:09:24,619 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 51 transitions. [2024-10-12 19:09:24,619 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-10-12 19:09:24,620 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 19:09:24,620 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 19:09:24,637 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-10-12 19:09:24,820 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-12 19:09:24,821 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 19:09:24,821 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 19:09:24,821 INFO L85 PathProgramCache]: Analyzing trace with hash 731759343, now seen corresponding path program 1 times [2024-10-12 19:09:24,821 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 19:09:24,821 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1807741410] [2024-10-12 19:09:24,821 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:24,821 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 19:09:24,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 19:09:24,857 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [524331681] [2024-10-12 19:09:24,860 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:24,860 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 19:09:24,860 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 19:09:24,862 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-12 19:09:24,864 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-12 19:09:24,916 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:24,917 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-12 19:09:24,919 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 19:09:25,047 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-10-12 19:09:25,048 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 19:09:25,159 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-10-12 19:09:25,159 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 19:09:25,159 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1807741410] [2024-10-12 19:09:25,160 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 19:09:25,160 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [524331681] [2024-10-12 19:09:25,160 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [524331681] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 19:09:25,160 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 19:09:25,160 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-10-12 19:09:25,160 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [534163819] [2024-10-12 19:09:25,161 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 19:09:25,161 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-10-12 19:09:25,161 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 19:09:25,162 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-10-12 19:09:25,162 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2024-10-12 19:09:25,162 INFO L87 Difference]: Start difference. First operand 45 states and 51 transitions. Second operand has 10 states, 8 states have (on average 2.75) internal successors, (22), 9 states have internal predecessors, (22), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-12 19:09:25,277 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 19:09:25,277 INFO L93 Difference]: Finished difference Result 54 states and 62 transitions. [2024-10-12 19:09:25,277 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-12 19:09:25,278 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.75) internal successors, (22), 9 states have internal predecessors, (22), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 28 [2024-10-12 19:09:25,278 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 19:09:25,278 INFO L225 Difference]: With dead ends: 54 [2024-10-12 19:09:25,279 INFO L226 Difference]: Without dead ends: 45 [2024-10-12 19:09:25,279 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 44 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2024-10-12 19:09:25,280 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 1 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 53 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 19:09:25,280 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 98 Invalid, 53 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 19:09:25,281 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-10-12 19:09:25,293 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2024-10-12 19:09:25,293 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 33 states have (on average 1.0606060606060606) internal successors, (35), 33 states have internal predecessors, (35), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-12 19:09:25,294 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 48 transitions. [2024-10-12 19:09:25,294 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 48 transitions. Word has length 28 [2024-10-12 19:09:25,294 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 19:09:25,294 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 48 transitions. [2024-10-12 19:09:25,295 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.75) internal successors, (22), 9 states have internal predecessors, (22), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-12 19:09:25,295 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 48 transitions. [2024-10-12 19:09:25,296 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-10-12 19:09:25,296 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 19:09:25,296 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 19:09:25,313 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-12 19:09:25,500 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 19:09:25,501 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 19:09:25,501 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 19:09:25,501 INFO L85 PathProgramCache]: Analyzing trace with hash -1074423298, now seen corresponding path program 1 times [2024-10-12 19:09:25,501 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 19:09:25,501 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [935574884] [2024-10-12 19:09:25,501 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:25,502 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 19:09:25,524 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:25,706 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-10-12 19:09:25,708 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:25,715 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-10-12 19:09:25,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:25,720 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-10-12 19:09:25,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:25,725 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-12 19:09:25,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:25,730 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-12 19:09:25,731 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:25,733 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-10-12 19:09:25,734 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 19:09:25,734 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [935574884] [2024-10-12 19:09:25,734 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [935574884] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 19:09:25,734 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1202399195] [2024-10-12 19:09:25,734 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:25,734 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 19:09:25,747 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 19:09:25,749 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-12 19:09:25,751 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-12 19:09:25,812 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 19:09:25,814 INFO L255 TraceCheckSpWp]: Trace formula consists of 141 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-12 19:09:25,816 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 19:09:25,885 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 24 proven. 56 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-10-12 19:09:25,886 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 19:09:26,013 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 10 proven. 32 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-10-12 19:09:26,014 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1202399195] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 19:09:26,014 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 19:09:26,014 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 16 [2024-10-12 19:09:26,014 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [997800112] [2024-10-12 19:09:26,014 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 19:09:26,015 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-12 19:09:26,015 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 19:09:26,016 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-12 19:09:26,016 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=144, Unknown=0, NotChecked=0, Total=240 [2024-10-12 19:09:26,016 INFO L87 Difference]: Start difference. First operand 45 states and 48 transitions. Second operand has 16 states, 16 states have (on average 3.6875) internal successors, (59), 16 states have internal predecessors, (59), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) [2024-10-12 19:09:26,255 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 19:09:26,256 INFO L93 Difference]: Finished difference Result 131 states and 143 transitions. [2024-10-12 19:09:26,256 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-10-12 19:09:26,256 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.6875) internal successors, (59), 16 states have internal predecessors, (59), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) Word has length 46 [2024-10-12 19:09:26,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 19:09:26,258 INFO L225 Difference]: With dead ends: 131 [2024-10-12 19:09:26,258 INFO L226 Difference]: Without dead ends: 121 [2024-10-12 19:09:26,258 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 94 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=196, Invalid=356, Unknown=0, NotChecked=0, Total=552 [2024-10-12 19:09:26,259 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 71 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 71 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 87 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-12 19:09:26,259 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [71 Valid, 111 Invalid, 87 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-12 19:09:26,260 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2024-10-12 19:09:26,294 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 96. [2024-10-12 19:09:26,295 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 68 states have (on average 1.1029411764705883) internal successors, (75), 73 states have internal predecessors, (75), 17 states have call successors, (17), 11 states have call predecessors, (17), 10 states have return successors, (16), 11 states have call predecessors, (16), 16 states have call successors, (16) [2024-10-12 19:09:26,296 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 108 transitions. [2024-10-12 19:09:26,297 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 108 transitions. Word has length 46 [2024-10-12 19:09:26,298 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 19:09:26,298 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 108 transitions. [2024-10-12 19:09:26,299 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.6875) internal successors, (59), 16 states have internal predecessors, (59), 9 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 9 states have call predecessors, (14), 9 states have call successors, (14) [2024-10-12 19:09:26,300 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 108 transitions. [2024-10-12 19:09:26,301 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-10-12 19:09:26,302 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 19:09:26,302 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 19:09:26,322 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-12 19:09:26,502 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 19:09:26,503 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 19:09:26,503 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 19:09:26,503 INFO L85 PathProgramCache]: Analyzing trace with hash -1441866883, now seen corresponding path program 2 times [2024-10-12 19:09:26,504 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 19:09:26,504 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [779102764] [2024-10-12 19:09:26,504 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:26,504 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 19:09:26,561 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 19:09:26,563 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1151416675] [2024-10-12 19:09:26,563 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-12 19:09:26,563 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 19:09:26,564 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 19:09:26,565 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-12 19:09:26,567 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-12 19:09:26,629 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-12 19:09:26,629 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-12 19:09:26,631 INFO L255 TraceCheckSpWp]: Trace formula consists of 151 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-10-12 19:09:26,633 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 19:09:26,885 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 12 proven. 40 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-10-12 19:09:26,886 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 19:09:27,245 INFO L134 CoverageAnalysis]: Checked inductivity of 112 backedges. 12 proven. 40 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-10-12 19:09:27,245 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 19:09:27,245 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [779102764] [2024-10-12 19:09:27,245 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-12 19:09:27,245 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1151416675] [2024-10-12 19:09:27,246 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1151416675] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 19:09:27,246 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-12 19:09:27,246 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 20 [2024-10-12 19:09:27,246 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [853138929] [2024-10-12 19:09:27,246 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-12 19:09:27,247 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-10-12 19:09:27,247 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 19:09:27,248 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-10-12 19:09:27,248 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=313, Unknown=0, NotChecked=0, Total=380 [2024-10-12 19:09:27,248 INFO L87 Difference]: Start difference. First operand 96 states and 108 transitions. Second operand has 20 states, 18 states have (on average 2.4444444444444446) internal successors, (44), 18 states have internal predecessors, (44), 12 states have call successors, (14), 3 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-10-12 19:09:27,763 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 19:09:27,764 INFO L93 Difference]: Finished difference Result 102 states and 113 transitions. [2024-10-12 19:09:27,764 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-10-12 19:09:27,764 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 2.4444444444444446) internal successors, (44), 18 states have internal predecessors, (44), 12 states have call successors, (14), 3 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Word has length 52 [2024-10-12 19:09:27,765 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-12 19:09:27,766 INFO L225 Difference]: With dead ends: 102 [2024-10-12 19:09:27,768 INFO L226 Difference]: Without dead ends: 91 [2024-10-12 19:09:27,769 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 133 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=167, Invalid=703, Unknown=0, NotChecked=0, Total=870 [2024-10-12 19:09:27,770 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 23 mSDsluCounter, 318 mSDsCounter, 0 mSdLazyCounter, 200 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 348 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 200 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-12 19:09:27,770 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 348 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 200 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-12 19:09:27,771 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2024-10-12 19:09:27,792 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 91. [2024-10-12 19:09:27,792 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 68 states have (on average 1.0294117647058822) internal successors, (70), 68 states have internal predecessors, (70), 12 states have call successors, (12), 11 states have call predecessors, (12), 10 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-10-12 19:09:27,793 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 93 transitions. [2024-10-12 19:09:27,793 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 93 transitions. Word has length 52 [2024-10-12 19:09:27,794 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-12 19:09:27,794 INFO L471 AbstractCegarLoop]: Abstraction has 91 states and 93 transitions. [2024-10-12 19:09:27,794 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 2.4444444444444446) internal successors, (44), 18 states have internal predecessors, (44), 12 states have call successors, (14), 3 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-10-12 19:09:27,794 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 93 transitions. [2024-10-12 19:09:27,795 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2024-10-12 19:09:27,795 INFO L207 NwaCegarLoop]: Found error trace [2024-10-12 19:09:27,796 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 19:09:27,814 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-12 19:09:27,999 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 19:09:28,000 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-12 19:09:28,000 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 19:09:28,000 INFO L85 PathProgramCache]: Analyzing trace with hash -1566715457, now seen corresponding path program 3 times [2024-10-12 19:09:28,000 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 19:09:28,000 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [655887235] [2024-10-12 19:09:28,001 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 19:09:28,001 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 19:09:28,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-12 19:09:28,083 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1979902329] [2024-10-12 19:09:28,084 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-12 19:09:28,084 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 19:09:28,084 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 19:09:28,086 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-12 19:09:28,087 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process