./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 023d838f 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/hard-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 aa72233183b4e91144bd6a6eb8a8b140b7f90e590c3e855f829f337fec510ab9 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-09 22:44:34,418 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 22:44:34,474 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-09 22:44:34,478 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 22:44:34,478 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 22:44:34,497 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 22:44:34,497 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 22:44:34,497 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 22:44:34,498 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 22:44:34,500 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 22:44:34,501 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 22:44:34,501 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 22:44:34,501 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 22:44:34,501 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 22:44:34,501 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 22:44:34,502 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 22:44:34,502 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 22:44:34,502 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 22:44:34,502 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 22:44:34,502 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 22:44:34,502 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 22:44:34,503 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 22:44:34,503 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 22:44:34,503 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 22:44:34,503 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 22:44:34,503 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 22:44:34,504 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 22:44:34,504 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 22:44:34,504 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-09 22:44:34,504 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 22:44:34,504 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 22:44:34,504 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 22:44:34,505 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:44:34,505 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 22:44:34,505 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 22:44:34,505 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 22:44:34,505 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 22:44:34,505 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 22:44:34,505 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 22:44:34,505 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-09 22:44:34,505 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-09 22:44:34,506 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 22:44:34,506 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 -> aa72233183b4e91144bd6a6eb8a8b140b7f90e590c3e855f829f337fec510ab9 [2024-11-09 22:44:34,700 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 22:44:34,722 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 22:44:34,724 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 22:44:34,725 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 22:44:34,725 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 22:44:34,726 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound100.c [2024-11-09 22:44:35,895 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 22:44:36,045 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 22:44:36,045 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard-u_unwindbound100.c [2024-11-09 22:44:36,054 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/47afb66be/ed1ee02a972d451cba198dd1275883a7/FLAG9bcad68b4 [2024-11-09 22:44:36,455 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/47afb66be/ed1ee02a972d451cba198dd1275883a7 [2024-11-09 22:44:36,457 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 22:44:36,458 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 22:44:36,459 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 22:44:36,459 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 22:44:36,463 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 22:44:36,464 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,464 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@aa355ed and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36, skipping insertion in model container [2024-11-09 22:44:36,464 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,481 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 22:44:36,610 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/hard-u_unwindbound100.c[537,550] [2024-11-09 22:44:36,630 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:44:36,637 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 22:44:36,647 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/hard-u_unwindbound100.c[537,550] [2024-11-09 22:44:36,653 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:44:36,669 INFO L204 MainTranslator]: Completed translation [2024-11-09 22:44:36,670 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36 WrapperNode [2024-11-09 22:44:36,670 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 22:44:36,670 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 22:44:36,671 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 22:44:36,671 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 22:44:36,676 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,682 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,696 INFO L138 Inliner]: procedures = 14, calls = 15, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 64 [2024-11-09 22:44:36,697 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 22:44:36,698 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 22:44:36,698 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 22:44:36,698 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 22:44:36,706 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,706 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,711 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,722 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-09 22:44:36,725 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,725 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,728 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,732 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,733 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,733 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,735 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 22:44:36,735 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-09 22:44:36,735 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-09 22:44:36,736 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-09 22:44:36,737 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36" (1/1) ... [2024-11-09 22:44:36,745 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:44:36,753 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:44:36,766 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-09 22:44:36,768 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-09 22:44:36,803 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 22:44:36,803 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 22:44:36,803 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 22:44:36,803 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 22:44:36,804 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 22:44:36,804 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 22:44:36,860 INFO L256 CfgBuilder]: Building ICFG [2024-11-09 22:44:36,862 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 22:44:37,013 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-09 22:44:37,014 INFO L307 CfgBuilder]: Performing block encoding [2024-11-09 22:44:37,024 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 22:44:37,024 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 22:44:37,025 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:44:37 BoogieIcfgContainer [2024-11-09 22:44:37,025 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-09 22:44:37,027 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 22:44:37,027 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 22:44:37,029 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 22:44:37,029 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 10:44:36" (1/3) ... [2024-11-09 22:44:37,030 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@35e0d898 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:44:37, skipping insertion in model container [2024-11-09 22:44:37,031 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:44:36" (2/3) ... [2024-11-09 22:44:37,031 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@35e0d898 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:44:37, skipping insertion in model container [2024-11-09 22:44:37,032 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:44:37" (3/3) ... [2024-11-09 22:44:37,033 INFO L112 eAbstractionObserver]: Analyzing ICFG hard-u_unwindbound100.c [2024-11-09 22:44:37,047 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 22:44:37,047 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 22:44:37,083 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 22:44:37,088 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;@2b4db429, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 22:44:37,089 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 22:44:37,091 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-09 22:44:37,097 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-09 22:44:37,097 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:44:37,097 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:44:37,098 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:44:37,101 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:44:37,101 INFO L85 PathProgramCache]: Analyzing trace with hash -292126860, now seen corresponding path program 1 times [2024-11-09 22:44:37,112 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:44:37,112 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1761618266] [2024-11-09 22:44:37,112 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:37,113 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:44:37,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:37,213 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-09 22:44:37,214 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:44:37,214 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1761618266] [2024-11-09 22:44:37,214 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1761618266] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:44:37,215 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:44:37,215 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 22:44:37,216 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1036364771] [2024-11-09 22:44:37,216 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:44:37,219 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-09 22:44:37,219 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:44:37,233 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-09 22:44:37,234 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 22:44:37,235 INFO L87 Difference]: Start difference. First operand has 29 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) 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-09 22:44:37,252 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:44:37,253 INFO L93 Difference]: Finished difference Result 55 states and 89 transitions. [2024-11-09 22:44:37,253 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 22:44:37,254 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-09 22:44:37,254 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:44:37,259 INFO L225 Difference]: With dead ends: 55 [2024-11-09 22:44:37,259 INFO L226 Difference]: Without dead ends: 25 [2024-11-09 22:44:37,262 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-09 22:44:37,266 INFO L432 NwaCegarLoop]: 39 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, 39 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-09 22:44:37,267 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:44:37,278 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2024-11-09 22:44:37,288 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2024-11-09 22:44:37,289 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 22:44:37,290 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 35 transitions. [2024-11-09 22:44:37,291 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 35 transitions. Word has length 11 [2024-11-09 22:44:37,291 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:44:37,291 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 35 transitions. [2024-11-09 22:44:37,292 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-09 22:44:37,292 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 35 transitions. [2024-11-09 22:44:37,293 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-09 22:44:37,293 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:44:37,293 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:44:37,293 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 22:44:37,293 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:44:37,294 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:44:37,294 INFO L85 PathProgramCache]: Analyzing trace with hash -2099581323, now seen corresponding path program 1 times [2024-11-09 22:44:37,294 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:44:37,294 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1133914082] [2024-11-09 22:44:37,294 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:37,294 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:44:37,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:37,469 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-09 22:44:37,469 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:44:37,470 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1133914082] [2024-11-09 22:44:37,470 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1133914082] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:44:37,470 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:44:37,470 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:44:37,470 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2043174879] [2024-11-09 22:44:37,470 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:44:37,471 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:44:37,471 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:44:37,472 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:44:37,472 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:44:37,472 INFO L87 Difference]: Start difference. First operand 25 states and 35 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 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-09 22:44:37,539 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:44:37,540 INFO L93 Difference]: Finished difference Result 40 states and 55 transitions. [2024-11-09 22:44:37,541 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:44:37,542 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 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-09 22:44:37,542 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:44:37,542 INFO L225 Difference]: With dead ends: 40 [2024-11-09 22:44:37,542 INFO L226 Difference]: Without dead ends: 37 [2024-11-09 22:44:37,557 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 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-09 22:44:37,563 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 12 mSDsluCounter, 77 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:44:37,564 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 108 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:44:37,564 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2024-11-09 22:44:37,576 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 29. [2024-11-09 22:44:37,576 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 22:44:37,577 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 38 transitions. [2024-11-09 22:44:37,577 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 38 transitions. Word has length 11 [2024-11-09 22:44:37,577 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:44:37,578 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 38 transitions. [2024-11-09 22:44:37,578 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 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-09 22:44:37,578 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 38 transitions. [2024-11-09 22:44:37,578 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-09 22:44:37,578 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:44:37,578 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:44:37,579 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-09 22:44:37,579 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:44:37,579 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:44:37,579 INFO L85 PathProgramCache]: Analyzing trace with hash -909958482, now seen corresponding path program 1 times [2024-11-09 22:44:37,580 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:44:37,580 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1204387235] [2024-11-09 22:44:37,580 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:37,580 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:44:37,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:37,624 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-09 22:44:37,624 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:44:37,624 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1204387235] [2024-11-09 22:44:37,624 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1204387235] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:44:37,624 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:44:37,624 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-09 22:44:37,625 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [903643906] [2024-11-09 22:44:37,625 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:44:37,625 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-09 22:44:37,625 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:44:37,629 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-09 22:44:37,629 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-09 22:44:37,629 INFO L87 Difference]: Start difference. First operand 29 states and 38 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-09 22:44:37,647 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:44:37,648 INFO L93 Difference]: Finished difference Result 46 states and 61 transitions. [2024-11-09 22:44:37,648 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-09 22:44:37,649 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-09 22:44:37,649 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:44:37,649 INFO L225 Difference]: With dead ends: 46 [2024-11-09 22:44:37,649 INFO L226 Difference]: Without dead ends: 31 [2024-11-09 22:44:37,650 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-09 22:44:37,650 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 0 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 92 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-09 22:44:37,651 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 92 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:44:37,651 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-09 22:44:37,656 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2024-11-09 22:44:37,657 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 22:44:37,658 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 40 transitions. [2024-11-09 22:44:37,658 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 40 transitions. Word has length 13 [2024-11-09 22:44:37,658 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:44:37,658 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 40 transitions. [2024-11-09 22:44:37,658 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-09 22:44:37,659 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 40 transitions. [2024-11-09 22:44:37,659 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-09 22:44:37,659 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:44:37,659 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:44:37,659 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-09 22:44:37,659 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:44:37,660 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:44:37,660 INFO L85 PathProgramCache]: Analyzing trace with hash 2100820203, now seen corresponding path program 1 times [2024-11-09 22:44:37,660 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:44:37,660 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1362779606] [2024-11-09 22:44:37,660 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:37,660 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:44:37,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:37,822 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 22:44:37,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:37,832 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-09 22:44:37,833 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:44:37,833 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1362779606] [2024-11-09 22:44:37,833 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1362779606] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:44:37,833 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:44:37,833 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:44:37,833 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [666448157] [2024-11-09 22:44:37,833 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:44:37,834 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:44:37,834 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:44:37,835 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:44:37,836 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:44:37,836 INFO L87 Difference]: Start difference. First operand 31 states and 40 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, (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-09 22:44:37,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:44:37,925 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2024-11-09 22:44:37,925 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:44:37,926 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, (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 16 [2024-11-09 22:44:37,926 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:44:37,927 INFO L225 Difference]: With dead ends: 46 [2024-11-09 22:44:37,928 INFO L226 Difference]: Without dead ends: 43 [2024-11-09 22:44:37,928 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 4 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-09 22:44:37,929 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 12 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:44:37,929 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 105 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:44:37,930 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-09 22:44:37,935 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 35. [2024-11-09 22:44:37,939 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 24 states have (on average 1.25) internal successors, (30), 25 states have internal predecessors, (30), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-09 22:44:37,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 43 transitions. [2024-11-09 22:44:37,940 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 43 transitions. Word has length 16 [2024-11-09 22:44:37,940 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:44:37,940 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 43 transitions. [2024-11-09 22:44:37,940 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, (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-09 22:44:37,940 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 43 transitions. [2024-11-09 22:44:37,941 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-09 22:44:37,942 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:44:37,943 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:44:37,943 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-09 22:44:37,943 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:44:37,943 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:44:37,943 INFO L85 PathProgramCache]: Analyzing trace with hash 1262954485, now seen corresponding path program 1 times [2024-11-09 22:44:37,944 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:44:37,944 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1096531462] [2024-11-09 22:44:37,944 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:37,944 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:44:37,957 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:44:37,959 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [642134879] [2024-11-09 22:44:37,960 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:37,961 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:44:37,961 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:44:37,963 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-09 22:44:37,964 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-09 22:44:38,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:38,007 INFO L255 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-09 22:44:38,011 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:44:38,153 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-09 22:44:38,153 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:44:38,154 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:44:38,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1096531462] [2024-11-09 22:44:38,154 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:44:38,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [642134879] [2024-11-09 22:44:38,155 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [642134879] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:44:38,155 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:44:38,155 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-11-09 22:44:38,157 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1485111241] [2024-11-09 22:44:38,157 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:44:38,157 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-09 22:44:38,158 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:44:38,158 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-09 22:44:38,159 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2024-11-09 22:44:38,159 INFO L87 Difference]: Start difference. First operand 35 states and 43 transitions. Second operand has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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-09 22:44:38,261 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:44:38,261 INFO L93 Difference]: Finished difference Result 65 states and 87 transitions. [2024-11-09 22:44:38,262 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-09 22:44:38,262 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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 21 [2024-11-09 22:44:38,263 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:44:38,263 INFO L225 Difference]: With dead ends: 65 [2024-11-09 22:44:38,263 INFO L226 Difference]: Without dead ends: 49 [2024-11-09 22:44:38,264 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-11-09 22:44:38,264 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 25 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:44:38,265 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 120 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:44:38,265 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-11-09 22:44:38,276 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2024-11-09 22:44:38,277 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-09 22:44:38,278 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 63 transitions. [2024-11-09 22:44:38,280 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 63 transitions. Word has length 21 [2024-11-09 22:44:38,280 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:44:38,280 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 63 transitions. [2024-11-09 22:44:38,280 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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-09 22:44:38,280 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 63 transitions. [2024-11-09 22:44:38,281 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-09 22:44:38,282 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:44:38,282 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:44:38,298 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-09 22:44:38,483 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-09 22:44:38,483 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:44:38,484 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:44:38,484 INFO L85 PathProgramCache]: Analyzing trace with hash -55756711, now seen corresponding path program 1 times [2024-11-09 22:44:38,484 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:44:38,487 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [628991833] [2024-11-09 22:44:38,487 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:38,487 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:44:38,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:38,563 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 22:44:38,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:38,570 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 22:44:38,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:38,592 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-09 22:44:38,595 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:38,599 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 22:44:38,599 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:44:38,600 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [628991833] [2024-11-09 22:44:38,600 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [628991833] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:44:38,600 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:44:38,602 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:44:38,603 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [206361749] [2024-11-09 22:44:38,603 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:44:38,603 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:44:38,603 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:44:38,603 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:44:38,604 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:44:38,604 INFO L87 Difference]: Start difference. First operand 49 states and 63 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-09 22:44:38,637 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:44:38,639 INFO L93 Difference]: Finished difference Result 69 states and 79 transitions. [2024-11-09 22:44:38,639 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:44:38,639 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 29 [2024-11-09 22:44:38,640 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:44:38,642 INFO L225 Difference]: With dead ends: 69 [2024-11-09 22:44:38,642 INFO L226 Difference]: Without dead ends: 61 [2024-11-09 22:44:38,642 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 7 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-09 22:44:38,643 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 7 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:44:38,645 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 112 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:44:38,645 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2024-11-09 22:44:38,655 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 60. [2024-11-09 22:44:38,657 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 40 states have (on average 1.175) internal successors, (47), 41 states have internal predecessors, (47), 12 states have call successors, (12), 7 states have call predecessors, (12), 7 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-09 22:44:38,658 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 70 transitions. [2024-11-09 22:44:38,659 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 70 transitions. Word has length 29 [2024-11-09 22:44:38,659 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:44:38,659 INFO L471 AbstractCegarLoop]: Abstraction has 60 states and 70 transitions. [2024-11-09 22:44:38,660 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-09 22:44:38,660 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 70 transitions. [2024-11-09 22:44:38,660 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-09 22:44:38,661 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:44:38,661 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:44:38,661 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-09 22:44:38,661 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:44:38,662 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:44:38,662 INFO L85 PathProgramCache]: Analyzing trace with hash -23433476, now seen corresponding path program 1 times [2024-11-09 22:44:38,662 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:44:38,662 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [292843377] [2024-11-09 22:44:38,662 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:38,662 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:44:38,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:44:38,678 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [395781454] [2024-11-09 22:44:38,679 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:38,679 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:44:38,679 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:44:38,680 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-09 22:44:38,682 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-09 22:44:38,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:38,730 INFO L255 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-09 22:44:38,732 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:44:38,926 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-09 22:44:38,927 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:44:39,321 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:44:39,321 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [292843377] [2024-11-09 22:44:39,321 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:44:39,321 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [395781454] [2024-11-09 22:44:39,322 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [395781454] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:44:39,322 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:44:39,322 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2024-11-09 22:44:39,322 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1710325852] [2024-11-09 22:44:39,322 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 22:44:39,322 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 22:44:39,322 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:44:39,323 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 22:44:39,323 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=121, Unknown=0, NotChecked=0, Total=156 [2024-11-09 22:44:39,324 INFO L87 Difference]: Start difference. First operand 60 states and 70 transitions. Second operand has 10 states, 9 states have (on average 2.111111111111111) internal successors, (19), 7 states have internal predecessors, (19), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 22:44:39,535 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:44:39,535 INFO L93 Difference]: Finished difference Result 69 states and 79 transitions. [2024-11-09 22:44:39,535 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 22:44:39,536 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.111111111111111) internal successors, (19), 7 states have internal predecessors, (19), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) Word has length 29 [2024-11-09 22:44:39,536 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:44:39,536 INFO L225 Difference]: With dead ends: 69 [2024-11-09 22:44:39,536 INFO L226 Difference]: Without dead ends: 51 [2024-11-09 22:44:39,537 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 24 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=67, Invalid=205, Unknown=0, NotChecked=0, Total=272 [2024-11-09 22:44:39,537 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 15 mSDsluCounter, 157 mSDsCounter, 0 mSdLazyCounter, 148 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 182 SdHoareTripleChecker+Invalid, 168 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 148 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:44:39,538 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 182 Invalid, 168 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 148 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:44:39,538 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2024-11-09 22:44:39,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2024-11-09 22:44:39,542 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 34 states have (on average 1.1764705882352942) internal successors, (40), 35 states have internal predecessors, (40), 10 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-09 22:44:39,543 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 59 transitions. [2024-11-09 22:44:39,543 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 59 transitions. Word has length 29 [2024-11-09 22:44:39,543 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:44:39,543 INFO L471 AbstractCegarLoop]: Abstraction has 51 states and 59 transitions. [2024-11-09 22:44:39,543 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.111111111111111) internal successors, (19), 7 states have internal predecessors, (19), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 22:44:39,544 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2024-11-09 22:44:39,544 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-09 22:44:39,544 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:44:39,544 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:44:39,557 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-09 22:44:39,748 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,SelfDestructingSolverStorable6 [2024-11-09 22:44:39,749 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:44:39,749 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:44:39,749 INFO L85 PathProgramCache]: Analyzing trace with hash 1329239513, now seen corresponding path program 1 times [2024-11-09 22:44:39,749 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:44:39,749 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1961556163] [2024-11-09 22:44:39,749 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:39,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:44:39,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:39,798 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 22:44:39,800 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:39,802 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 22:44:39,803 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:39,805 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-09 22:44:39,806 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:39,808 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 22:44:39,808 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:44:39,808 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1961556163] [2024-11-09 22:44:39,809 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1961556163] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:44:39,809 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1448212344] [2024-11-09 22:44:39,809 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:39,809 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:44:39,809 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:44:39,810 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-09 22:44:39,811 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-09 22:44:39,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:39,854 INFO L255 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-09 22:44:39,855 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:44:39,884 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 22:44:39,884 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:44:39,920 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 22:44:39,922 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1448212344] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:44:39,922 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 22:44:39,922 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 8 [2024-11-09 22:44:39,922 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [176103887] [2024-11-09 22:44:39,922 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 22:44:39,923 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-09 22:44:39,923 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:44:39,923 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-09 22:44:39,923 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2024-11-09 22:44:39,923 INFO L87 Difference]: Start difference. First operand 51 states and 59 transitions. Second operand has 8 states, 8 states have (on average 3.75) internal successors, (30), 8 states have internal predecessors, (30), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-09 22:44:40,005 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:44:40,005 INFO L93 Difference]: Finished difference Result 119 states and 143 transitions. [2024-11-09 22:44:40,005 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 22:44:40,005 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.75) internal successors, (30), 8 states have internal predecessors, (30), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 31 [2024-11-09 22:44:40,006 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:44:40,006 INFO L225 Difference]: With dead ends: 119 [2024-11-09 22:44:40,006 INFO L226 Difference]: Without dead ends: 104 [2024-11-09 22:44:40,007 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 64 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-09 22:44:40,007 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 38 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:44:40,007 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 121 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:44:40,008 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2024-11-09 22:44:40,017 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 96. [2024-11-09 22:44:40,019 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 63 states have (on average 1.1904761904761905) internal successors, (75), 65 states have internal predecessors, (75), 20 states have call successors, (20), 12 states have call predecessors, (20), 12 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2024-11-09 22:44:40,020 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 113 transitions. [2024-11-09 22:44:40,021 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 113 transitions. Word has length 31 [2024-11-09 22:44:40,021 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:44:40,022 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 113 transitions. [2024-11-09 22:44:40,022 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.75) internal successors, (30), 8 states have internal predecessors, (30), 3 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-09 22:44:40,022 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 113 transitions. [2024-11-09 22:44:40,022 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-09 22:44:40,023 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:44:40,024 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:44:40,039 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-09 22:44:40,227 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-09 22:44:40,228 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:44:40,229 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:44:40,229 INFO L85 PathProgramCache]: Analyzing trace with hash 253378592, now seen corresponding path program 1 times [2024-11-09 22:44:40,229 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:44:40,229 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1732963044] [2024-11-09 22:44:40,229 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:40,229 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:44:40,250 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:44:40,251 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [209132463] [2024-11-09 22:44:40,252 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:40,252 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:44:40,252 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:44:40,254 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-09 22:44:40,254 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-09 22:44:40,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:40,341 INFO L255 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 22:44:40,342 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:44:40,407 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-09 22:44:40,408 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:44:40,530 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-09 22:44:40,530 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:44:40,531 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1732963044] [2024-11-09 22:44:40,531 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:44:40,531 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [209132463] [2024-11-09 22:44:40,531 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [209132463] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-09 22:44:40,531 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:44:40,531 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 8 [2024-11-09 22:44:40,531 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1512181208] [2024-11-09 22:44:40,531 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:44:40,531 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-09 22:44:40,531 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:44:40,532 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 22:44:40,532 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2024-11-09 22:44:40,532 INFO L87 Difference]: Start difference. First operand 96 states and 113 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-09 22:44:42,078 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.45s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:44:46,390 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-09 22:44:50,399 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-09 22:44:50,413 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:44:50,413 INFO L93 Difference]: Finished difference Result 116 states and 138 transitions. [2024-11-09 22:44:50,413 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:44:50,413 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), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 39 [2024-11-09 22:44:50,413 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:44:50,414 INFO L225 Difference]: With dead ends: 116 [2024-11-09 22:44:50,414 INFO L226 Difference]: Without dead ends: 113 [2024-11-09 22:44:50,414 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 68 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2024-11-09 22:44:50,415 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 13 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 5 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 45 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.9s IncrementalHoareTripleChecker+Time [2024-11-09 22:44:50,415 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 100 Invalid, 45 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 38 Invalid, 2 Unknown, 0 Unchecked, 9.9s Time] [2024-11-09 22:44:50,415 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113 states. [2024-11-09 22:44:50,426 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113 to 108. [2024-11-09 22:44:50,427 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 71 states have (on average 1.1690140845070423) internal successors, (83), 74 states have internal predecessors, (83), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2024-11-09 22:44:50,427 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 125 transitions. [2024-11-09 22:44:50,428 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 125 transitions. Word has length 39 [2024-11-09 22:44:50,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:44:50,428 INFO L471 AbstractCegarLoop]: Abstraction has 108 states and 125 transitions. [2024-11-09 22:44:50,428 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), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-09 22:44:50,428 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 125 transitions. [2024-11-09 22:44:50,429 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-09 22:44:50,429 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:44:50,429 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:44:50,438 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-09 22:44:50,629 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-09 22:44:50,630 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:44:50,630 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:44:50,630 INFO L85 PathProgramCache]: Analyzing trace with hash -1889077884, now seen corresponding path program 1 times [2024-11-09 22:44:50,630 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:44:50,631 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1101605834] [2024-11-09 22:44:50,631 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:50,631 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:44:50,641 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:50,704 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-09 22:44:50,705 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:50,707 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 22:44:50,708 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:50,709 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-09 22:44:50,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:50,712 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-09 22:44:50,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:50,714 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-09 22:44:50,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:50,717 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-09 22:44:50,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:50,719 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-09 22:44:50,719 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:44:50,719 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1101605834] [2024-11-09 22:44:50,720 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1101605834] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:44:50,720 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1684890147] [2024-11-09 22:44:50,720 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:50,720 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:44:50,720 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:44:50,721 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-09 22:44:50,722 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-09 22:44:50,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:50,762 INFO L255 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 22:44:50,764 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:44:50,806 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 42 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-09 22:44:50,807 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:44:50,861 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-09 22:44:50,862 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1684890147] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:44:50,862 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 22:44:50,862 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2024-11-09 22:44:50,862 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [10888635] [2024-11-09 22:44:50,862 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 22:44:50,863 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 22:44:50,863 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:44:50,863 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 22:44:50,863 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-11-09 22:44:50,863 INFO L87 Difference]: Start difference. First operand 108 states and 125 transitions. Second operand has 10 states, 10 states have (on average 3.7) internal successors, (37), 10 states have internal predecessors, (37), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-09 22:44:50,994 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:44:50,995 INFO L93 Difference]: Finished difference Result 204 states and 243 transitions. [2024-11-09 22:44:50,995 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-09 22:44:50,995 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.7) internal successors, (37), 10 states have internal predecessors, (37), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) Word has length 47 [2024-11-09 22:44:50,995 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:44:50,997 INFO L225 Difference]: With dead ends: 204 [2024-11-09 22:44:50,997 INFO L226 Difference]: Without dead ends: 189 [2024-11-09 22:44:50,998 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=52, Invalid=104, Unknown=0, NotChecked=0, Total=156 [2024-11-09 22:44:50,998 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 85 mSDsluCounter, 120 mSDsCounter, 0 mSdLazyCounter, 83 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 85 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 98 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 83 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:44:50,998 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [85 Valid, 152 Invalid, 98 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 83 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:44:51,002 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2024-11-09 22:44:51,023 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 179. [2024-11-09 22:44:51,024 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 179 states, 116 states have (on average 1.1810344827586208) internal successors, (137), 123 states have internal predecessors, (137), 40 states have call successors, (40), 22 states have call predecessors, (40), 22 states have return successors, (36), 33 states have call predecessors, (36), 36 states have call successors, (36) [2024-11-09 22:44:51,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 179 states to 179 states and 213 transitions. [2024-11-09 22:44:51,027 INFO L78 Accepts]: Start accepts. Automaton has 179 states and 213 transitions. Word has length 47 [2024-11-09 22:44:51,028 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:44:51,028 INFO L471 AbstractCegarLoop]: Abstraction has 179 states and 213 transitions. [2024-11-09 22:44:51,028 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.7) internal successors, (37), 10 states have internal predecessors, (37), 5 states have call successors, (19), 4 states have call predecessors, (19), 3 states have return successors, (18), 4 states have call predecessors, (18), 4 states have call successors, (18) [2024-11-09 22:44:51,028 INFO L276 IsEmpty]: Start isEmpty. Operand 179 states and 213 transitions. [2024-11-09 22:44:51,029 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-09 22:44:51,030 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:44:51,030 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:44:51,044 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-09 22:44:51,235 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-09 22:44:51,236 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:44:51,236 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:44:51,236 INFO L85 PathProgramCache]: Analyzing trace with hash -1856754649, now seen corresponding path program 1 times [2024-11-09 22:44:51,237 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:44:51,237 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [174016824] [2024-11-09 22:44:51,237 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:51,237 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:44:51,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:44:51,256 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1576154317] [2024-11-09 22:44:51,256 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:44:51,256 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:44:51,256 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:44:51,257 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-09 22:44:51,258 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-09 22:44:51,304 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:44:51,310 INFO L255 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-09 22:44:51,312 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:44:59,865 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 24 proven. 21 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2024-11-09 22:44:59,866 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:45:00,998 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:45:00,998 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [174016824] [2024-11-09 22:45:00,998 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:45:00,998 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1576154317] [2024-11-09 22:45:00,998 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1576154317] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:45:00,998 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:45:00,998 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2024-11-09 22:45:00,999 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2142968134] [2024-11-09 22:45:00,999 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 22:45:00,999 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-09 22:45:00,999 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:45:00,999 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-09 22:45:00,999 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2024-11-09 22:45:00,999 INFO L87 Difference]: Start difference. First operand 179 states and 213 transitions. Second operand has 13 states, 13 states have (on average 1.6923076923076923) internal successors, (22), 10 states have internal predecessors, (22), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 4 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-09 22:45:10,396 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 [0] [2024-11-09 22:45:15,727 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 [0] [2024-11-09 22:45:16,011 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:45:16,011 INFO L93 Difference]: Finished difference Result 242 states and 302 transitions. [2024-11-09 22:45:16,012 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-09 22:45:16,012 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.6923076923076923) internal successors, (22), 10 states have internal predecessors, (22), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 4 states have call predecessors, (6), 2 states have call successors, (6) Word has length 47 [2024-11-09 22:45:16,012 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:45:16,014 INFO L225 Difference]: With dead ends: 242 [2024-11-09 22:45:16,014 INFO L226 Difference]: Without dead ends: 237 [2024-11-09 22:45:16,014 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 39 SyntacticMatches, 2 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 13.5s TimeCoverageRelationStatistics Valid=77, Invalid=265, Unknown=0, NotChecked=0, Total=342 [2024-11-09 22:45:16,015 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 36 mSDsluCounter, 212 mSDsCounter, 0 mSdLazyCounter, 220 mSolverCounterSat, 24 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 238 SdHoareTripleChecker+Invalid, 246 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 220 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.8s IncrementalHoareTripleChecker+Time [2024-11-09 22:45:16,015 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 238 Invalid, 246 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 220 Invalid, 2 Unknown, 0 Unchecked, 10.8s Time] [2024-11-09 22:45:16,015 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 237 states. [2024-11-09 22:45:16,049 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 237 to 216. [2024-11-09 22:45:16,050 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 141 states have (on average 1.1914893617021276) internal successors, (168), 150 states have internal predecessors, (168), 49 states have call successors, (49), 26 states have call predecessors, (49), 25 states have return successors, (45), 39 states have call predecessors, (45), 45 states have call successors, (45) [2024-11-09 22:45:16,051 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 262 transitions. [2024-11-09 22:45:16,051 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 262 transitions. Word has length 47 [2024-11-09 22:45:16,051 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:45:16,051 INFO L471 AbstractCegarLoop]: Abstraction has 216 states and 262 transitions. [2024-11-09 22:45:16,051 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.6923076923076923) internal successors, (22), 10 states have internal predecessors, (22), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 4 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-09 22:45:16,051 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 262 transitions. [2024-11-09 22:45:16,054 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2024-11-09 22:45:16,055 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:45:16,055 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:45:16,067 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-09 22:45:16,258 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-09 22:45:16,259 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:45:16,259 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:45:16,259 INFO L85 PathProgramCache]: Analyzing trace with hash -646613615, now seen corresponding path program 1 times [2024-11-09 22:45:16,259 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:45:16,259 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1774542286] [2024-11-09 22:45:16,259 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:45:16,259 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:45:16,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:45:16,290 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [906626930] [2024-11-09 22:45:16,290 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:45:16,293 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:45:16,293 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:45:16,294 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-09 22:45:16,295 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-09 22:45:18,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:45:18,388 INFO L255 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 45 conjuncts are in the unsatisfiable core [2024-11-09 22:45:18,390 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:45:19,121 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 43 proven. 27 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2024-11-09 22:45:19,121 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:46:17,121 WARN L286 SmtUtils]: Spent 7.87s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify)