./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_unwindbound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3289d67d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_unwindbound100.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 376367d14f0ef5deff3321a7267050cf9f2383eb99d0a19dad6a556c0772ff28 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-3289d67-m [2024-11-16 06:58:31,633 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-16 06:58:31,692 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-16 06:58:31,695 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-16 06:58:31,696 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-16 06:58:31,714 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-16 06:58:31,715 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-16 06:58:31,715 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-16 06:58:31,715 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-16 06:58:31,716 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-16 06:58:31,716 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-16 06:58:31,716 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-16 06:58:31,718 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-16 06:58:31,719 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-16 06:58:31,719 INFO L153 SettingsManager]: * Use SBE=true [2024-11-16 06:58:31,719 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-16 06:58:31,720 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-16 06:58:31,720 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-16 06:58:31,720 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-16 06:58:31,720 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-16 06:58:31,720 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-16 06:58:31,724 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-16 06:58:31,724 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-16 06:58:31,724 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-16 06:58:31,724 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-16 06:58:31,725 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-16 06:58:31,725 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-16 06:58:31,725 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-16 06:58:31,725 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-16 06:58:31,725 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-16 06:58:31,726 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-16 06:58:31,726 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-16 06:58:31,726 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-16 06:58:31,726 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-16 06:58:31,726 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-16 06:58:31,726 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-16 06:58:31,727 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-16 06:58:31,727 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-16 06:58:31,727 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-16 06:58:31,727 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-16 06:58:31,727 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-16 06:58:31,728 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-16 06:58:31,728 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 -> 376367d14f0ef5deff3321a7267050cf9f2383eb99d0a19dad6a556c0772ff28 [2024-11-16 06:58:31,923 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-16 06:58:31,942 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-16 06:58:31,944 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-16 06:58:31,945 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-16 06:58:31,945 INFO L274 PluginConnector]: CDTParser initialized [2024-11-16 06:58:31,946 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_unwindbound100.c [2024-11-16 06:58:33,279 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-16 06:58:33,430 INFO L384 CDTParser]: Found 1 translation units. [2024-11-16 06:58:33,434 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_unwindbound100.c [2024-11-16 06:58:33,442 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/575c7daab/8ec4aae260504cbb822a6aee47bb7923/FLAGb91fb01f3 [2024-11-16 06:58:33,454 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/575c7daab/8ec4aae260504cbb822a6aee47bb7923 [2024-11-16 06:58:33,456 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-16 06:58:33,457 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-16 06:58:33,458 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-16 06:58:33,459 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-16 06:58:33,463 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-16 06:58:33,464 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,464 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1ed5f13a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33, skipping insertion in model container [2024-11-16 06:58:33,465 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,478 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-16 06:58:33,690 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_unwindbound100.c[525,538] [2024-11-16 06:58:33,721 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-16 06:58:33,729 INFO L200 MainTranslator]: Completed pre-run [2024-11-16 06:58:33,738 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_unwindbound100.c[525,538] [2024-11-16 06:58:33,747 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-16 06:58:33,759 INFO L204 MainTranslator]: Completed translation [2024-11-16 06:58:33,760 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33 WrapperNode [2024-11-16 06:58:33,760 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-16 06:58:33,761 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-16 06:58:33,761 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-16 06:58:33,761 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-16 06:58:33,766 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,771 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,787 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 62 [2024-11-16 06:58:33,787 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-16 06:58:33,788 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-16 06:58:33,788 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-16 06:58:33,788 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-16 06:58:33,795 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,796 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,797 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,806 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-11-16 06:58:33,806 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,806 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,809 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,809 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,810 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,810 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,811 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-16 06:58:33,812 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-16 06:58:33,812 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-16 06:58:33,812 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-16 06:58:33,813 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33" (1/1) ... [2024-11-16 06:58:33,818 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-16 06:58:33,827 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 06:58:33,840 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-16 06:58:33,842 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-16 06:58:33,875 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-16 06:58:33,876 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-16 06:58:33,876 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-16 06:58:33,876 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-16 06:58:33,876 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-16 06:58:33,876 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-16 06:58:33,934 INFO L256 CfgBuilder]: Building ICFG [2024-11-16 06:58:33,938 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-16 06:58:34,153 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-16 06:58:34,153 INFO L307 CfgBuilder]: Performing block encoding [2024-11-16 06:58:34,162 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-16 06:58:34,162 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-16 06:58:34,163 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.11 06:58:34 BoogieIcfgContainer [2024-11-16 06:58:34,163 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-16 06:58:34,165 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-16 06:58:34,166 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-16 06:58:34,168 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-16 06:58:34,168 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.11 06:58:33" (1/3) ... [2024-11-16 06:58:34,169 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@11a970e2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.11 06:58:34, skipping insertion in model container [2024-11-16 06:58:34,170 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 06:58:33" (2/3) ... [2024-11-16 06:58:34,170 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@11a970e2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.11 06:58:34, skipping insertion in model container [2024-11-16 06:58:34,170 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.11 06:58:34" (3/3) ... [2024-11-16 06:58:34,171 INFO L112 eAbstractionObserver]: Analyzing ICFG dijkstra-u_unwindbound100.c [2024-11-16 06:58:34,183 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-16 06:58:34,183 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-16 06:58:34,224 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-16 06:58:34,229 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;@318546e5, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-16 06:58:34,229 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-16 06:58:34,232 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 9 states have call successors, (9), 1 states have call predecessors, (9), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-16 06:58:34,240 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-16 06:58:34,244 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 06:58:34,245 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 06:58:34,245 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 06:58:34,248 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 06:58:34,250 INFO L85 PathProgramCache]: Analyzing trace with hash 621682870, now seen corresponding path program 1 times [2024-11-16 06:58:34,256 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 06:58:34,257 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1780656638] [2024-11-16 06:58:34,257 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:58:34,257 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 06:58:34,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:58:34,373 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:58:34,373 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 06:58:34,373 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1780656638] [2024-11-16 06:58:34,374 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1780656638] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 06:58:34,374 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 06:58:34,374 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-16 06:58:34,375 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [494953273] [2024-11-16 06:58:34,376 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 06:58:34,380 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-16 06:58:34,381 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 06:58:34,401 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-16 06:58:34,402 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-16 06:58:34,403 INFO L87 Difference]: Start difference. First operand has 31 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 9 states have call successors, (9), 1 states have call predecessors, (9), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 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-11-16 06:58:34,421 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 06:58:34,422 INFO L93 Difference]: Finished difference Result 59 states and 99 transitions. [2024-11-16 06:58:34,423 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-16 06:58:34,424 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 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 11 [2024-11-16 06:58:34,424 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 06:58:34,429 INFO L225 Difference]: With dead ends: 59 [2024-11-16 06:58:34,429 INFO L226 Difference]: Without dead ends: 27 [2024-11-16 06:58:34,431 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-16 06:58:34,436 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 06:58:34,437 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 06:58:34,452 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2024-11-16 06:58:34,465 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2024-11-16 06:58:34,467 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 9 states have call successors, (9), 1 states have call predecessors, (9), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-16 06:58:34,468 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 39 transitions. [2024-11-16 06:58:34,470 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 39 transitions. Word has length 11 [2024-11-16 06:58:34,470 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 06:58:34,470 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 39 transitions. [2024-11-16 06:58:34,471 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 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-11-16 06:58:34,471 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 39 transitions. [2024-11-16 06:58:34,472 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-16 06:58:34,472 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 06:58:34,473 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 06:58:34,473 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-16 06:58:34,473 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 06:58:34,474 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 06:58:34,474 INFO L85 PathProgramCache]: Analyzing trace with hash -770397230, now seen corresponding path program 1 times [2024-11-16 06:58:34,474 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 06:58:34,475 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1907555776] [2024-11-16 06:58:34,475 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:58:34,475 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 06:58:34,497 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:58:34,592 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:58:34,592 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 06:58:34,593 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1907555776] [2024-11-16 06:58:34,593 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1907555776] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 06:58:34,593 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 06:58:34,594 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-16 06:58:34,594 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1727192160] [2024-11-16 06:58:34,594 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 06:58:34,595 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-16 06:58:34,596 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 06:58:34,597 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-16 06:58:34,597 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-16 06:58:34,598 INFO L87 Difference]: Start difference. First operand 27 states and 39 transitions. Second operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 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-11-16 06:58:34,623 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 06:58:34,624 INFO L93 Difference]: Finished difference Result 49 states and 72 transitions. [2024-11-16 06:58:34,624 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-16 06:58:34,625 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 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 13 [2024-11-16 06:58:34,625 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 06:58:34,626 INFO L225 Difference]: With dead ends: 49 [2024-11-16 06:58:34,626 INFO L226 Difference]: Without dead ends: 29 [2024-11-16 06:58:34,626 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-11-16 06:58:34,628 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 0 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 104 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-11-16 06:58:34,628 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 104 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 06:58:34,629 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2024-11-16 06:58:34,634 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2024-11-16 06:58:34,634 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 9 states have call successors, (9), 1 states have call predecessors, (9), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-16 06:58:34,638 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 41 transitions. [2024-11-16 06:58:34,638 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 41 transitions. Word has length 13 [2024-11-16 06:58:34,638 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 06:58:34,638 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 41 transitions. [2024-11-16 06:58:34,638 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 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-11-16 06:58:34,638 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 41 transitions. [2024-11-16 06:58:34,639 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-16 06:58:34,639 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 06:58:34,639 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 06:58:34,639 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-16 06:58:34,639 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 06:58:34,640 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 06:58:34,640 INFO L85 PathProgramCache]: Analyzing trace with hash 1963862612, now seen corresponding path program 1 times [2024-11-16 06:58:34,640 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 06:58:34,640 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1434861699] [2024-11-16 06:58:34,641 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:58:34,641 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 06:58:34,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:58:34,765 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:58:34,766 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 06:58:34,766 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1434861699] [2024-11-16 06:58:34,766 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1434861699] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 06:58:34,766 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 06:58:34,766 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-16 06:58:34,766 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [136717464] [2024-11-16 06:58:34,766 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 06:58:34,766 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 06:58:34,767 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 06:58:34,767 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 06:58:34,767 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-16 06:58:34,767 INFO L87 Difference]: Start difference. First operand 29 states and 41 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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-11-16 06:58:34,794 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 06:58:34,794 INFO L93 Difference]: Finished difference Result 43 states and 58 transitions. [2024-11-16 06:58:34,796 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 06:58:34,796 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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 14 [2024-11-16 06:58:34,796 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 06:58:34,797 INFO L225 Difference]: With dead ends: 43 [2024-11-16 06:58:34,797 INFO L226 Difference]: Without dead ends: 33 [2024-11-16 06:58:34,797 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-16 06:58:34,798 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 1 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 06:58:34,799 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 105 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 06:58:34,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2024-11-16 06:58:34,802 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 32. [2024-11-16 06:58:34,802 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 21 states have (on average 1.3333333333333333) internal successors, (28), 22 states have internal predecessors, (28), 9 states have call successors, (9), 1 states have call predecessors, (9), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-16 06:58:34,803 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 45 transitions. [2024-11-16 06:58:34,803 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 45 transitions. Word has length 14 [2024-11-16 06:58:34,804 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 06:58:34,804 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 45 transitions. [2024-11-16 06:58:34,804 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 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-11-16 06:58:34,804 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 45 transitions. [2024-11-16 06:58:34,804 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-16 06:58:34,804 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 06:58:34,805 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 06:58:34,805 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-16 06:58:34,805 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 06:58:34,805 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 06:58:34,805 INFO L85 PathProgramCache]: Analyzing trace with hash 2003574015, now seen corresponding path program 1 times [2024-11-16 06:58:34,806 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 06:58:34,806 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [804147041] [2024-11-16 06:58:34,806 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:58:34,806 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 06:58:34,837 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:58:35,105 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:58:35,105 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 06:58:35,105 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [804147041] [2024-11-16 06:58:35,105 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [804147041] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 06:58:35,106 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 06:58:35,106 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-16 06:58:35,106 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [926171175] [2024-11-16 06:58:35,106 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 06:58:35,106 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-16 06:58:35,107 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 06:58:35,107 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-16 06:58:35,107 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-16 06:58:35,107 INFO L87 Difference]: Start difference. First operand 32 states and 45 transitions. Second operand has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 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-11-16 06:58:35,337 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 06:58:35,337 INFO L93 Difference]: Finished difference Result 63 states and 93 transitions. [2024-11-16 06:58:35,340 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-16 06:58:35,340 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 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 14 [2024-11-16 06:58:35,340 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 06:58:35,341 INFO L225 Difference]: With dead ends: 63 [2024-11-16 06:58:35,341 INFO L226 Difference]: Without dead ends: 43 [2024-11-16 06:58:35,342 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-16 06:58:35,342 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 6 mSDsluCounter, 139 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 182 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-16 06:58:35,343 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 182 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-16 06:58:35,343 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-16 06:58:35,351 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2024-11-16 06:58:35,352 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 25 states have (on average 1.28) internal successors, (32), 26 states have internal predecessors, (32), 15 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-16 06:58:35,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 61 transitions. [2024-11-16 06:58:35,353 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 61 transitions. Word has length 14 [2024-11-16 06:58:35,354 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 06:58:35,354 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 61 transitions. [2024-11-16 06:58:35,354 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 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-11-16 06:58:35,354 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 61 transitions. [2024-11-16 06:58:35,355 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-16 06:58:35,355 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 06:58:35,355 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 06:58:35,355 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-16 06:58:35,355 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 06:58:35,356 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 06:58:35,356 INFO L85 PathProgramCache]: Analyzing trace with hash 2027361748, now seen corresponding path program 1 times [2024-11-16 06:58:35,357 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 06:58:35,357 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [681941455] [2024-11-16 06:58:35,357 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:58:35,358 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 06:58:35,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:58:35,413 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:58:35,414 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 06:58:35,414 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [681941455] [2024-11-16 06:58:35,414 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [681941455] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 06:58:35,415 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1391317217] [2024-11-16 06:58:35,415 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:58:35,415 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 06:58:35,415 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 06:58:35,424 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 06:58:35,425 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-16 06:58:35,467 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:58:35,469 INFO L255 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-16 06:58:35,472 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 06:58:35,513 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:58:35,514 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 06:58:35,556 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:58:35,556 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1391317217] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 06:58:35,556 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 06:58:35,557 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 7 [2024-11-16 06:58:35,557 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1703849210] [2024-11-16 06:58:35,557 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 06:58:35,557 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-16 06:58:35,557 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 06:58:35,558 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-16 06:58:35,558 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2024-11-16 06:58:35,558 INFO L87 Difference]: Start difference. First operand 43 states and 61 transitions. Second operand has 8 states, 8 states have (on average 3.0) internal successors, (24), 7 states have internal predecessors, (24), 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-11-16 06:58:36,902 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.29s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:58:37,065 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 06:58:37,065 INFO L93 Difference]: Finished difference Result 102 states and 146 transitions. [2024-11-16 06:58:37,066 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-16 06:58:37,067 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.0) internal successors, (24), 7 states have internal predecessors, (24), 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 16 [2024-11-16 06:58:37,067 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 06:58:37,068 INFO L225 Difference]: With dead ends: 102 [2024-11-16 06:58:37,069 INFO L226 Difference]: Without dead ends: 82 [2024-11-16 06:58:37,070 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2024-11-16 06:58:37,071 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 66 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 66 SdHoareTripleChecker+Valid, 167 SdHoareTripleChecker+Invalid, 98 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-11-16 06:58:37,071 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [66 Valid, 167 Invalid, 98 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2024-11-16 06:58:37,073 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2024-11-16 06:58:37,088 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 58. [2024-11-16 06:58:37,088 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 36 states have (on average 1.2777777777777777) internal successors, (46), 38 states have internal predecessors, (46), 18 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-16 06:58:37,092 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 80 transitions. [2024-11-16 06:58:37,092 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 80 transitions. Word has length 16 [2024-11-16 06:58:37,092 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 06:58:37,092 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 80 transitions. [2024-11-16 06:58:37,092 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.0) internal successors, (24), 7 states have internal predecessors, (24), 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-11-16 06:58:37,093 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 80 transitions. [2024-11-16 06:58:37,094 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-16 06:58:37,094 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 06:58:37,094 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 06:58:37,108 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-16 06:58:37,294 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 06:58:37,296 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 06:58:37,297 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 06:58:37,297 INFO L85 PathProgramCache]: Analyzing trace with hash -1499922286, now seen corresponding path program 1 times [2024-11-16 06:58:37,298 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 06:58:37,298 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1845996703] [2024-11-16 06:58:37,298 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:58:37,298 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 06:58:37,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:58:37,347 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:58:37,347 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 06:58:37,347 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1845996703] [2024-11-16 06:58:37,348 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1845996703] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 06:58:37,348 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [981868514] [2024-11-16 06:58:37,348 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:58:37,348 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 06:58:37,348 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 06:58:37,350 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 06:58:37,351 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-16 06:58:37,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:58:37,386 INFO L255 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-16 06:58:37,387 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 06:58:37,405 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:58:37,406 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 06:58:37,452 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:58:37,453 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [981868514] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 06:58:37,453 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 06:58:37,453 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 9 [2024-11-16 06:58:37,453 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [303098951] [2024-11-16 06:58:37,453 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 06:58:37,453 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-16 06:58:37,453 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 06:58:37,454 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-16 06:58:37,454 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-11-16 06:58:37,454 INFO L87 Difference]: Start difference. First operand 58 states and 80 transitions. Second operand has 10 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 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-11-16 06:58:41,571 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:58:45,593 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:58:49,742 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-16 06:58:50,600 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 06:58:50,600 INFO L93 Difference]: Finished difference Result 138 states and 194 transitions. [2024-11-16 06:58:50,600 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-16 06:58:50,601 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 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 17 [2024-11-16 06:58:50,601 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 06:58:50,605 INFO L225 Difference]: With dead ends: 138 [2024-11-16 06:58:50,605 INFO L226 Difference]: Without dead ends: 128 [2024-11-16 06:58:50,606 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2024-11-16 06:58:50,606 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 134 mSDsluCounter, 202 mSDsCounter, 0 mSdLazyCounter, 116 mSolverCounterSat, 41 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 13.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 246 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 116 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 13.1s IncrementalHoareTripleChecker+Time [2024-11-16 06:58:50,607 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 246 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 116 Invalid, 3 Unknown, 0 Unchecked, 13.1s Time] [2024-11-16 06:58:50,607 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2024-11-16 06:58:50,618 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 115. [2024-11-16 06:58:50,619 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 63 states have (on average 1.3492063492063493) internal successors, (85), 68 states have internal predecessors, (85), 45 states have call successors, (45), 6 states have call predecessors, (45), 6 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2024-11-16 06:58:50,620 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 170 transitions. [2024-11-16 06:58:50,620 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 170 transitions. Word has length 17 [2024-11-16 06:58:50,620 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 06:58:50,620 INFO L471 AbstractCegarLoop]: Abstraction has 115 states and 170 transitions. [2024-11-16 06:58:50,621 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.8) internal successors, (28), 9 states have internal predecessors, (28), 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-11-16 06:58:50,621 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 170 transitions. [2024-11-16 06:58:50,621 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-16 06:58:50,621 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 06:58:50,621 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 06:58:50,633 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-16 06:58:50,825 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,SelfDestructingSolverStorable5 [2024-11-16 06:58:50,826 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 06:58:50,826 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 06:58:50,827 INFO L85 PathProgramCache]: Analyzing trace with hash -1460210883, now seen corresponding path program 1 times [2024-11-16 06:58:50,827 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 06:58:50,827 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1557601292] [2024-11-16 06:58:50,827 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:58:50,827 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 06:58:50,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:58:51,004 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-16 06:58:51,004 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 06:58:51,004 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1557601292] [2024-11-16 06:58:51,004 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1557601292] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 06:58:51,004 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 06:58:51,004 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-16 06:58:51,004 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [325504821] [2024-11-16 06:58:51,004 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 06:58:51,005 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-16 06:58:51,005 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 06:58:51,005 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-16 06:58:51,005 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-16 06:58:51,005 INFO L87 Difference]: Start difference. First operand 115 states and 170 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 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-11-16 06:58:52,625 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.56s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:58:56,643 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:58:57,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 06:58:57,311 INFO L93 Difference]: Finished difference Result 207 states and 316 transitions. [2024-11-16 06:58:57,311 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-16 06:58:57,311 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 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 17 [2024-11-16 06:58:57,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 06:58:57,313 INFO L225 Difference]: With dead ends: 207 [2024-11-16 06:58:57,313 INFO L226 Difference]: Without dead ends: 204 [2024-11-16 06:58:57,313 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-16 06:58:57,314 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 14 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 61 mSolverCounterSat, 16 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 150 SdHoareTripleChecker+Invalid, 78 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 61 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.3s IncrementalHoareTripleChecker+Time [2024-11-16 06:58:57,314 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 150 Invalid, 78 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 61 Invalid, 1 Unknown, 0 Unchecked, 6.3s Time] [2024-11-16 06:58:57,315 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 204 states. [2024-11-16 06:58:57,335 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 204 to 142. [2024-11-16 06:58:57,335 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 83 states have (on average 1.2771084337349397) internal successors, (106), 91 states have internal predecessors, (106), 48 states have call successors, (48), 10 states have call predecessors, (48), 10 states have return successors, (43), 40 states have call predecessors, (43), 43 states have call successors, (43) [2024-11-16 06:58:57,336 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 197 transitions. [2024-11-16 06:58:57,337 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 197 transitions. Word has length 17 [2024-11-16 06:58:57,337 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 06:58:57,337 INFO L471 AbstractCegarLoop]: Abstraction has 142 states and 197 transitions. [2024-11-16 06:58:57,337 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 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-11-16 06:58:57,337 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 197 transitions. [2024-11-16 06:58:57,337 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-16 06:58:57,338 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 06:58:57,338 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 06:58:57,338 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-11-16 06:58:57,338 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 06:58:57,338 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 06:58:57,338 INFO L85 PathProgramCache]: Analyzing trace with hash 752431267, now seen corresponding path program 1 times [2024-11-16 06:58:57,338 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 06:58:57,339 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1840160776] [2024-11-16 06:58:57,339 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:58:57,339 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 06:58:57,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 06:58:57,347 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [95856636] [2024-11-16 06:58:57,347 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:58:57,348 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 06:58:57,348 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 06:58:57,349 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 06:58:57,359 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-16 06:58:57,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:58:57,393 INFO L255 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-16 06:58:57,394 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 06:58:57,477 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:58:57,477 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 06:58:57,477 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 06:58:57,478 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1840160776] [2024-11-16 06:58:57,478 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 06:58:57,478 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [95856636] [2024-11-16 06:58:57,478 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [95856636] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 06:58:57,478 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 06:58:57,479 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-16 06:58:57,479 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [369610026] [2024-11-16 06:58:57,479 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 06:58:57,479 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-16 06:58:57,479 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 06:58:57,480 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-16 06:58:57,480 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-16 06:58:57,480 INFO L87 Difference]: Start difference. First operand 142 states and 197 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 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-11-16 06:59:01,558 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:01,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 06:59:01,684 INFO L93 Difference]: Finished difference Result 149 states and 203 transitions. [2024-11-16 06:59:01,684 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-16 06:59:01,684 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 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 19 [2024-11-16 06:59:01,684 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 06:59:01,686 INFO L225 Difference]: With dead ends: 149 [2024-11-16 06:59:01,687 INFO L226 Difference]: Without dead ends: 146 [2024-11-16 06:59:01,687 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2024-11-16 06:59:01,691 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 3 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 4 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 62 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.2s IncrementalHoareTripleChecker+Time [2024-11-16 06:59:01,691 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 136 Invalid, 62 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 57 Invalid, 1 Unknown, 0 Unchecked, 4.2s Time] [2024-11-16 06:59:01,692 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2024-11-16 06:59:01,719 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 146. [2024-11-16 06:59:01,720 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 146 states, 86 states have (on average 1.2674418604651163) internal successors, (109), 94 states have internal predecessors, (109), 48 states have call successors, (48), 11 states have call predecessors, (48), 11 states have return successors, (43), 40 states have call predecessors, (43), 43 states have call successors, (43) [2024-11-16 06:59:01,721 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 200 transitions. [2024-11-16 06:59:01,724 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 200 transitions. Word has length 19 [2024-11-16 06:59:01,724 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 06:59:01,724 INFO L471 AbstractCegarLoop]: Abstraction has 146 states and 200 transitions. [2024-11-16 06:59:01,724 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 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-11-16 06:59:01,724 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 200 transitions. [2024-11-16 06:59:01,725 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-11-16 06:59:01,725 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 06:59:01,725 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 06:59:01,750 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-16 06:59:01,925 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 06:59:01,926 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 06:59:01,926 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 06:59:01,926 INFO L85 PathProgramCache]: Analyzing trace with hash -126840539, now seen corresponding path program 1 times [2024-11-16 06:59:01,926 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 06:59:01,926 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1456491134] [2024-11-16 06:59:01,926 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:59:01,927 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 06:59:01,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 06:59:01,937 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1702042666] [2024-11-16 06:59:01,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:59:01,937 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 06:59:01,937 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 06:59:01,938 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 06:59:01,939 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-16 06:59:02,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:59:02,013 INFO L255 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-16 06:59:02,015 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 06:59:02,108 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:59:02,109 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 06:59:02,982 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:59:02,982 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 06:59:02,982 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1456491134] [2024-11-16 06:59:02,982 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 06:59:02,982 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1702042666] [2024-11-16 06:59:02,983 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1702042666] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 06:59:02,983 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 06:59:02,983 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2024-11-16 06:59:02,983 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1151073933] [2024-11-16 06:59:02,983 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 06:59:02,983 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-16 06:59:02,983 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 06:59:02,984 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-16 06:59:02,984 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-16 06:59:02,984 INFO L87 Difference]: Start difference. First operand 146 states and 200 transitions. Second operand has 8 states, 8 states have (on average 3.5) internal successors, (28), 7 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-16 06:59:08,858 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:10,199 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.27s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:14,204 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:15,988 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.78s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:17,167 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.16s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:23,098 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:27,116 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:31,121 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:35,140 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:39,161 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:40,710 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.49s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:45,811 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:50,057 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:54,079 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 06:59:55,209 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 06:59:55,209 INFO L93 Difference]: Finished difference Result 226 states and 322 transitions. [2024-11-16 06:59:55,210 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-16 06:59:55,210 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.5) internal successors, (28), 7 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2024-11-16 06:59:55,210 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 06:59:55,212 INFO L225 Difference]: With dead ends: 226 [2024-11-16 06:59:55,216 INFO L226 Difference]: Without dead ends: 179 [2024-11-16 06:59:55,217 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 34 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=27, Invalid=63, Unknown=0, NotChecked=0, Total=90 [2024-11-16 06:59:55,217 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 15 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 117 mSolverCounterSat, 52 mSolverCounterUnsat, 10 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 50.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 202 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 117 IncrementalHoareTripleChecker+Invalid, 10 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 50.4s IncrementalHoareTripleChecker+Time [2024-11-16 06:59:55,217 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 202 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 117 Invalid, 10 Unknown, 0 Unchecked, 50.4s Time] [2024-11-16 06:59:55,218 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 179 states. [2024-11-16 06:59:55,276 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 179 to 174. [2024-11-16 06:59:55,279 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 174 states, 98 states have (on average 1.2244897959183674) internal successors, (120), 105 states have internal predecessors, (120), 61 states have call successors, (61), 14 states have call predecessors, (61), 14 states have return successors, (57), 54 states have call predecessors, (57), 57 states have call successors, (57) [2024-11-16 06:59:55,280 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 174 states to 174 states and 238 transitions. [2024-11-16 06:59:55,281 INFO L78 Accepts]: Start accepts. Automaton has 174 states and 238 transitions. Word has length 22 [2024-11-16 06:59:55,281 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 06:59:55,281 INFO L471 AbstractCegarLoop]: Abstraction has 174 states and 238 transitions. [2024-11-16 06:59:55,281 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.5) internal successors, (28), 7 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-16 06:59:55,281 INFO L276 IsEmpty]: Start isEmpty. Operand 174 states and 238 transitions. [2024-11-16 06:59:55,282 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-16 06:59:55,282 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 06:59:55,282 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 06:59:55,294 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-16 06:59:55,482 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 06:59:55,482 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 06:59:55,483 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 06:59:55,483 INFO L85 PathProgramCache]: Analyzing trace with hash 1408557887, now seen corresponding path program 1 times [2024-11-16 06:59:55,483 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 06:59:55,483 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [539244076] [2024-11-16 06:59:55,483 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:59:55,483 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 06:59:55,491 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 06:59:55,491 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2101337121] [2024-11-16 06:59:55,491 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:59:55,492 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 06:59:55,492 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 06:59:55,493 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 06:59:55,494 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-16 06:59:55,530 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:59:55,530 INFO L255 TraceCheckSpWp]: Trace formula consists of 75 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-16 06:59:55,531 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 06:59:55,582 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-16 06:59:55,582 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 06:59:55,582 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 06:59:55,582 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [539244076] [2024-11-16 06:59:55,582 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 06:59:55,582 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2101337121] [2024-11-16 06:59:55,582 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2101337121] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 06:59:55,582 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 06:59:55,583 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 06:59:55,583 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [742922421] [2024-11-16 06:59:55,583 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 06:59:55,583 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 06:59:55,583 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 06:59:55,583 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 06:59:55,583 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 06:59:55,583 INFO L87 Difference]: Start difference. First operand 174 states and 238 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-16 06:59:55,677 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 06:59:55,677 INFO L93 Difference]: Finished difference Result 223 states and 300 transitions. [2024-11-16 06:59:55,678 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 06:59:55,678 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2024-11-16 06:59:55,678 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 06:59:55,679 INFO L225 Difference]: With dead ends: 223 [2024-11-16 06:59:55,679 INFO L226 Difference]: Without dead ends: 214 [2024-11-16 06:59:55,680 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 20 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-11-16 06:59:55,680 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 7 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 06:59:55,680 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 124 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 06:59:55,681 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 214 states. [2024-11-16 06:59:55,702 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 214 to 214. [2024-11-16 06:59:55,702 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 214 states, 122 states have (on average 1.1967213114754098) internal successors, (146), 129 states have internal predecessors, (146), 72 states have call successors, (72), 20 states have call predecessors, (72), 19 states have return successors, (65), 64 states have call predecessors, (65), 65 states have call successors, (65) [2024-11-16 06:59:55,703 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 214 states to 214 states and 283 transitions. [2024-11-16 06:59:55,703 INFO L78 Accepts]: Start accepts. Automaton has 214 states and 283 transitions. Word has length 24 [2024-11-16 06:59:55,704 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 06:59:55,704 INFO L471 AbstractCegarLoop]: Abstraction has 214 states and 283 transitions. [2024-11-16 06:59:55,704 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-16 06:59:55,704 INFO L276 IsEmpty]: Start isEmpty. Operand 214 states and 283 transitions. [2024-11-16 06:59:55,704 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-16 06:59:55,705 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 06:59:55,705 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 06:59:55,717 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-16 06:59:55,905 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-16 06:59:55,906 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 06:59:55,906 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 06:59:55,906 INFO L85 PathProgramCache]: Analyzing trace with hash 1709334525, now seen corresponding path program 1 times [2024-11-16 06:59:55,906 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 06:59:55,906 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [54663185] [2024-11-16 06:59:55,906 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:59:55,907 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 06:59:55,916 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:59:55,977 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:59:55,977 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 06:59:55,977 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [54663185] [2024-11-16 06:59:55,977 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [54663185] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 06:59:55,977 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1153239497] [2024-11-16 06:59:55,978 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 06:59:55,978 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 06:59:55,978 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 06:59:55,979 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 06:59:55,980 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-16 06:59:56,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 06:59:56,012 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-16 06:59:56,013 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 06:59:56,037 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:59:56,037 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 06:59:56,125 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 06:59:56,125 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1153239497] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 06:59:56,125 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 06:59:56,125 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 13 [2024-11-16 06:59:56,125 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2096560392] [2024-11-16 06:59:56,125 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 06:59:56,126 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-16 06:59:56,126 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 06:59:56,126 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-16 06:59:56,126 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2024-11-16 06:59:56,126 INFO L87 Difference]: Start difference. First operand 214 states and 283 transitions. Second operand has 14 states, 14 states have (on average 3.0) internal successors, (42), 13 states have internal predecessors, (42), 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-11-16 06:59:58,545 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.19s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-16 07:00:02,678 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-16 07:00:06,721 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 07:00:07,143 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:00:07,143 INFO L93 Difference]: Finished difference Result 426 states and 585 transitions. [2024-11-16 07:00:07,144 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-16 07:00:07,144 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.0) internal successors, (42), 13 states have internal predecessors, (42), 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 25 [2024-11-16 07:00:07,144 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:00:07,146 INFO L225 Difference]: With dead ends: 426 [2024-11-16 07:00:07,146 INFO L226 Difference]: Without dead ends: 389 [2024-11-16 07:00:07,147 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2024-11-16 07:00:07,147 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 304 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 196 mSolverCounterSat, 122 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 304 SdHoareTripleChecker+Valid, 297 SdHoareTripleChecker+Invalid, 320 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 122 IncrementalHoareTripleChecker+Valid, 196 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.9s IncrementalHoareTripleChecker+Time [2024-11-16 07:00:07,147 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [304 Valid, 297 Invalid, 320 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [122 Valid, 196 Invalid, 2 Unknown, 0 Unchecked, 10.9s Time] [2024-11-16 07:00:07,148 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 389 states. [2024-11-16 07:00:07,175 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 389 to 365. [2024-11-16 07:00:07,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 365 states, 193 states have (on average 1.2487046632124352) internal successors, (241), 208 states have internal predecessors, (241), 140 states have call successors, (140), 32 states have call predecessors, (140), 31 states have return successors, (125), 124 states have call predecessors, (125), 125 states have call successors, (125) [2024-11-16 07:00:07,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 365 states to 365 states and 506 transitions. [2024-11-16 07:00:07,178 INFO L78 Accepts]: Start accepts. Automaton has 365 states and 506 transitions. Word has length 25 [2024-11-16 07:00:07,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:00:07,178 INFO L471 AbstractCegarLoop]: Abstraction has 365 states and 506 transitions. [2024-11-16 07:00:07,178 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.0) internal successors, (42), 13 states have internal predecessors, (42), 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-11-16 07:00:07,178 INFO L276 IsEmpty]: Start isEmpty. Operand 365 states and 506 transitions. [2024-11-16 07:00:07,179 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-16 07:00:07,179 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:00:07,179 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:00:07,199 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-16 07:00:07,379 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:00:07,380 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:00:07,380 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:00:07,380 INFO L85 PathProgramCache]: Analyzing trace with hash -1261317597, now seen corresponding path program 2 times [2024-11-16 07:00:07,380 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:00:07,380 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1238363195] [2024-11-16 07:00:07,381 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:00:07,381 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:00:07,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:00:07,406 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [92770128] [2024-11-16 07:00:07,410 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 07:00:07,410 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:00:07,410 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:00:07,411 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:00:07,416 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-16 07:00:07,499 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 07:00:07,499 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:00:07,500 INFO L255 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-16 07:00:07,501 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:00:07,666 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 2 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 07:00:07,666 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:00:12,441 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 2 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 07:00:12,442 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:00:12,442 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1238363195] [2024-11-16 07:00:12,442 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:00:12,442 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [92770128] [2024-11-16 07:00:12,442 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [92770128] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:00:12,442 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:00:12,442 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2024-11-16 07:00:12,442 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [894829947] [2024-11-16 07:00:12,442 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:00:12,443 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-16 07:00:12,443 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:00:12,443 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-16 07:00:12,443 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=132, Unknown=0, NotChecked=0, Total=182 [2024-11-16 07:00:12,444 INFO L87 Difference]: Start difference. First operand 365 states and 506 transitions. Second operand has 14 states, 14 states have (on average 3.2857142857142856) internal successors, (46), 13 states have internal predecessors, (46), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-16 07:00:21,283 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.13s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers []