./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3289d67d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.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 c3e4caaff40cd418d8c93f0410c37d1e421cc5f90c41578bfaa7bb16ff289f1e --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-3289d67-m [2024-11-16 07:05:35,981 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-16 07:05:36,076 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-16 07:05:36,081 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-16 07:05:36,081 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-16 07:05:36,106 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-16 07:05:36,109 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-16 07:05:36,109 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-16 07:05:36,110 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-16 07:05:36,110 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-16 07:05:36,111 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-16 07:05:36,111 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-16 07:05:36,112 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-16 07:05:36,112 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-16 07:05:36,112 INFO L153 SettingsManager]: * Use SBE=true [2024-11-16 07:05:36,113 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-16 07:05:36,113 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-16 07:05:36,113 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-16 07:05:36,114 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-16 07:05:36,114 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-16 07:05:36,114 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-16 07:05:36,118 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-16 07:05:36,118 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-16 07:05:36,119 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-16 07:05:36,119 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-16 07:05:36,119 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-16 07:05:36,119 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-16 07:05:36,119 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-16 07:05:36,120 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-16 07:05:36,120 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-16 07:05:36,120 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-16 07:05:36,120 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-16 07:05:36,121 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-16 07:05:36,121 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-16 07:05:36,121 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-16 07:05:36,121 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-16 07:05:36,121 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-16 07:05:36,122 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-16 07:05:36,122 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-16 07:05:36,122 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-16 07:05:36,122 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-16 07:05:36,124 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-16 07:05:36,125 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 -> c3e4caaff40cd418d8c93f0410c37d1e421cc5f90c41578bfaa7bb16ff289f1e [2024-11-16 07:05:36,403 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-16 07:05:36,422 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-16 07:05:36,425 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-16 07:05:36,426 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-16 07:05:36,426 INFO L274 PluginConnector]: CDTParser initialized [2024-11-16 07:05:36,428 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.c [2024-11-16 07:05:37,827 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-16 07:05:38,032 INFO L384 CDTParser]: Found 1 translation units. [2024-11-16 07:05:38,033 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_valuebound100.c [2024-11-16 07:05:38,043 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7f9aef0af/cef2882b89e64400a938c2881f001751/FLAGae8942d90 [2024-11-16 07:05:38,410 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7f9aef0af/cef2882b89e64400a938c2881f001751 [2024-11-16 07:05:38,412 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-16 07:05:38,413 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-16 07:05:38,414 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-16 07:05:38,414 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-16 07:05:38,418 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-16 07:05:38,419 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,420 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@cf61284 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38, skipping insertion in model container [2024-11-16 07:05:38,420 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,436 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-16 07:05:38,626 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/egcd3-ll_valuebound100.c[490,503] [2024-11-16 07:05:38,646 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-16 07:05:38,654 INFO L200 MainTranslator]: Completed pre-run [2024-11-16 07:05:38,663 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/egcd3-ll_valuebound100.c[490,503] [2024-11-16 07:05:38,673 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-16 07:05:38,686 INFO L204 MainTranslator]: Completed translation [2024-11-16 07:05:38,687 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38 WrapperNode [2024-11-16 07:05:38,687 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-16 07:05:38,688 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-16 07:05:38,688 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-16 07:05:38,688 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-16 07:05:38,694 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,699 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,713 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 80 [2024-11-16 07:05:38,713 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-16 07:05:38,714 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-16 07:05:38,714 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-16 07:05:38,714 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-16 07:05:38,723 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,723 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,725 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,734 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-16 07:05:38,735 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,735 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,738 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,738 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,739 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,740 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,741 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-16 07:05:38,742 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-16 07:05:38,742 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-16 07:05:38,742 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-16 07:05:38,743 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38" (1/1) ... [2024-11-16 07:05:38,748 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-16 07:05:38,757 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:38,771 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-16 07:05:38,778 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-16 07:05:38,814 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-16 07:05:38,814 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-16 07:05:38,814 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-16 07:05:38,814 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-16 07:05:38,814 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-16 07:05:38,814 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-16 07:05:38,814 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-16 07:05:38,814 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-16 07:05:38,872 INFO L256 CfgBuilder]: Building ICFG [2024-11-16 07:05:38,875 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-16 07:05:39,033 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-16 07:05:39,033 INFO L307 CfgBuilder]: Performing block encoding [2024-11-16 07:05:39,046 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-16 07:05:39,047 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-16 07:05:39,047 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.11 07:05:39 BoogieIcfgContainer [2024-11-16 07:05:39,047 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-16 07:05:39,049 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-16 07:05:39,049 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-16 07:05:39,052 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-16 07:05:39,052 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.11 07:05:38" (1/3) ... [2024-11-16 07:05:39,052 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@34eb8768 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.11 07:05:39, skipping insertion in model container [2024-11-16 07:05:39,053 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:05:38" (2/3) ... [2024-11-16 07:05:39,053 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@34eb8768 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.11 07:05:39, skipping insertion in model container [2024-11-16 07:05:39,053 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.11 07:05:39" (3/3) ... [2024-11-16 07:05:39,054 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound100.c [2024-11-16 07:05:39,067 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-16 07:05:39,067 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-16 07:05:39,113 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-16 07:05:39,120 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;@4603d303, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-16 07:05:39,121 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-16 07:05:39,125 INFO L276 IsEmpty]: Start isEmpty. Operand has 39 states, 26 states have (on average 1.4615384615384615) internal successors, (38), 27 states have internal predecessors, (38), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-16 07:05:39,132 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-16 07:05:39,132 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:39,133 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:39,133 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:39,138 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:39,138 INFO L85 PathProgramCache]: Analyzing trace with hash 1204067688, now seen corresponding path program 1 times [2024-11-16 07:05:39,146 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:39,147 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1594215602] [2024-11-16 07:05:39,147 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:39,147 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:39,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:39,316 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-16 07:05:39,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:39,326 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-16 07:05:39,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:39,333 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-16 07:05:39,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:39,341 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-16 07:05:39,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:39,351 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:39,353 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:39,354 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1594215602] [2024-11-16 07:05:39,354 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1594215602] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:39,355 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:39,355 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-16 07:05:39,356 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1267498743] [2024-11-16 07:05:39,357 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:39,361 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-16 07:05:39,361 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:39,383 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-16 07:05:39,384 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-16 07:05:39,386 INFO L87 Difference]: Start difference. First operand has 39 states, 26 states have (on average 1.4615384615384615) internal successors, (38), 27 states have internal predecessors, (38), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-16 07:05:39,410 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:39,412 INFO L93 Difference]: Finished difference Result 75 states and 117 transitions. [2024-11-16 07:05:39,413 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-16 07:05:39,414 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2024-11-16 07:05:39,415 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:39,420 INFO L225 Difference]: With dead ends: 75 [2024-11-16 07:05:39,420 INFO L226 Difference]: Without dead ends: 35 [2024-11-16 07:05:39,424 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-16 07:05:39,428 INFO L432 NwaCegarLoop]: 48 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, 48 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:39,429 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:39,444 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2024-11-16 07:05:39,458 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2024-11-16 07:05:39,459 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-16 07:05:39,461 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 44 transitions. [2024-11-16 07:05:39,463 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 44 transitions. Word has length 30 [2024-11-16 07:05:39,463 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:39,463 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 44 transitions. [2024-11-16 07:05:39,464 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-16 07:05:39,464 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 44 transitions. [2024-11-16 07:05:39,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-16 07:05:39,465 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:39,466 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:39,466 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-16 07:05:39,466 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:39,467 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:39,467 INFO L85 PathProgramCache]: Analyzing trace with hash -440055221, now seen corresponding path program 1 times [2024-11-16 07:05:39,467 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:39,467 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [12823578] [2024-11-16 07:05:39,468 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:39,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:39,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:39,723 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-16 07:05:39,725 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:39,729 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-16 07:05:39,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:39,736 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-16 07:05:39,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:39,743 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-16 07:05:39,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:39,806 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-16 07:05:39,806 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:39,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [12823578] [2024-11-16 07:05:39,807 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [12823578] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:39,807 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:39,807 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-16 07:05:39,807 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [215624341] [2024-11-16 07:05:39,807 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:39,809 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-16 07:05:39,809 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:39,813 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-16 07:05:39,813 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-16 07:05:39,813 INFO L87 Difference]: Start difference. First operand 35 states and 44 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:39,931 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:39,931 INFO L93 Difference]: Finished difference Result 58 states and 73 transitions. [2024-11-16 07:05:39,931 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-16 07:05:39,932 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2024-11-16 07:05:39,932 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:39,933 INFO L225 Difference]: With dead ends: 58 [2024-11-16 07:05:39,933 INFO L226 Difference]: Without dead ends: 50 [2024-11-16 07:05:39,934 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-16 07:05:39,935 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 25 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 60 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 60 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:39,937 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 136 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 60 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 07:05:39,938 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2024-11-16 07:05:39,953 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 38. [2024-11-16 07:05:39,953 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 26 states have (on average 1.1538461538461537) internal successors, (30), 27 states have internal predecessors, (30), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-16 07:05:39,954 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 47 transitions. [2024-11-16 07:05:39,956 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 47 transitions. Word has length 32 [2024-11-16 07:05:39,984 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:39,984 INFO L471 AbstractCegarLoop]: Abstraction has 38 states and 47 transitions. [2024-11-16 07:05:39,985 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:39,985 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 47 transitions. [2024-11-16 07:05:39,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-11-16 07:05:39,987 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:39,987 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:39,987 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-16 07:05:39,988 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:39,989 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:39,989 INFO L85 PathProgramCache]: Analyzing trace with hash -1503367536, now seen corresponding path program 1 times [2024-11-16 07:05:39,989 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:39,989 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1340830418] [2024-11-16 07:05:39,990 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:39,990 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:40,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:40,037 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [791156018] [2024-11-16 07:05:40,037 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:40,037 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:40,037 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:40,039 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:05:40,041 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-16 07:05:40,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:40,107 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-16 07:05:40,113 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:40,273 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:40,274 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 07:05:40,274 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:40,274 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1340830418] [2024-11-16 07:05:40,274 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:40,275 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [791156018] [2024-11-16 07:05:40,275 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [791156018] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:40,275 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:40,275 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:05:40,275 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1435137107] [2024-11-16 07:05:40,275 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:40,276 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:40,276 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:40,278 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:40,279 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:05:40,279 INFO L87 Difference]: Start difference. First operand 38 states and 47 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:40,336 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:40,336 INFO L93 Difference]: Finished difference Result 57 states and 71 transitions. [2024-11-16 07:05:40,340 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:05:40,341 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 37 [2024-11-16 07:05:40,341 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:40,342 INFO L225 Difference]: With dead ends: 57 [2024-11-16 07:05:40,345 INFO L226 Difference]: Without dead ends: 54 [2024-11-16 07:05:40,345 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-16 07:05:40,347 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 7 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 150 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:40,348 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 150 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:40,349 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2024-11-16 07:05:40,359 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 53. [2024-11-16 07:05:40,360 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 36 states have (on average 1.1666666666666667) internal successors, (42), 37 states have internal predecessors, (42), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-16 07:05:40,362 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 67 transitions. [2024-11-16 07:05:40,362 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 67 transitions. Word has length 37 [2024-11-16 07:05:40,362 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:40,362 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 67 transitions. [2024-11-16 07:05:40,363 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:40,363 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 67 transitions. [2024-11-16 07:05:40,363 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-16 07:05:40,364 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:40,364 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:40,378 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-16 07:05:40,564 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:40,565 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:40,565 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:40,565 INFO L85 PathProgramCache]: Analyzing trace with hash 383673201, now seen corresponding path program 1 times [2024-11-16 07:05:40,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:40,565 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1303327503] [2024-11-16 07:05:40,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:40,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:40,587 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:40,764 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-16 07:05:40,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:40,768 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-16 07:05:40,769 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:40,770 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-16 07:05:40,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:40,803 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-16 07:05:40,805 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:40,809 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-16 07:05:40,811 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:40,812 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1303327503] [2024-11-16 07:05:40,812 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1303327503] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:05:40,815 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1524497422] [2024-11-16 07:05:40,815 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:40,815 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:40,815 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:40,817 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:05:40,819 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-16 07:05:40,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:40,872 INFO L255 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-16 07:05:40,873 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:40,935 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-16 07:05:40,937 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:41,067 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-16 07:05:41,067 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1524497422] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:05:41,068 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 07:05:41,068 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 12 [2024-11-16 07:05:41,068 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [191239147] [2024-11-16 07:05:41,068 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 07:05:41,068 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-16 07:05:41,069 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:41,070 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-16 07:05:41,070 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2024-11-16 07:05:41,071 INFO L87 Difference]: Start difference. First operand 53 states and 67 transitions. Second operand has 12 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-16 07:05:41,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:41,318 INFO L93 Difference]: Finished difference Result 118 states and 158 transitions. [2024-11-16 07:05:41,319 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-16 07:05:41,320 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 39 [2024-11-16 07:05:41,320 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:41,321 INFO L225 Difference]: With dead ends: 118 [2024-11-16 07:05:41,321 INFO L226 Difference]: Without dead ends: 110 [2024-11-16 07:05:41,321 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 77 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=54, Invalid=156, Unknown=0, NotChecked=0, Total=210 [2024-11-16 07:05:41,322 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 66 mSDsluCounter, 337 mSDsCounter, 0 mSdLazyCounter, 167 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 74 SdHoareTripleChecker+Valid, 384 SdHoareTripleChecker+Invalid, 188 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 167 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:41,323 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [74 Valid, 384 Invalid, 188 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 167 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-16 07:05:41,325 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2024-11-16 07:05:41,345 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 81. [2024-11-16 07:05:41,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 60 states have (on average 1.2) internal successors, (72), 61 states have internal predecessors, (72), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-16 07:05:41,349 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 105 transitions. [2024-11-16 07:05:41,350 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 105 transitions. Word has length 39 [2024-11-16 07:05:41,351 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:41,351 INFO L471 AbstractCegarLoop]: Abstraction has 81 states and 105 transitions. [2024-11-16 07:05:41,352 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-16 07:05:41,352 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 105 transitions. [2024-11-16 07:05:41,353 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-11-16 07:05:41,355 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:41,355 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:41,372 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-16 07:05:41,556 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2024-11-16 07:05:41,556 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:41,557 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:41,557 INFO L85 PathProgramCache]: Analyzing trace with hash -1151148547, now seen corresponding path program 1 times [2024-11-16 07:05:41,557 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:41,557 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [573345767] [2024-11-16 07:05:41,557 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:41,558 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:41,571 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:41,572 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [669074854] [2024-11-16 07:05:41,573 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:41,573 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:41,573 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:41,575 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:05:41,576 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-16 07:05:41,624 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:41,625 INFO L255 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-16 07:05:41,627 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:41,740 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:41,740 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 07:05:41,741 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:41,741 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [573345767] [2024-11-16 07:05:41,741 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:41,741 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [669074854] [2024-11-16 07:05:41,741 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [669074854] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:41,742 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:41,742 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:05:41,743 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1349194659] [2024-11-16 07:05:41,743 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:41,743 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:41,743 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:41,744 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:41,744 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:05:41,744 INFO L87 Difference]: Start difference. First operand 81 states and 105 transitions. Second operand has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 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-16 07:05:41,800 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:41,800 INFO L93 Difference]: Finished difference Result 90 states and 113 transitions. [2024-11-16 07:05:41,801 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:05:41,801 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 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 42 [2024-11-16 07:05:41,801 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:41,802 INFO L225 Difference]: With dead ends: 90 [2024-11-16 07:05:41,802 INFO L226 Difference]: Without dead ends: 87 [2024-11-16 07:05:41,803 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-16 07:05:41,804 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 7 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:41,804 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 147 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:41,805 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2024-11-16 07:05:41,818 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 85. [2024-11-16 07:05:41,818 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 63 states have (on average 1.1904761904761905) internal successors, (75), 64 states have internal predecessors, (75), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-16 07:05:41,820 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 108 transitions. [2024-11-16 07:05:41,820 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 108 transitions. Word has length 42 [2024-11-16 07:05:41,821 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:41,821 INFO L471 AbstractCegarLoop]: Abstraction has 85 states and 108 transitions. [2024-11-16 07:05:41,821 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 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-16 07:05:41,821 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 108 transitions. [2024-11-16 07:05:41,822 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-16 07:05:41,822 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:41,822 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:41,838 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-16 07:05:42,022 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:42,023 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:42,024 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:42,024 INFO L85 PathProgramCache]: Analyzing trace with hash 652942634, now seen corresponding path program 1 times [2024-11-16 07:05:42,024 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:42,024 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [700017062] [2024-11-16 07:05:42,024 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:42,024 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:42,042 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:42,043 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1806482305] [2024-11-16 07:05:42,044 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:42,044 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:42,044 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:42,046 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:05:42,048 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-16 07:05:42,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:42,101 INFO L255 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-16 07:05:42,104 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:42,240 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:42,241 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:42,410 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:42,410 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:42,411 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [700017062] [2024-11-16 07:05:42,411 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:42,411 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1806482305] [2024-11-16 07:05:42,411 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1806482305] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:05:42,411 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:05:42,411 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2024-11-16 07:05:42,411 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [45883688] [2024-11-16 07:05:42,411 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:05:42,411 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-16 07:05:42,412 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:42,412 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-16 07:05:42,412 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2024-11-16 07:05:42,412 INFO L87 Difference]: Start difference. First operand 85 states and 108 transitions. Second operand has 10 states, 10 states have (on average 4.4) internal successors, (44), 8 states have internal predecessors, (44), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:42,633 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:42,633 INFO L93 Difference]: Finished difference Result 129 states and 165 transitions. [2024-11-16 07:05:42,634 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-16 07:05:42,635 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.4) internal successors, (44), 8 states have internal predecessors, (44), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 44 [2024-11-16 07:05:42,635 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:42,636 INFO L225 Difference]: With dead ends: 129 [2024-11-16 07:05:42,638 INFO L226 Difference]: Without dead ends: 126 [2024-11-16 07:05:42,639 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-11-16 07:05:42,639 INFO L432 NwaCegarLoop]: 58 mSDtfsCounter, 14 mSDsluCounter, 299 mSDsCounter, 0 mSdLazyCounter, 108 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 357 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 108 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:42,639 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 357 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 108 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-16 07:05:42,640 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2024-11-16 07:05:42,659 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 122. [2024-11-16 07:05:42,660 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 91 states have (on average 1.1978021978021978) internal successors, (109), 92 states have internal predecessors, (109), 25 states have call successors, (25), 5 states have call predecessors, (25), 5 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-16 07:05:42,661 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 158 transitions. [2024-11-16 07:05:42,661 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 158 transitions. Word has length 44 [2024-11-16 07:05:42,662 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:42,662 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 158 transitions. [2024-11-16 07:05:42,662 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.4) internal successors, (44), 8 states have internal predecessors, (44), 3 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:42,662 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 158 transitions. [2024-11-16 07:05:42,663 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-16 07:05:42,663 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:42,663 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:42,681 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-16 07:05:42,867 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:42,868 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:42,868 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:42,868 INFO L85 PathProgramCache]: Analyzing trace with hash 898378352, now seen corresponding path program 1 times [2024-11-16 07:05:42,868 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:42,868 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [514111628] [2024-11-16 07:05:42,868 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:42,869 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:42,879 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:42,880 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1751173282] [2024-11-16 07:05:42,880 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:42,880 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:42,880 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:42,882 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:05:42,883 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-16 07:05:42,935 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:42,936 INFO L255 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-16 07:05:42,938 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:42,997 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-16 07:05:42,997 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 07:05:42,998 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:42,998 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [514111628] [2024-11-16 07:05:42,999 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:42,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1751173282] [2024-11-16 07:05:42,999 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1751173282] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:42,999 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:42,999 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:05:42,999 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [287836336] [2024-11-16 07:05:42,999 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:43,000 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:43,000 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:43,000 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:43,000 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:05:43,001 INFO L87 Difference]: Start difference. First operand 122 states and 158 transitions. Second operand has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-16 07:05:43,064 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:43,065 INFO L93 Difference]: Finished difference Result 176 states and 238 transitions. [2024-11-16 07:05:43,065 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:05:43,065 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 47 [2024-11-16 07:05:43,067 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:43,068 INFO L225 Difference]: With dead ends: 176 [2024-11-16 07:05:43,068 INFO L226 Difference]: Without dead ends: 173 [2024-11-16 07:05:43,068 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-16 07:05:43,069 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 6 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:43,069 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 140 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:43,070 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2024-11-16 07:05:43,093 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 167. [2024-11-16 07:05:43,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 167 states, 115 states have (on average 1.2173913043478262) internal successors, (140), 116 states have internal predecessors, (140), 45 states have call successors, (45), 6 states have call predecessors, (45), 6 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-11-16 07:05:43,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 167 states to 167 states and 229 transitions. [2024-11-16 07:05:43,096 INFO L78 Accepts]: Start accepts. Automaton has 167 states and 229 transitions. Word has length 47 [2024-11-16 07:05:43,096 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:43,096 INFO L471 AbstractCegarLoop]: Abstraction has 167 states and 229 transitions. [2024-11-16 07:05:43,096 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-16 07:05:43,097 INFO L276 IsEmpty]: Start isEmpty. Operand 167 states and 229 transitions. [2024-11-16 07:05:43,097 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-16 07:05:43,097 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:43,098 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:43,114 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-16 07:05:43,298 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:43,299 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:43,299 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:43,299 INFO L85 PathProgramCache]: Analyzing trace with hash -1868349533, now seen corresponding path program 1 times [2024-11-16 07:05:43,299 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:43,299 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1591995044] [2024-11-16 07:05:43,299 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:43,299 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:43,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:43,313 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1521872124] [2024-11-16 07:05:43,313 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:43,313 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:43,313 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:43,315 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:05:43,316 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-16 07:05:43,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:43,364 INFO L255 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-11-16 07:05:43,366 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:43,555 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 1 proven. 7 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:43,555 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:43,616 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:43,616 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1591995044] [2024-11-16 07:05:43,616 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:43,617 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1521872124] [2024-11-16 07:05:43,617 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1521872124] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:05:43,617 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-16 07:05:43,617 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2024-11-16 07:05:43,617 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [287650239] [2024-11-16 07:05:43,617 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-16 07:05:43,617 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-16 07:05:43,618 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:43,618 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-16 07:05:43,618 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2024-11-16 07:05:43,618 INFO L87 Difference]: Start difference. First operand 167 states and 229 transitions. Second operand has 9 states, 9 states have (on average 3.2222222222222223) internal successors, (29), 8 states have internal predecessors, (29), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-16 07:05:43,797 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:43,798 INFO L93 Difference]: Finished difference Result 181 states and 241 transitions. [2024-11-16 07:05:43,798 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-16 07:05:43,798 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.2222222222222223) internal successors, (29), 8 states have internal predecessors, (29), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 49 [2024-11-16 07:05:43,798 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:43,800 INFO L225 Difference]: With dead ends: 181 [2024-11-16 07:05:43,800 INFO L226 Difference]: Without dead ends: 178 [2024-11-16 07:05:43,801 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2024-11-16 07:05:43,803 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 32 mSDsluCounter, 215 mSDsCounter, 0 mSdLazyCounter, 160 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 258 SdHoareTripleChecker+Invalid, 174 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 160 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:43,803 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 258 Invalid, 174 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 160 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 07:05:43,804 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2024-11-16 07:05:43,824 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 175. [2024-11-16 07:05:43,825 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 175 states, 121 states have (on average 1.2066115702479339) internal successors, (146), 122 states have internal predecessors, (146), 45 states have call successors, (45), 8 states have call predecessors, (45), 8 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2024-11-16 07:05:43,826 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 175 states to 175 states and 235 transitions. [2024-11-16 07:05:43,827 INFO L78 Accepts]: Start accepts. Automaton has 175 states and 235 transitions. Word has length 49 [2024-11-16 07:05:43,828 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:43,828 INFO L471 AbstractCegarLoop]: Abstraction has 175 states and 235 transitions. [2024-11-16 07:05:43,828 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.2222222222222223) internal successors, (29), 8 states have internal predecessors, (29), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-16 07:05:43,829 INFO L276 IsEmpty]: Start isEmpty. Operand 175 states and 235 transitions. [2024-11-16 07:05:43,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-11-16 07:05:43,832 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:43,833 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:43,851 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-16 07:05:44,036 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:44,037 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:44,037 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:44,037 INFO L85 PathProgramCache]: Analyzing trace with hash 503958941, now seen corresponding path program 1 times [2024-11-16 07:05:44,037 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:44,037 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1002136875] [2024-11-16 07:05:44,037 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:44,038 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:44,047 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:44,048 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [65264592] [2024-11-16 07:05:44,048 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:44,048 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:44,049 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:44,050 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:05:44,053 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-16 07:05:44,098 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:44,099 INFO L255 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-16 07:05:44,101 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:44,144 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-16 07:05:44,145 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 07:05:44,145 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:44,145 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1002136875] [2024-11-16 07:05:44,145 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:44,145 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [65264592] [2024-11-16 07:05:44,145 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [65264592] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:44,145 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:44,145 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:05:44,145 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [643718645] [2024-11-16 07:05:44,145 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:44,146 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:44,146 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:44,146 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:44,146 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:05:44,146 INFO L87 Difference]: Start difference. First operand 175 states and 235 transitions. Second operand has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-16 07:05:44,216 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:44,216 INFO L93 Difference]: Finished difference Result 257 states and 366 transitions. [2024-11-16 07:05:44,217 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:05:44,217 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 52 [2024-11-16 07:05:44,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:44,221 INFO L225 Difference]: With dead ends: 257 [2024-11-16 07:05:44,221 INFO L226 Difference]: Without dead ends: 254 [2024-11-16 07:05:44,221 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 48 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-16 07:05:44,222 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 4 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 148 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:44,223 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 148 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:44,223 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 254 states. [2024-11-16 07:05:44,262 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 254 to 239. [2024-11-16 07:05:44,263 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 239 states, 144 states have (on average 1.1736111111111112) internal successors, (169), 155 states have internal predecessors, (169), 85 states have call successors, (85), 9 states have call predecessors, (85), 9 states have return successors, (84), 74 states have call predecessors, (84), 84 states have call successors, (84) [2024-11-16 07:05:44,265 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 239 states to 239 states and 338 transitions. [2024-11-16 07:05:44,266 INFO L78 Accepts]: Start accepts. Automaton has 239 states and 338 transitions. Word has length 52 [2024-11-16 07:05:44,266 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:44,266 INFO L471 AbstractCegarLoop]: Abstraction has 239 states and 338 transitions. [2024-11-16 07:05:44,266 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.4) internal successors, (22), 4 states have internal predecessors, (22), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-16 07:05:44,266 INFO L276 IsEmpty]: Start isEmpty. Operand 239 states and 338 transitions. [2024-11-16 07:05:44,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-16 07:05:44,267 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:44,267 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:44,286 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-16 07:05:44,468 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:44,468 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:44,468 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:44,468 INFO L85 PathProgramCache]: Analyzing trace with hash -1382437552, now seen corresponding path program 2 times [2024-11-16 07:05:44,469 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:44,469 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1560300494] [2024-11-16 07:05:44,469 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:44,469 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:44,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:44,531 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-16 07:05:44,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:44,534 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-16 07:05:44,534 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:44,536 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-16 07:05:44,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:44,537 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-16 07:05:44,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:44,539 INFO L134 CoverageAnalysis]: Checked inductivity of 43 backedges. 19 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-16 07:05:44,539 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:44,539 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1560300494] [2024-11-16 07:05:44,540 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1560300494] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:44,540 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:44,540 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:05:44,540 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [850387444] [2024-11-16 07:05:44,540 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:44,540 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:44,541 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:44,541 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:44,541 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:05:44,541 INFO L87 Difference]: Start difference. First operand 239 states and 338 transitions. Second operand has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:44,639 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:44,639 INFO L93 Difference]: Finished difference Result 302 states and 421 transitions. [2024-11-16 07:05:44,640 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-16 07:05:44,640 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 51 [2024-11-16 07:05:44,640 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:44,643 INFO L225 Difference]: With dead ends: 302 [2024-11-16 07:05:44,643 INFO L226 Difference]: Without dead ends: 205 [2024-11-16 07:05:44,644 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2024-11-16 07:05:44,644 INFO L432 NwaCegarLoop]: 56 mSDtfsCounter, 23 mSDsluCounter, 129 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 185 SdHoareTripleChecker+Invalid, 62 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:44,645 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 185 Invalid, 62 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 07:05:44,645 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 205 states. [2024-11-16 07:05:44,669 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 205 to 195. [2024-11-16 07:05:44,670 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 195 states, 116 states have (on average 1.1379310344827587) internal successors, (132), 125 states have internal predecessors, (132), 69 states have call successors, (69), 9 states have call predecessors, (69), 9 states have return successors, (68), 60 states have call predecessors, (68), 68 states have call successors, (68) [2024-11-16 07:05:44,672 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 195 states to 195 states and 269 transitions. [2024-11-16 07:05:44,672 INFO L78 Accepts]: Start accepts. Automaton has 195 states and 269 transitions. Word has length 51 [2024-11-16 07:05:44,672 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:44,673 INFO L471 AbstractCegarLoop]: Abstraction has 195 states and 269 transitions. [2024-11-16 07:05:44,673 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-16 07:05:44,673 INFO L276 IsEmpty]: Start isEmpty. Operand 195 states and 269 transitions. [2024-11-16 07:05:44,674 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2024-11-16 07:05:44,674 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:44,674 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:44,674 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2024-11-16 07:05:44,674 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:44,675 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:44,675 INFO L85 PathProgramCache]: Analyzing trace with hash 538614248, now seen corresponding path program 1 times [2024-11-16 07:05:44,675 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:44,675 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1441435084] [2024-11-16 07:05:44,675 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:44,675 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:44,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:44,694 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [66484602] [2024-11-16 07:05:44,696 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:44,696 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:44,697 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:44,698 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:05:44,700 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-16 07:05:44,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:44,756 INFO L255 TraceCheckSpWp]: Trace formula consists of 159 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-11-16 07:05:44,758 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:45,503 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 14 proven. 9 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-16 07:05:45,503 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:46,653 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 8 proven. 6 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-16 07:05:46,653 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:46,653 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1441435084] [2024-11-16 07:05:46,654 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:46,654 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [66484602] [2024-11-16 07:05:46,654 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [66484602] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:05:46,654 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:05:46,654 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-11-16 07:05:46,654 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [84311231] [2024-11-16 07:05:46,654 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:05:46,655 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-16 07:05:46,655 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:46,656 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-16 07:05:46,656 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2024-11-16 07:05:46,656 INFO L87 Difference]: Start difference. First operand 195 states and 269 transitions. Second operand has 23 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 20 states have internal predecessors, (54), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-16 07:05:50,550 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:50,551 INFO L93 Difference]: Finished difference Result 526 states and 746 transitions. [2024-11-16 07:05:50,551 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2024-11-16 07:05:50,552 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 20 states have internal predecessors, (54), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 66 [2024-11-16 07:05:50,552 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:50,556 INFO L225 Difference]: With dead ends: 526 [2024-11-16 07:05:50,556 INFO L226 Difference]: Without dead ends: 405 [2024-11-16 07:05:50,559 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 109 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 429 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=398, Invalid=1672, Unknown=0, NotChecked=0, Total=2070 [2024-11-16 07:05:50,560 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 226 mSDsluCounter, 449 mSDsCounter, 0 mSdLazyCounter, 571 mSolverCounterSat, 153 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 234 SdHoareTripleChecker+Valid, 487 SdHoareTripleChecker+Invalid, 724 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 153 IncrementalHoareTripleChecker+Valid, 571 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.3s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:50,560 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [234 Valid, 487 Invalid, 724 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [153 Valid, 571 Invalid, 0 Unknown, 0 Unchecked, 2.3s Time] [2024-11-16 07:05:50,561 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 405 states. [2024-11-16 07:05:50,657 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 405 to 305. [2024-11-16 07:05:50,657 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 305 states, 199 states have (on average 1.1557788944723617) internal successors, (230), 206 states have internal predecessors, (230), 93 states have call successors, (93), 12 states have call predecessors, (93), 12 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-16 07:05:50,659 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 305 states to 305 states and 415 transitions. [2024-11-16 07:05:50,660 INFO L78 Accepts]: Start accepts. Automaton has 305 states and 415 transitions. Word has length 66 [2024-11-16 07:05:50,660 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:50,660 INFO L471 AbstractCegarLoop]: Abstraction has 305 states and 415 transitions. [2024-11-16 07:05:50,661 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 20 states have internal predecessors, (54), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-16 07:05:50,661 INFO L276 IsEmpty]: Start isEmpty. Operand 305 states and 415 transitions. [2024-11-16 07:05:50,662 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2024-11-16 07:05:50,662 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:50,663 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:50,677 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-16 07:05:50,866 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-16 07:05:50,867 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:50,867 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:50,867 INFO L85 PathProgramCache]: Analyzing trace with hash -308189961, now seen corresponding path program 1 times [2024-11-16 07:05:50,867 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:50,867 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1097394989] [2024-11-16 07:05:50,868 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:50,868 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:50,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:50,888 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [643206971] [2024-11-16 07:05:50,888 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:50,889 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:50,889 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:50,894 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:05:50,896 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-16 07:05:50,947 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:50,948 INFO L255 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-16 07:05:50,950 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:51,020 INFO L134 CoverageAnalysis]: Checked inductivity of 128 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 108 trivial. 0 not checked. [2024-11-16 07:05:51,020 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:51,098 INFO L134 CoverageAnalysis]: Checked inductivity of 128 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 114 trivial. 0 not checked. [2024-11-16 07:05:51,099 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:51,099 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1097394989] [2024-11-16 07:05:51,099 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:51,099 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [643206971] [2024-11-16 07:05:51,099 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [643206971] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-16 07:05:51,099 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-16 07:05:51,099 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-16 07:05:51,100 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [325418933] [2024-11-16 07:05:51,100 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:51,100 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:51,100 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:51,101 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:51,101 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-16 07:05:51,101 INFO L87 Difference]: Start difference. First operand 305 states and 415 transitions. Second operand has 5 states, 5 states have (on average 4.6) internal successors, (23), 4 states have internal predecessors, (23), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-16 07:05:51,230 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:51,231 INFO L93 Difference]: Finished difference Result 312 states and 421 transitions. [2024-11-16 07:05:51,231 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:05:51,231 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 4 states have internal predecessors, (23), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 75 [2024-11-16 07:05:51,232 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:51,236 INFO L225 Difference]: With dead ends: 312 [2024-11-16 07:05:51,236 INFO L226 Difference]: Without dead ends: 309 [2024-11-16 07:05:51,237 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 141 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-16 07:05:51,237 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 4 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:51,237 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 142 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:51,238 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 309 states. [2024-11-16 07:05:51,323 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 309 to 309. [2024-11-16 07:05:51,323 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 309 states, 202 states have (on average 1.1534653465346534) internal successors, (233), 209 states have internal predecessors, (233), 93 states have call successors, (93), 13 states have call predecessors, (93), 13 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-16 07:05:51,325 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 309 states to 309 states and 418 transitions. [2024-11-16 07:05:51,326 INFO L78 Accepts]: Start accepts. Automaton has 309 states and 418 transitions. Word has length 75 [2024-11-16 07:05:51,326 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:51,326 INFO L471 AbstractCegarLoop]: Abstraction has 309 states and 418 transitions. [2024-11-16 07:05:51,326 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 4 states have internal predecessors, (23), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-16 07:05:51,326 INFO L276 IsEmpty]: Start isEmpty. Operand 309 states and 418 transitions. [2024-11-16 07:05:51,327 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2024-11-16 07:05:51,327 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:51,327 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:51,344 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-16 07:05:51,528 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:51,528 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:51,528 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:51,528 INFO L85 PathProgramCache]: Analyzing trace with hash -2085625555, now seen corresponding path program 1 times [2024-11-16 07:05:51,529 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:51,529 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1500064809] [2024-11-16 07:05:51,529 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:51,529 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:51,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:51,552 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1582215733] [2024-11-16 07:05:51,552 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:51,552 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:51,552 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:51,554 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:05:51,556 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-16 07:05:51,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:51,614 INFO L255 TraceCheckSpWp]: Trace formula consists of 193 conjuncts, 49 conjuncts are in the unsatisfiable core [2024-11-16 07:05:51,616 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:52,207 INFO L134 CoverageAnalysis]: Checked inductivity of 87 backedges. 16 proven. 41 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-16 07:05:52,208 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:52,432 INFO L134 CoverageAnalysis]: Checked inductivity of 87 backedges. 32 proven. 10 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-16 07:05:52,432 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:52,432 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1500064809] [2024-11-16 07:05:52,433 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:52,433 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1582215733] [2024-11-16 07:05:52,433 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1582215733] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:05:52,433 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:05:52,433 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2024-11-16 07:05:52,433 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1693628479] [2024-11-16 07:05:52,433 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:05:52,434 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-16 07:05:52,434 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:52,434 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-16 07:05:52,434 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2024-11-16 07:05:52,434 INFO L87 Difference]: Start difference. First operand 309 states and 418 transitions. Second operand has 22 states, 22 states have (on average 3.5454545454545454) internal successors, (78), 19 states have internal predecessors, (78), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-16 07:05:54,708 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:54,709 INFO L93 Difference]: Finished difference Result 383 states and 520 transitions. [2024-11-16 07:05:54,709 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-16 07:05:54,709 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 3.5454545454545454) internal successors, (78), 19 states have internal predecessors, (78), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 78 [2024-11-16 07:05:54,710 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:54,712 INFO L225 Difference]: With dead ends: 383 [2024-11-16 07:05:54,712 INFO L226 Difference]: Without dead ends: 380 [2024-11-16 07:05:54,713 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 143 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 193 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=190, Invalid=932, Unknown=0, NotChecked=0, Total=1122 [2024-11-16 07:05:54,713 INFO L432 NwaCegarLoop]: 66 mSDtfsCounter, 140 mSDsluCounter, 691 mSDsCounter, 0 mSdLazyCounter, 683 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 142 SdHoareTripleChecker+Valid, 757 SdHoareTripleChecker+Invalid, 774 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 683 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:54,713 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [142 Valid, 757 Invalid, 774 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 683 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2024-11-16 07:05:54,714 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 380 states. [2024-11-16 07:05:54,808 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 380 to 317. [2024-11-16 07:05:54,808 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 317 states, 208 states have (on average 1.1490384615384615) internal successors, (239), 215 states have internal predecessors, (239), 93 states have call successors, (93), 15 states have call predecessors, (93), 15 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-16 07:05:54,810 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 317 states to 317 states and 424 transitions. [2024-11-16 07:05:54,811 INFO L78 Accepts]: Start accepts. Automaton has 317 states and 424 transitions. Word has length 78 [2024-11-16 07:05:54,811 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:54,811 INFO L471 AbstractCegarLoop]: Abstraction has 317 states and 424 transitions. [2024-11-16 07:05:54,811 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 3.5454545454545454) internal successors, (78), 19 states have internal predecessors, (78), 6 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-16 07:05:54,811 INFO L276 IsEmpty]: Start isEmpty. Operand 317 states and 424 transitions. [2024-11-16 07:05:54,812 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2024-11-16 07:05:54,812 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:54,812 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:54,829 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-16 07:05:55,013 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-16 07:05:55,013 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:55,013 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:55,014 INFO L85 PathProgramCache]: Analyzing trace with hash -882752627, now seen corresponding path program 2 times [2024-11-16 07:05:55,014 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:55,014 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [15459321] [2024-11-16 07:05:55,014 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:55,014 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:55,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:55,099 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-16 07:05:55,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:55,102 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-16 07:05:55,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:55,104 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-16 07:05:55,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:55,108 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-16 07:05:55,109 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:55,110 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-16 07:05:55,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:55,115 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2024-11-16 07:05:55,120 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:55,122 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2024-11-16 07:05:55,124 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:55,126 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-11-16 07:05:55,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:55,131 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 66 [2024-11-16 07:05:55,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:55,136 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 71 [2024-11-16 07:05:55,140 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:05:55,142 INFO L134 CoverageAnalysis]: Checked inductivity of 113 backedges. 23 proven. 0 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2024-11-16 07:05:55,145 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:55,145 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [15459321] [2024-11-16 07:05:55,145 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [15459321] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:05:55,145 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:05:55,146 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:05:55,146 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [548889466] [2024-11-16 07:05:55,146 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:05:55,146 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:05:55,146 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:55,147 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:05:55,147 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:05:55,147 INFO L87 Difference]: Start difference. First operand 317 states and 424 transitions. Second operand has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-16 07:05:55,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:55,297 INFO L93 Difference]: Finished difference Result 543 states and 729 transitions. [2024-11-16 07:05:55,297 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:05:55,298 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 81 [2024-11-16 07:05:55,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:55,300 INFO L225 Difference]: With dead ends: 543 [2024-11-16 07:05:55,300 INFO L226 Difference]: Without dead ends: 343 [2024-11-16 07:05:55,301 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-16 07:05:55,301 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 1 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:55,302 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 140 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:05:55,302 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 343 states. [2024-11-16 07:05:55,389 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 343 to 327. [2024-11-16 07:05:55,390 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 327 states, 218 states have (on average 1.151376146788991) internal successors, (251), 219 states have internal predecessors, (251), 93 states have call successors, (93), 15 states have call predecessors, (93), 15 states have return successors, (92), 92 states have call predecessors, (92), 92 states have call successors, (92) [2024-11-16 07:05:55,392 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 327 states to 327 states and 436 transitions. [2024-11-16 07:05:55,392 INFO L78 Accepts]: Start accepts. Automaton has 327 states and 436 transitions. Word has length 81 [2024-11-16 07:05:55,393 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:55,393 INFO L471 AbstractCegarLoop]: Abstraction has 327 states and 436 transitions. [2024-11-16 07:05:55,393 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-16 07:05:55,393 INFO L276 IsEmpty]: Start isEmpty. Operand 327 states and 436 transitions. [2024-11-16 07:05:55,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2024-11-16 07:05:55,394 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:55,394 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:55,394 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13 [2024-11-16 07:05:55,394 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:05:55,395 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:05:55,395 INFO L85 PathProgramCache]: Analyzing trace with hash 156730752, now seen corresponding path program 3 times [2024-11-16 07:05:55,395 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:05:55,395 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [419993697] [2024-11-16 07:05:55,395 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:05:55,395 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:05:55,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:05:55,411 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [776444240] [2024-11-16 07:05:55,411 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-16 07:05:55,411 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:05:55,411 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:05:55,413 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:05:55,414 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-16 07:05:55,472 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-16 07:05:55,473 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:05:55,474 INFO L255 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 65 conjuncts are in the unsatisfiable core [2024-11-16 07:05:55,476 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:05:56,345 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 21 proven. 33 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-11-16 07:05:56,345 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:05:59,055 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:05:59,055 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [419993697] [2024-11-16 07:05:59,055 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:05:59,055 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [776444240] [2024-11-16 07:05:59,055 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [776444240] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:05:59,055 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-16 07:05:59,055 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-11-16 07:05:59,055 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [64089292] [2024-11-16 07:05:59,056 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-16 07:05:59,056 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-16 07:05:59,056 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:05:59,056 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-16 07:05:59,057 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=453, Unknown=0, NotChecked=0, Total=552 [2024-11-16 07:05:59,057 INFO L87 Difference]: Start difference. First operand 327 states and 436 transitions. Second operand has 16 states, 15 states have (on average 3.066666666666667) internal successors, (46), 14 states have internal predecessors, (46), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2024-11-16 07:05:59,693 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:05:59,693 INFO L93 Difference]: Finished difference Result 405 states and 530 transitions. [2024-11-16 07:05:59,693 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-16 07:05:59,694 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 3.066666666666667) internal successors, (46), 14 states have internal predecessors, (46), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 83 [2024-11-16 07:05:59,694 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:05:59,696 INFO L225 Difference]: With dead ends: 405 [2024-11-16 07:05:59,696 INFO L226 Difference]: Without dead ends: 402 [2024-11-16 07:05:59,697 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 141 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=167, Invalid=763, Unknown=0, NotChecked=0, Total=930 [2024-11-16 07:05:59,697 INFO L432 NwaCegarLoop]: 55 mSDtfsCounter, 63 mSDsluCounter, 549 mSDsCounter, 0 mSdLazyCounter, 471 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 75 SdHoareTripleChecker+Valid, 604 SdHoareTripleChecker+Invalid, 519 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 471 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-16 07:05:59,697 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [75 Valid, 604 Invalid, 519 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 471 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-16 07:05:59,698 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 402 states. [2024-11-16 07:05:59,803 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 402 to 390. [2024-11-16 07:05:59,804 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 390 states, 260 states have (on average 1.146153846153846) internal successors, (298), 261 states have internal predecessors, (298), 109 states have call successors, (109), 20 states have call predecessors, (109), 20 states have return successors, (108), 108 states have call predecessors, (108), 108 states have call successors, (108) [2024-11-16 07:05:59,806 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 390 states to 390 states and 515 transitions. [2024-11-16 07:05:59,807 INFO L78 Accepts]: Start accepts. Automaton has 390 states and 515 transitions. Word has length 83 [2024-11-16 07:05:59,807 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:05:59,807 INFO L471 AbstractCegarLoop]: Abstraction has 390 states and 515 transitions. [2024-11-16 07:05:59,808 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 3.066666666666667) internal successors, (46), 14 states have internal predecessors, (46), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2024-11-16 07:05:59,808 INFO L276 IsEmpty]: Start isEmpty. Operand 390 states and 515 transitions. [2024-11-16 07:05:59,809 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2024-11-16 07:05:59,809 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:05:59,810 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:05:59,827 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-16 07:06:00,013 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-16 07:06:00,014 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:06:00,014 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:06:00,014 INFO L85 PathProgramCache]: Analyzing trace with hash -382848575, now seen corresponding path program 1 times [2024-11-16 07:06:00,014 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:06:00,014 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [246569193] [2024-11-16 07:06:00,014 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:06:00,014 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:06:00,042 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:06:00,045 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1104511448] [2024-11-16 07:06:00,045 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:06:00,046 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:06:00,046 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:06:00,047 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:06:00,049 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-16 07:06:00,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:00,113 INFO L255 TraceCheckSpWp]: Trace formula consists of 210 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-16 07:06:00,116 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:06:00,439 INFO L134 CoverageAnalysis]: Checked inductivity of 244 backedges. 26 proven. 23 refuted. 0 times theorem prover too weak. 195 trivial. 0 not checked. [2024-11-16 07:06:00,439 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:06:00,976 INFO L134 CoverageAnalysis]: Checked inductivity of 244 backedges. 23 proven. 17 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2024-11-16 07:06:00,976 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:06:00,976 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [246569193] [2024-11-16 07:06:00,976 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:06:00,976 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1104511448] [2024-11-16 07:06:00,976 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1104511448] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:06:00,976 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:06:00,976 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 10] total 22 [2024-11-16 07:06:00,977 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [922251047] [2024-11-16 07:06:00,977 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:06:00,977 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-16 07:06:00,977 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:06:00,978 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-16 07:06:00,978 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=373, Unknown=0, NotChecked=0, Total=462 [2024-11-16 07:06:00,978 INFO L87 Difference]: Start difference. First operand 390 states and 515 transitions. Second operand has 22 states, 22 states have (on average 2.5454545454545454) internal successors, (56), 19 states have internal predecessors, (56), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-16 07:06:03,028 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:06:03,029 INFO L93 Difference]: Finished difference Result 979 states and 1449 transitions. [2024-11-16 07:06:03,029 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2024-11-16 07:06:03,029 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.5454545454545454) internal successors, (56), 19 states have internal predecessors, (56), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 97 [2024-11-16 07:06:03,030 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:06:03,034 INFO L225 Difference]: With dead ends: 979 [2024-11-16 07:06:03,034 INFO L226 Difference]: Without dead ends: 976 [2024-11-16 07:06:03,035 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 220 GetRequests, 173 SyntacticMatches, 0 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 561 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=528, Invalid=1824, Unknown=0, NotChecked=0, Total=2352 [2024-11-16 07:06:03,036 INFO L432 NwaCegarLoop]: 51 mSDtfsCounter, 184 mSDsluCounter, 512 mSDsCounter, 0 mSdLazyCounter, 480 mSolverCounterSat, 127 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 188 SdHoareTripleChecker+Valid, 563 SdHoareTripleChecker+Invalid, 607 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 127 IncrementalHoareTripleChecker+Valid, 480 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-16 07:06:03,036 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [188 Valid, 563 Invalid, 607 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [127 Valid, 480 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-16 07:06:03,037 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 976 states. [2024-11-16 07:06:03,321 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 976 to 787. [2024-11-16 07:06:03,322 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 787 states, 458 states have (on average 1.2096069868995634) internal successors, (554), 459 states have internal predecessors, (554), 305 states have call successors, (305), 23 states have call predecessors, (305), 23 states have return successors, (304), 304 states have call predecessors, (304), 304 states have call successors, (304) [2024-11-16 07:06:03,326 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 787 states to 787 states and 1163 transitions. [2024-11-16 07:06:03,327 INFO L78 Accepts]: Start accepts. Automaton has 787 states and 1163 transitions. Word has length 97 [2024-11-16 07:06:03,328 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:06:03,328 INFO L471 AbstractCegarLoop]: Abstraction has 787 states and 1163 transitions. [2024-11-16 07:06:03,328 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.5454545454545454) internal successors, (56), 19 states have internal predecessors, (56), 8 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-16 07:06:03,329 INFO L276 IsEmpty]: Start isEmpty. Operand 787 states and 1163 transitions. [2024-11-16 07:06:03,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2024-11-16 07:06:03,330 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:06:03,330 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:06:03,347 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-16 07:06:03,534 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-16 07:06:03,535 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:06:03,536 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:06:03,536 INFO L85 PathProgramCache]: Analyzing trace with hash -1581530788, now seen corresponding path program 1 times [2024-11-16 07:06:03,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:06:03,536 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2031776168] [2024-11-16 07:06:03,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:06:03,536 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:06:03,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:06:03,557 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [358975330] [2024-11-16 07:06:03,558 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:06:03,558 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:06:03,558 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:06:03,560 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:06:03,561 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-16 07:06:03,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:03,629 INFO L255 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 60 conjuncts are in the unsatisfiable core [2024-11-16 07:06:03,631 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:06:05,361 INFO L134 CoverageAnalysis]: Checked inductivity of 178 backedges. 36 proven. 36 refuted. 0 times theorem prover too weak. 106 trivial. 0 not checked. [2024-11-16 07:06:05,361 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:06:10,725 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:06:10,726 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2031776168] [2024-11-16 07:06:10,726 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:06:10,726 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [358975330] [2024-11-16 07:06:10,726 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [358975330] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:06:10,726 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-16 07:06:10,726 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2024-11-16 07:06:10,727 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1199648993] [2024-11-16 07:06:10,727 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-16 07:06:10,727 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-16 07:06:10,727 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:06:10,728 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-16 07:06:10,728 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=663, Unknown=1, NotChecked=0, Total=756 [2024-11-16 07:06:10,728 INFO L87 Difference]: Start difference. First operand 787 states and 1163 transitions. Second operand has 21 states, 20 states have (on average 2.35) internal successors, (47), 19 states have internal predecessors, (47), 6 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-16 07:06:13,529 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:06:13,529 INFO L93 Difference]: Finished difference Result 937 states and 1384 transitions. [2024-11-16 07:06:13,529 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-16 07:06:13,530 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 2.35) internal successors, (47), 19 states have internal predecessors, (47), 6 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) Word has length 96 [2024-11-16 07:06:13,530 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:06:13,534 INFO L225 Difference]: With dead ends: 937 [2024-11-16 07:06:13,534 INFO L226 Difference]: Without dead ends: 929 [2024-11-16 07:06:13,535 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 94 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 253 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=165, Invalid=1166, Unknown=1, NotChecked=0, Total=1332 [2024-11-16 07:06:13,535 INFO L432 NwaCegarLoop]: 64 mSDtfsCounter, 103 mSDsluCounter, 758 mSDsCounter, 0 mSdLazyCounter, 932 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 119 SdHoareTripleChecker+Valid, 822 SdHoareTripleChecker+Invalid, 990 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 932 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-11-16 07:06:13,535 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [119 Valid, 822 Invalid, 990 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 932 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2024-11-16 07:06:13,536 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 929 states. [2024-11-16 07:06:13,926 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 929 to 912. [2024-11-16 07:06:13,928 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 912 states, 525 states have (on average 1.2152380952380952) internal successors, (638), 526 states have internal predecessors, (638), 361 states have call successors, (361), 25 states have call predecessors, (361), 25 states have return successors, (360), 360 states have call predecessors, (360), 360 states have call successors, (360) [2024-11-16 07:06:13,932 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 912 states to 912 states and 1359 transitions. [2024-11-16 07:06:13,933 INFO L78 Accepts]: Start accepts. Automaton has 912 states and 1359 transitions. Word has length 96 [2024-11-16 07:06:13,933 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:06:13,934 INFO L471 AbstractCegarLoop]: Abstraction has 912 states and 1359 transitions. [2024-11-16 07:06:13,934 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 2.35) internal successors, (47), 19 states have internal predecessors, (47), 6 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-16 07:06:13,934 INFO L276 IsEmpty]: Start isEmpty. Operand 912 states and 1359 transitions. [2024-11-16 07:06:13,935 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2024-11-16 07:06:13,935 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:06:13,936 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:06:13,949 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2024-11-16 07:06:14,139 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-16 07:06:14,140 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:06:14,140 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:06:14,140 INFO L85 PathProgramCache]: Analyzing trace with hash -471812428, now seen corresponding path program 1 times [2024-11-16 07:06:14,140 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:06:14,140 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1595326823] [2024-11-16 07:06:14,140 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:06:14,140 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:06:14,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:06:14,160 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2096898145] [2024-11-16 07:06:14,160 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:06:14,160 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:06:14,160 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:06:14,163 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:06:14,164 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-16 07:06:14,222 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:14,224 INFO L255 TraceCheckSpWp]: Trace formula consists of 223 conjuncts, 47 conjuncts are in the unsatisfiable core [2024-11-16 07:06:14,226 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:06:14,954 INFO L134 CoverageAnalysis]: Checked inductivity of 213 backedges. 24 proven. 30 refuted. 0 times theorem prover too weak. 159 trivial. 0 not checked. [2024-11-16 07:06:14,954 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:06:16,429 INFO L134 CoverageAnalysis]: Checked inductivity of 213 backedges. 18 proven. 27 refuted. 0 times theorem prover too weak. 168 trivial. 0 not checked. [2024-11-16 07:06:16,429 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:06:16,429 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1595326823] [2024-11-16 07:06:16,430 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:06:16,430 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2096898145] [2024-11-16 07:06:16,430 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2096898145] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:06:16,430 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:06:16,430 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 23 [2024-11-16 07:06:16,430 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [63034769] [2024-11-16 07:06:16,430 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:06:16,430 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-16 07:06:16,431 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:06:16,431 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-16 07:06:16,431 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=426, Unknown=0, NotChecked=0, Total=506 [2024-11-16 07:06:16,432 INFO L87 Difference]: Start difference. First operand 912 states and 1359 transitions. Second operand has 23 states, 23 states have (on average 3.0434782608695654) internal successors, (70), 20 states have internal predecessors, (70), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-16 07:06:25,018 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:06:25,018 INFO L93 Difference]: Finished difference Result 1262 states and 1879 transitions. [2024-11-16 07:06:25,019 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2024-11-16 07:06:25,019 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 3.0434782608695654) internal successors, (70), 20 states have internal predecessors, (70), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 99 [2024-11-16 07:06:25,019 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:06:25,025 INFO L225 Difference]: With dead ends: 1262 [2024-11-16 07:06:25,025 INFO L226 Difference]: Without dead ends: 1259 [2024-11-16 07:06:25,027 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 233 GetRequests, 175 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 766 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=711, Invalid=2829, Unknown=0, NotChecked=0, Total=3540 [2024-11-16 07:06:25,027 INFO L432 NwaCegarLoop]: 64 mSDtfsCounter, 218 mSDsluCounter, 758 mSDsCounter, 0 mSdLazyCounter, 895 mSolverCounterSat, 171 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 218 SdHoareTripleChecker+Valid, 822 SdHoareTripleChecker+Invalid, 1066 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 171 IncrementalHoareTripleChecker+Valid, 895 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.5s IncrementalHoareTripleChecker+Time [2024-11-16 07:06:25,027 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [218 Valid, 822 Invalid, 1066 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [171 Valid, 895 Invalid, 0 Unknown, 0 Unchecked, 3.5s Time] [2024-11-16 07:06:25,029 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1259 states. [2024-11-16 07:06:25,645 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1259 to 1157. [2024-11-16 07:06:25,647 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1157 states, 670 states have (on average 1.2223880597014924) internal successors, (819), 671 states have internal predecessors, (819), 457 states have call successors, (457), 29 states have call predecessors, (457), 29 states have return successors, (456), 456 states have call predecessors, (456), 456 states have call successors, (456) [2024-11-16 07:06:25,651 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1732 transitions. [2024-11-16 07:06:25,653 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1732 transitions. Word has length 99 [2024-11-16 07:06:25,653 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:06:25,653 INFO L471 AbstractCegarLoop]: Abstraction has 1157 states and 1732 transitions. [2024-11-16 07:06:25,653 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 3.0434782608695654) internal successors, (70), 20 states have internal predecessors, (70), 8 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-16 07:06:25,654 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1732 transitions. [2024-11-16 07:06:25,655 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2024-11-16 07:06:25,655 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:06:25,655 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:06:25,673 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-11-16 07:06:25,859 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable17,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:06:25,860 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:06:25,860 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:06:25,860 INFO L85 PathProgramCache]: Analyzing trace with hash -117331861, now seen corresponding path program 2 times [2024-11-16 07:06:25,860 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:06:25,860 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [821709247] [2024-11-16 07:06:25,860 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:06:25,860 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:06:25,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:26,047 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-16 07:06:26,048 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:26,049 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-16 07:06:26,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:26,051 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-16 07:06:26,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:26,055 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-16 07:06:26,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:26,057 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2024-11-16 07:06:26,058 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:26,060 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2024-11-16 07:06:26,061 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:26,063 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2024-11-16 07:06:26,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:26,067 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-11-16 07:06:26,068 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:26,069 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 73 [2024-11-16 07:06:26,070 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:26,072 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-11-16 07:06:26,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:26,074 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-11-16 07:06:26,075 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:26,077 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 88 [2024-11-16 07:06:26,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:06:26,080 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 48 proven. 21 refuted. 0 times theorem prover too weak. 142 trivial. 0 not checked. [2024-11-16 07:06:26,080 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:06:26,080 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [821709247] [2024-11-16 07:06:26,080 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [821709247] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:06:26,080 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2014858698] [2024-11-16 07:06:26,080 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 07:06:26,080 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:06:26,081 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:06:26,082 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:06:26,083 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-16 07:06:26,185 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 07:06:26,185 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:06:26,186 INFO L255 TraceCheckSpWp]: Trace formula consists of 253 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-16 07:06:26,187 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:06:26,236 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 48 proven. 21 refuted. 0 times theorem prover too weak. 142 trivial. 0 not checked. [2024-11-16 07:06:26,236 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:06:26,330 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 48 proven. 21 refuted. 0 times theorem prover too weak. 142 trivial. 0 not checked. [2024-11-16 07:06:26,331 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2014858698] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:06:26,331 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 07:06:26,331 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 10] total 11 [2024-11-16 07:06:26,331 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1010471514] [2024-11-16 07:06:26,331 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 07:06:26,331 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-16 07:06:26,331 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:06:26,332 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-16 07:06:26,332 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=89, Unknown=0, NotChecked=0, Total=110 [2024-11-16 07:06:26,332 INFO L87 Difference]: Start difference. First operand 1157 states and 1732 transitions. Second operand has 11 states, 11 states have (on average 4.454545454545454) internal successors, (49), 11 states have internal predecessors, (49), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-16 07:06:27,311 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:06:27,311 INFO L93 Difference]: Finished difference Result 1287 states and 1919 transitions. [2024-11-16 07:06:27,312 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-16 07:06:27,312 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 4.454545454545454) internal successors, (49), 11 states have internal predecessors, (49), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 107 [2024-11-16 07:06:27,312 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:06:27,319 INFO L225 Difference]: With dead ends: 1287 [2024-11-16 07:06:27,319 INFO L226 Difference]: Without dead ends: 1279 [2024-11-16 07:06:27,320 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 266 GetRequests, 235 SyntacticMatches, 8 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 96 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=141, Invalid=459, Unknown=0, NotChecked=0, Total=600 [2024-11-16 07:06:27,320 INFO L432 NwaCegarLoop]: 71 mSDtfsCounter, 86 mSDsluCounter, 415 mSDsCounter, 0 mSdLazyCounter, 254 mSolverCounterSat, 57 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 90 SdHoareTripleChecker+Valid, 486 SdHoareTripleChecker+Invalid, 311 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 57 IncrementalHoareTripleChecker+Valid, 254 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-16 07:06:27,320 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [90 Valid, 486 Invalid, 311 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [57 Valid, 254 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-16 07:06:27,321 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1279 states. [2024-11-16 07:06:28,082 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1279 to 1117. [2024-11-16 07:06:28,084 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1117 states, 638 states have (on average 1.2272727272727273) internal successors, (783), 639 states have internal predecessors, (783), 449 states have call successors, (449), 29 states have call predecessors, (449), 29 states have return successors, (448), 448 states have call predecessors, (448), 448 states have call successors, (448) [2024-11-16 07:06:28,088 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1117 states to 1117 states and 1680 transitions. [2024-11-16 07:06:28,090 INFO L78 Accepts]: Start accepts. Automaton has 1117 states and 1680 transitions. Word has length 107 [2024-11-16 07:06:28,090 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:06:28,090 INFO L471 AbstractCegarLoop]: Abstraction has 1117 states and 1680 transitions. [2024-11-16 07:06:28,090 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 4.454545454545454) internal successors, (49), 11 states have internal predecessors, (49), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-16 07:06:28,090 INFO L276 IsEmpty]: Start isEmpty. Operand 1117 states and 1680 transitions. [2024-11-16 07:06:28,091 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2024-11-16 07:06:28,091 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:06:28,091 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:06:28,097 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-16 07:06:28,291 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:06:28,292 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:06:28,292 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:06:28,292 INFO L85 PathProgramCache]: Analyzing trace with hash 1115104424, now seen corresponding path program 2 times [2024-11-16 07:06:28,292 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:06:28,292 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1888284964] [2024-11-16 07:06:28,292 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:06:28,293 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:06:28,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:06:28,311 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [85444896] [2024-11-16 07:06:28,311 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 07:06:28,311 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:06:28,312 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:06:28,313 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:06:28,315 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-16 07:06:28,403 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 07:06:28,403 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:06:28,404 INFO L255 TraceCheckSpWp]: Trace formula consists of 245 conjuncts, 49 conjuncts are in the unsatisfiable core [2024-11-16 07:06:28,406 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:06:29,001 INFO L134 CoverageAnalysis]: Checked inductivity of 339 backedges. 24 proven. 27 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-16 07:06:29,001 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:06:30,307 INFO L134 CoverageAnalysis]: Checked inductivity of 339 backedges. 24 proven. 27 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-16 07:06:30,308 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:06:30,308 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1888284964] [2024-11-16 07:06:30,308 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:06:30,308 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [85444896] [2024-11-16 07:06:30,308 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [85444896] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:06:30,308 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:06:30,308 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 20 [2024-11-16 07:06:30,308 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [374466781] [2024-11-16 07:06:30,308 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:06:30,309 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-16 07:06:30,309 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:06:30,310 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-16 07:06:30,310 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2024-11-16 07:06:30,310 INFO L87 Difference]: Start difference. First operand 1117 states and 1680 transitions. Second operand has 20 states, 18 states have (on average 3.388888888888889) internal successors, (61), 19 states have internal predecessors, (61), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-16 07:06:37,632 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:06:37,632 INFO L93 Difference]: Finished difference Result 1448 states and 2168 transitions. [2024-11-16 07:06:37,632 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2024-11-16 07:06:37,633 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 3.388888888888889) internal successors, (61), 19 states have internal predecessors, (61), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 112 [2024-11-16 07:06:37,633 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:06:37,640 INFO L225 Difference]: With dead ends: 1448 [2024-11-16 07:06:37,640 INFO L226 Difference]: Without dead ends: 1439 [2024-11-16 07:06:37,642 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 265 GetRequests, 202 SyntacticMatches, 2 SemanticMatches, 61 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 965 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=778, Invalid=3128, Unknown=0, NotChecked=0, Total=3906 [2024-11-16 07:06:37,642 INFO L432 NwaCegarLoop]: 81 mSDtfsCounter, 219 mSDsluCounter, 753 mSDsCounter, 0 mSdLazyCounter, 889 mSolverCounterSat, 166 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 231 SdHoareTripleChecker+Valid, 834 SdHoareTripleChecker+Invalid, 1055 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 166 IncrementalHoareTripleChecker+Valid, 889 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.9s IncrementalHoareTripleChecker+Time [2024-11-16 07:06:37,642 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [231 Valid, 834 Invalid, 1055 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [166 Valid, 889 Invalid, 0 Unknown, 0 Unchecked, 2.9s Time] [2024-11-16 07:06:37,644 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1439 states. [2024-11-16 07:06:38,398 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1439 to 1304. [2024-11-16 07:06:38,400 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1304 states, 756 states have (on average 1.2248677248677249) internal successors, (926), 757 states have internal predecessors, (926), 513 states have call successors, (513), 34 states have call predecessors, (513), 34 states have return successors, (512), 512 states have call predecessors, (512), 512 states have call successors, (512) [2024-11-16 07:06:38,405 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1304 states to 1304 states and 1951 transitions. [2024-11-16 07:06:38,407 INFO L78 Accepts]: Start accepts. Automaton has 1304 states and 1951 transitions. Word has length 112 [2024-11-16 07:06:38,408 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:06:38,410 INFO L471 AbstractCegarLoop]: Abstraction has 1304 states and 1951 transitions. [2024-11-16 07:06:38,410 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 3.388888888888889) internal successors, (61), 19 states have internal predecessors, (61), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-16 07:06:38,410 INFO L276 IsEmpty]: Start isEmpty. Operand 1304 states and 1951 transitions. [2024-11-16 07:06:38,411 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2024-11-16 07:06:38,411 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:06:38,411 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 5, 5, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:06:38,420 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-11-16 07:06:38,612 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:06:38,612 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:06:38,612 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:06:38,612 INFO L85 PathProgramCache]: Analyzing trace with hash -229300873, now seen corresponding path program 4 times [2024-11-16 07:06:38,613 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:06:38,613 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [989076339] [2024-11-16 07:06:38,613 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:06:38,613 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:06:38,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:06:38,633 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1512490742] [2024-11-16 07:06:38,633 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-16 07:06:38,633 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:06:38,634 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:06:38,635 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:06:38,637 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-16 07:06:38,706 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-16 07:06:38,707 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:06:38,710 INFO L255 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 60 conjuncts are in the unsatisfiable core [2024-11-16 07:06:38,712 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:06:39,676 INFO L134 CoverageAnalysis]: Checked inductivity of 242 backedges. 32 proven. 66 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2024-11-16 07:06:39,677 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:06:42,198 INFO L134 CoverageAnalysis]: Checked inductivity of 242 backedges. 48 proven. 50 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2024-11-16 07:06:42,198 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:06:42,198 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [989076339] [2024-11-16 07:06:42,198 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:06:42,198 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1512490742] [2024-11-16 07:06:42,198 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1512490742] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:06:42,198 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:06:42,199 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 31 [2024-11-16 07:06:42,199 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [488776336] [2024-11-16 07:06:42,199 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:06:42,199 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2024-11-16 07:06:42,199 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:06:42,200 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2024-11-16 07:06:42,200 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=133, Invalid=797, Unknown=0, NotChecked=0, Total=930 [2024-11-16 07:06:42,200 INFO L87 Difference]: Start difference. First operand 1304 states and 1951 transitions. Second operand has 31 states, 31 states have (on average 2.967741935483871) internal successors, (92), 28 states have internal predecessors, (92), 9 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) [2024-11-16 07:06:48,079 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:06:48,080 INFO L93 Difference]: Finished difference Result 1489 states and 2186 transitions. [2024-11-16 07:06:48,080 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2024-11-16 07:06:48,080 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 31 states have (on average 2.967741935483871) internal successors, (92), 28 states have internal predecessors, (92), 9 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) Word has length 110 [2024-11-16 07:06:48,081 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:06:48,088 INFO L225 Difference]: With dead ends: 1489 [2024-11-16 07:06:48,088 INFO L226 Difference]: Without dead ends: 1486 [2024-11-16 07:06:48,089 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 247 GetRequests, 187 SyntacticMatches, 2 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 672 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=656, Invalid=2884, Unknown=0, NotChecked=0, Total=3540 [2024-11-16 07:06:48,090 INFO L432 NwaCegarLoop]: 57 mSDtfsCounter, 198 mSDsluCounter, 777 mSDsCounter, 0 mSdLazyCounter, 705 mSolverCounterSat, 166 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 198 SdHoareTripleChecker+Valid, 834 SdHoareTripleChecker+Invalid, 871 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 166 IncrementalHoareTripleChecker+Valid, 705 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:06:48,090 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [198 Valid, 834 Invalid, 871 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [166 Valid, 705 Invalid, 0 Unknown, 0 Unchecked, 2.1s Time] [2024-11-16 07:06:48,091 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1486 states. [2024-11-16 07:06:49,007 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1486 to 1366. [2024-11-16 07:06:49,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1366 states, 806 states have (on average 1.2133995037220844) internal successors, (978), 809 states have internal predecessors, (978), 517 states have call successors, (517), 42 states have call predecessors, (517), 42 states have return successors, (516), 514 states have call predecessors, (516), 516 states have call successors, (516) [2024-11-16 07:06:49,013 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1366 states to 1366 states and 2011 transitions. [2024-11-16 07:06:49,015 INFO L78 Accepts]: Start accepts. Automaton has 1366 states and 2011 transitions. Word has length 110 [2024-11-16 07:06:49,016 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:06:49,016 INFO L471 AbstractCegarLoop]: Abstraction has 1366 states and 2011 transitions. [2024-11-16 07:06:49,016 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 31 states have (on average 2.967741935483871) internal successors, (92), 28 states have internal predecessors, (92), 9 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) [2024-11-16 07:06:49,016 INFO L276 IsEmpty]: Start isEmpty. Operand 1366 states and 2011 transitions. [2024-11-16 07:06:49,018 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2024-11-16 07:06:49,018 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:06:49,018 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:06:49,036 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2024-11-16 07:06:49,219 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:06:49,219 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:06:49,219 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:06:49,219 INFO L85 PathProgramCache]: Analyzing trace with hash -330692873, now seen corresponding path program 3 times [2024-11-16 07:06:49,219 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:06:49,220 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1029392940] [2024-11-16 07:06:49,220 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:06:49,220 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:06:49,244 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:06:49,245 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [970786003] [2024-11-16 07:06:49,245 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-16 07:06:49,245 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:06:49,245 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:06:49,248 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:06:49,249 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-16 07:06:49,329 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-11-16 07:06:49,329 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:06:49,330 INFO L255 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 53 conjuncts are in the unsatisfiable core [2024-11-16 07:06:49,332 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:06:50,019 INFO L134 CoverageAnalysis]: Checked inductivity of 346 backedges. 24 proven. 34 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-16 07:06:50,019 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:06:51,633 INFO L134 CoverageAnalysis]: Checked inductivity of 346 backedges. 24 proven. 34 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-16 07:06:51,633 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:06:51,633 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1029392940] [2024-11-16 07:06:51,634 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:06:51,634 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [970786003] [2024-11-16 07:06:51,634 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [970786003] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:06:51,634 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:06:51,634 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2024-11-16 07:06:51,634 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [130295247] [2024-11-16 07:06:51,634 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:06:51,634 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-16 07:06:51,634 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:06:51,635 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-16 07:06:51,635 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=384, Unknown=0, NotChecked=0, Total=462 [2024-11-16 07:06:51,635 INFO L87 Difference]: Start difference. First operand 1366 states and 2011 transitions. Second operand has 22 states, 20 states have (on average 3.45) internal successors, (69), 21 states have internal predecessors, (69), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-16 07:06:57,629 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:06:57,629 INFO L93 Difference]: Finished difference Result 1701 states and 2500 transitions. [2024-11-16 07:06:57,630 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2024-11-16 07:06:57,630 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 3.45) internal successors, (69), 21 states have internal predecessors, (69), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) Word has length 116 [2024-11-16 07:06:57,630 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:06:57,639 INFO L225 Difference]: With dead ends: 1701 [2024-11-16 07:06:57,639 INFO L226 Difference]: Without dead ends: 1692 [2024-11-16 07:06:57,640 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 263 GetRequests, 208 SyntacticMatches, 2 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 649 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=579, Invalid=2391, Unknown=0, NotChecked=0, Total=2970 [2024-11-16 07:06:57,641 INFO L432 NwaCegarLoop]: 69 mSDtfsCounter, 285 mSDsluCounter, 744 mSDsCounter, 0 mSdLazyCounter, 850 mSolverCounterSat, 216 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 297 SdHoareTripleChecker+Valid, 813 SdHoareTripleChecker+Invalid, 1066 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 216 IncrementalHoareTripleChecker+Valid, 850 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.9s IncrementalHoareTripleChecker+Time [2024-11-16 07:06:57,641 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [297 Valid, 813 Invalid, 1066 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [216 Valid, 850 Invalid, 0 Unknown, 0 Unchecked, 2.9s Time] [2024-11-16 07:06:57,642 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1692 states. [2024-11-16 07:06:58,627 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1692 to 1485. [2024-11-16 07:06:58,629 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1485 states, 873 states have (on average 1.2130584192439862) internal successors, (1059), 876 states have internal predecessors, (1059), 565 states have call successors, (565), 46 states have call predecessors, (565), 46 states have return successors, (564), 562 states have call predecessors, (564), 564 states have call successors, (564) [2024-11-16 07:06:58,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1485 states to 1485 states and 2188 transitions. [2024-11-16 07:06:58,637 INFO L78 Accepts]: Start accepts. Automaton has 1485 states and 2188 transitions. Word has length 116 [2024-11-16 07:06:58,637 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:06:58,637 INFO L471 AbstractCegarLoop]: Abstraction has 1485 states and 2188 transitions. [2024-11-16 07:06:58,637 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 3.45) internal successors, (69), 21 states have internal predecessors, (69), 9 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (28), 7 states have call predecessors, (28), 7 states have call successors, (28) [2024-11-16 07:06:58,638 INFO L276 IsEmpty]: Start isEmpty. Operand 1485 states and 2188 transitions. [2024-11-16 07:06:58,640 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2024-11-16 07:06:58,640 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:06:58,640 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:06:58,647 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2024-11-16 07:06:58,841 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:06:58,841 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:06:58,841 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:06:58,841 INFO L85 PathProgramCache]: Analyzing trace with hash -1458173243, now seen corresponding path program 4 times [2024-11-16 07:06:58,842 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:06:58,842 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1271536662] [2024-11-16 07:06:58,842 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:06:58,842 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:06:58,877 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:06:58,878 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1168496086] [2024-11-16 07:06:58,878 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-16 07:06:58,878 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:06:58,879 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:06:58,880 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:06:58,882 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2024-11-16 07:06:58,968 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-16 07:06:58,968 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:06:58,970 INFO L255 TraceCheckSpWp]: Trace formula consists of 243 conjuncts, 74 conjuncts are in the unsatisfiable core [2024-11-16 07:06:58,975 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:07:00,635 INFO L134 CoverageAnalysis]: Checked inductivity of 362 backedges. 56 proven. 60 refuted. 0 times theorem prover too weak. 246 trivial. 0 not checked. [2024-11-16 07:07:00,635 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:07:05,317 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:07:05,317 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1271536662] [2024-11-16 07:07:05,317 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:07:05,317 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1168496086] [2024-11-16 07:07:05,317 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1168496086] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:07:05,317 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-16 07:07:05,317 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2024-11-16 07:07:05,318 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1185232698] [2024-11-16 07:07:05,318 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-16 07:07:05,318 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-16 07:07:05,318 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:07:05,318 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-16 07:07:05,319 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=172, Invalid=1160, Unknown=0, NotChecked=0, Total=1332 [2024-11-16 07:07:05,319 INFO L87 Difference]: Start difference. First operand 1485 states and 2188 transitions. Second operand has 23 states, 22 states have (on average 2.4545454545454546) internal successors, (54), 21 states have internal predecessors, (54), 7 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-16 07:07:07,675 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:07:07,675 INFO L93 Difference]: Finished difference Result 1635 states and 2405 transitions. [2024-11-16 07:07:07,676 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-11-16 07:07:07,676 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 22 states have (on average 2.4545454545454546) internal successors, (54), 21 states have internal predecessors, (54), 7 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 123 [2024-11-16 07:07:07,676 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:07:07,683 INFO L225 Difference]: With dead ends: 1635 [2024-11-16 07:07:07,683 INFO L226 Difference]: Without dead ends: 1627 [2024-11-16 07:07:07,685 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 159 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 514 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=313, Invalid=1943, Unknown=0, NotChecked=0, Total=2256 [2024-11-16 07:07:07,685 INFO L432 NwaCegarLoop]: 64 mSDtfsCounter, 106 mSDsluCounter, 708 mSDsCounter, 0 mSdLazyCounter, 986 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 122 SdHoareTripleChecker+Valid, 772 SdHoareTripleChecker+Invalid, 1036 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 986 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-16 07:07:07,685 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [122 Valid, 772 Invalid, 1036 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 986 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-16 07:07:07,686 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1627 states. [2024-11-16 07:07:08,782 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1627 to 1603. [2024-11-16 07:07:08,784 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1603 states, 934 states have (on average 1.2162740899357602) internal successors, (1136), 936 states have internal predecessors, (1136), 619 states have call successors, (619), 49 states have call predecessors, (619), 49 states have return successors, (618), 617 states have call predecessors, (618), 618 states have call successors, (618) [2024-11-16 07:07:08,787 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1603 states to 1603 states and 2373 transitions. [2024-11-16 07:07:08,788 INFO L78 Accepts]: Start accepts. Automaton has 1603 states and 2373 transitions. Word has length 123 [2024-11-16 07:07:08,788 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:07:08,788 INFO L471 AbstractCegarLoop]: Abstraction has 1603 states and 2373 transitions. [2024-11-16 07:07:08,788 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 22 states have (on average 2.4545454545454546) internal successors, (54), 21 states have internal predecessors, (54), 7 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-16 07:07:08,789 INFO L276 IsEmpty]: Start isEmpty. Operand 1603 states and 2373 transitions. [2024-11-16 07:07:08,790 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2024-11-16 07:07:08,790 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:07:08,790 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:07:08,802 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2024-11-16 07:07:08,990 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable22,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:07:08,991 INFO L396 AbstractCegarLoop]: === Iteration 24 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:07:08,991 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:07:08,991 INFO L85 PathProgramCache]: Analyzing trace with hash 1671777728, now seen corresponding path program 2 times [2024-11-16 07:07:08,991 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:07:08,991 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [828042553] [2024-11-16 07:07:08,991 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:07:08,991 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:07:09,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:07:09,010 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1472989127] [2024-11-16 07:07:09,011 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 07:07:09,011 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:07:09,011 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:07:09,013 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:07:09,015 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2024-11-16 07:07:09,088 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 07:07:09,089 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:07:09,090 INFO L255 TraceCheckSpWp]: Trace formula consists of 288 conjuncts, 71 conjuncts are in the unsatisfiable core [2024-11-16 07:07:09,096 INFO L278 TraceCheckSpWp]: Computing forward predicates...