/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-05ce600 [2022-02-23 23:22:23,987 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-02-23 23:22:24,000 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-02-23 23:22:24,046 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-02-23 23:22:24,047 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-02-23 23:22:24,049 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-02-23 23:22:24,051 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-02-23 23:22:24,056 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-02-23 23:22:24,058 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-02-23 23:22:24,062 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-02-23 23:22:24,063 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-02-23 23:22:24,063 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-02-23 23:22:24,064 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-02-23 23:22:24,064 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-02-23 23:22:24,065 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-02-23 23:22:24,065 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-02-23 23:22:24,066 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-02-23 23:22:24,066 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-02-23 23:22:24,067 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-02-23 23:22:24,068 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-02-23 23:22:24,069 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-02-23 23:22:24,070 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-02-23 23:22:24,071 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-02-23 23:22:24,071 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-02-23 23:22:24,073 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-02-23 23:22:24,073 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-02-23 23:22:24,074 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-02-23 23:22:24,074 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-02-23 23:22:24,075 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-02-23 23:22:24,075 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-02-23 23:22:24,076 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-02-23 23:22:24,076 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-02-23 23:22:24,077 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-02-23 23:22:24,077 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-02-23 23:22:24,078 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-02-23 23:22:24,079 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-02-23 23:22:24,079 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-02-23 23:22:24,079 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-02-23 23:22:24,080 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-02-23 23:22:24,080 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-02-23 23:22:24,081 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-02-23 23:22:24,083 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-02-23 23:22:24,128 INFO L113 SettingsManager]: Loading preferences was successful [2022-02-23 23:22:24,129 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-02-23 23:22:24,129 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-02-23 23:22:24,129 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-02-23 23:22:24,130 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-02-23 23:22:24,130 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-02-23 23:22:24,130 INFO L138 SettingsManager]: * Use SBE=true [2022-02-23 23:22:24,130 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-02-23 23:22:24,130 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-02-23 23:22:24,130 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-02-23 23:22:24,131 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-02-23 23:22:24,131 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-02-23 23:22:24,131 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-02-23 23:22:24,131 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-02-23 23:22:24,131 INFO L138 SettingsManager]: * Use constant arrays=true [2022-02-23 23:22:24,131 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-02-23 23:22:24,131 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-02-23 23:22:24,131 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-02-23 23:22:24,132 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-02-23 23:22:24,132 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-02-23 23:22:24,132 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-02-23 23:22:24,132 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-02-23 23:22:24,132 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-02-23 23:22:24,132 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-02-23 23:22:24,132 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-02-23 23:22:24,133 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-02-23 23:22:24,133 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-02-23 23:22:24,133 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-02-23 23:22:24,133 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-02-23 23:22:24,134 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_QVASR 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.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-02-23 23:22:24,313 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-02-23 23:22:24,330 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-02-23 23:22:24,332 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-02-23 23:22:24,333 INFO L271 PluginConnector]: Initializing CDTParser... [2022-02-23 23:22:24,336 INFO L275 PluginConnector]: CDTParser initialized [2022-02-23 23:22:24,336 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound20.c [2022-02-23 23:22:24,382 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b3089b58c/c37221c26aad4df78fb973f2248715bc/FLAG971445ef0 [2022-02-23 23:22:24,745 INFO L306 CDTParser]: Found 1 translation units. [2022-02-23 23:22:24,745 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound20.c [2022-02-23 23:22:24,752 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b3089b58c/c37221c26aad4df78fb973f2248715bc/FLAG971445ef0 [2022-02-23 23:22:24,762 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b3089b58c/c37221c26aad4df78fb973f2248715bc [2022-02-23 23:22:24,764 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-02-23 23:22:24,764 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-02-23 23:22:24,766 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-02-23 23:22:24,766 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-02-23 23:22:24,768 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-02-23 23:22:24,768 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.02 11:22:24" (1/1) ... [2022-02-23 23:22:24,769 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@591ac366 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 11:22:24, skipping insertion in model container [2022-02-23 23:22:24,769 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.02 11:22:24" (1/1) ... [2022-02-23 23:22:24,773 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-02-23 23:22:24,783 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-02-23 23:22:24,890 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound20.c[526,539] [2022-02-23 23:22:24,912 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-02-23 23:22:24,918 INFO L203 MainTranslator]: Completed pre-run [2022-02-23 23:22:24,936 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_unwindbound20.c[526,539] [2022-02-23 23:22:24,951 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-02-23 23:22:24,960 INFO L208 MainTranslator]: Completed translation [2022-02-23 23:22:24,960 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 11:22:24 WrapperNode [2022-02-23 23:22:24,961 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-02-23 23:22:24,961 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-02-23 23:22:24,961 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-02-23 23:22:24,962 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-02-23 23:22:24,969 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 11:22:24" (1/1) ... [2022-02-23 23:22:24,969 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 11:22:24" (1/1) ... [2022-02-23 23:22:24,973 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 11:22:24" (1/1) ... [2022-02-23 23:22:24,973 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 11:22:24" (1/1) ... [2022-02-23 23:22:24,976 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 11:22:24" (1/1) ... [2022-02-23 23:22:24,979 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 11:22:24" (1/1) ... [2022-02-23 23:22:24,980 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 11:22:24" (1/1) ... [2022-02-23 23:22:24,981 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-02-23 23:22:24,982 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-02-23 23:22:24,982 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-02-23 23:22:24,982 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-02-23 23:22:24,983 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 11:22:24" (1/1) ... [2022-02-23 23:22:24,987 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-02-23 23:22:24,994 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:22:25,003 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-02-23 23:22:25,008 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-02-23 23:22:25,032 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-02-23 23:22:25,032 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-02-23 23:22:25,033 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-02-23 23:22:25,033 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-02-23 23:22:25,033 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-02-23 23:22:25,033 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-02-23 23:22:25,033 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-02-23 23:22:25,033 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-02-23 23:22:25,033 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-02-23 23:22:25,034 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-02-23 23:22:25,034 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-02-23 23:22:25,034 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-02-23 23:22:25,034 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-02-23 23:22:25,034 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-02-23 23:22:25,034 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-02-23 23:22:25,034 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-02-23 23:22:25,034 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-02-23 23:22:25,034 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-02-23 23:22:25,035 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-02-23 23:22:25,035 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-02-23 23:22:25,077 INFO L234 CfgBuilder]: Building ICFG [2022-02-23 23:22:25,078 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-02-23 23:22:25,221 INFO L275 CfgBuilder]: Performing block encoding [2022-02-23 23:22:25,226 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-02-23 23:22:25,226 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-02-23 23:22:25,227 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 11:22:25 BoogieIcfgContainer [2022-02-23 23:22:25,227 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-02-23 23:22:25,228 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-02-23 23:22:25,228 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-02-23 23:22:25,229 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-02-23 23:22:25,231 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 11:22:25" (1/1) ... [2022-02-23 23:22:25,253 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 23.02 11:22:25 BasicIcfg [2022-02-23 23:22:25,254 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-02-23 23:22:25,255 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-02-23 23:22:25,255 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-02-23 23:22:25,256 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-02-23 23:22:25,257 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.02 11:22:24" (1/4) ... [2022-02-23 23:22:25,257 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4f992078 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.02 11:22:25, skipping insertion in model container [2022-02-23 23:22:25,257 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 11:22:24" (2/4) ... [2022-02-23 23:22:25,257 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4f992078 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.02 11:22:25, skipping insertion in model container [2022-02-23 23:22:25,257 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 11:22:25" (3/4) ... [2022-02-23 23:22:25,258 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4f992078 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.02 11:22:25, skipping insertion in model container [2022-02-23 23:22:25,258 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 23.02 11:22:25" (4/4) ... [2022-02-23 23:22:25,258 INFO L111 eAbstractionObserver]: Analyzing ICFG hard2_unwindbound20.cqvasr [2022-02-23 23:22:25,270 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-02-23 23:22:25,270 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-02-23 23:22:25,310 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-02-23 23:22:25,316 INFO L339 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, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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, mLoopAccelerationTechnique=FAST_UPR [2022-02-23 23:22:25,317 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-02-23 23:22:25,335 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-02-23 23:22:25,338 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-02-23 23:22:25,338 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:25,338 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:22:25,339 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:25,343 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:25,343 INFO L85 PathProgramCache]: Analyzing trace with hash 121155216, now seen corresponding path program 1 times [2022-02-23 23:22:25,349 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:25,350 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1011520168] [2022-02-23 23:22:25,350 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:25,351 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:25,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:25,497 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-02-23 23:22:25,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:25,508 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-23 23:22:25,509 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:25,509 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1011520168] [2022-02-23 23:22:25,509 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1011520168] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 23:22:25,510 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 23:22:25,510 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-02-23 23:22:25,511 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1856728095] [2022-02-23 23:22:25,511 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 23:22:25,514 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-02-23 23:22:25,514 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:25,534 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-02-23 23:22:25,535 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-02-23 23:22:25,536 INFO L87 Difference]: Start difference. First operand has 31 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-23 23:22:25,591 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:22:25,592 INFO L93 Difference]: Finished difference Result 57 states and 91 transitions. [2022-02-23 23:22:25,593 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-02-23 23:22:25,594 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-02-23 23:22:25,594 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:22:25,598 INFO L225 Difference]: With dead ends: 57 [2022-02-23 23:22:25,598 INFO L226 Difference]: Without dead ends: 27 [2022-02-23 23:22:25,600 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-02-23 23:22:25,603 INFO L933 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 23:22:25,603 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 44 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 23:22:25,613 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-02-23 23:22:25,624 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-02-23 23:22:25,625 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 9 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-02-23 23:22:25,626 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 36 transitions. [2022-02-23 23:22:25,627 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 36 transitions. Word has length 12 [2022-02-23 23:22:25,627 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:22:25,627 INFO L470 AbstractCegarLoop]: Abstraction has 26 states and 36 transitions. [2022-02-23 23:22:25,627 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-23 23:22:25,627 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 36 transitions. [2022-02-23 23:22:25,628 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-02-23 23:22:25,628 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:25,628 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:22:25,628 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-02-23 23:22:25,628 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:25,629 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:25,629 INFO L85 PathProgramCache]: Analyzing trace with hash 152644303, now seen corresponding path program 1 times [2022-02-23 23:22:25,629 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:25,629 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [46344919] [2022-02-23 23:22:25,629 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:25,629 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:25,643 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:25,681 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-02-23 23:22:25,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:25,696 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-23 23:22:25,696 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:25,696 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [46344919] [2022-02-23 23:22:25,697 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [46344919] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 23:22:25,697 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 23:22:25,697 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-02-23 23:22:25,697 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [774900423] [2022-02-23 23:22:25,697 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 23:22:25,698 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-02-23 23:22:25,698 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:25,698 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-02-23 23:22:25,699 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-02-23 23:22:25,699 INFO L87 Difference]: Start difference. First operand 26 states and 36 transitions. Second operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-23 23:22:25,854 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:22:25,854 INFO L93 Difference]: Finished difference Result 41 states and 56 transitions. [2022-02-23 23:22:25,854 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-02-23 23:22:25,854 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-02-23 23:22:25,855 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:22:25,855 INFO L225 Difference]: With dead ends: 41 [2022-02-23 23:22:25,855 INFO L226 Difference]: Without dead ends: 39 [2022-02-23 23:22:25,856 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-02-23 23:22:25,857 INFO L933 BasicCegarLoop]: 34 mSDtfsCounter, 24 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 87 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 23:22:25,857 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 91 Invalid, 87 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 23:22:25,858 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-02-23 23:22:25,862 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 30. [2022-02-23 23:22:25,863 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-02-23 23:22:25,863 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2022-02-23 23:22:25,863 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 12 [2022-02-23 23:22:25,864 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:22:25,864 INFO L470 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2022-02-23 23:22:25,864 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-23 23:22:25,864 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2022-02-23 23:22:25,864 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-02-23 23:22:25,864 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:25,865 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:22:25,865 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-02-23 23:22:25,865 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:25,865 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:25,865 INFO L85 PathProgramCache]: Analyzing trace with hash -400958603, now seen corresponding path program 1 times [2022-02-23 23:22:25,865 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:25,866 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1194333615] [2022-02-23 23:22:25,866 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:25,866 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:25,873 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:25,905 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-02-23 23:22:25,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:25,918 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-23 23:22:25,919 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:25,936 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1194333615] [2022-02-23 23:22:25,937 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1194333615] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 23:22:25,937 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 23:22:25,937 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-02-23 23:22:25,937 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [700464604] [2022-02-23 23:22:25,937 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 23:22:25,937 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 23:22:25,938 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:25,938 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 23:22:25,938 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-02-23 23:22:25,938 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-23 23:22:25,986 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:22:25,986 INFO L93 Difference]: Finished difference Result 46 states and 61 transitions. [2022-02-23 23:22:25,987 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-02-23 23:22:25,987 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-02-23 23:22:25,987 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:22:25,988 INFO L225 Difference]: With dead ends: 46 [2022-02-23 23:22:25,988 INFO L226 Difference]: Without dead ends: 32 [2022-02-23 23:22:25,988 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-02-23 23:22:25,989 INFO L933 BasicCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 23:22:25,989 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 73 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 23:22:25,990 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-02-23 23:22:25,993 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-02-23 23:22:25,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-02-23 23:22:25,994 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2022-02-23 23:22:25,994 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 14 [2022-02-23 23:22:25,994 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:22:25,994 INFO L470 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2022-02-23 23:22:25,995 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-23 23:22:25,995 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-02-23 23:22:25,995 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-02-23 23:22:25,995 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:25,995 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:22:25,995 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-02-23 23:22:25,996 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:25,996 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:25,996 INFO L85 PathProgramCache]: Analyzing trace with hash 185978583, now seen corresponding path program 1 times [2022-02-23 23:22:25,996 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:25,996 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [986910673] [2022-02-23 23:22:25,996 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:25,997 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:26,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:26,030 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-02-23 23:22:26,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:26,036 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-02-23 23:22:26,037 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:26,040 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-23 23:22:26,040 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:26,040 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [986910673] [2022-02-23 23:22:26,040 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [986910673] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 23:22:26,040 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 23:22:26,041 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-02-23 23:22:26,041 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1972988397] [2022-02-23 23:22:26,041 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 23:22:26,041 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-02-23 23:22:26,041 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:26,042 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-02-23 23:22:26,042 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-02-23 23:22:26,042 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-02-23 23:22:26,132 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:22:26,133 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-02-23 23:22:26,133 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-02-23 23:22:26,133 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2022-02-23 23:22:26,133 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:22:26,134 INFO L225 Difference]: With dead ends: 46 [2022-02-23 23:22:26,134 INFO L226 Difference]: Without dead ends: 44 [2022-02-23 23:22:26,134 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-02-23 23:22:26,135 INFO L933 BasicCegarLoop]: 34 mSDtfsCounter, 19 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 87 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 100 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 87 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 23:22:26,135 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 84 Invalid, 100 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 87 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 23:22:26,136 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-02-23 23:22:26,140 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 36. [2022-02-23 23:22:26,140 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-02-23 23:22:26,141 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 44 transitions. [2022-02-23 23:22:26,141 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 44 transitions. Word has length 17 [2022-02-23 23:22:26,141 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:22:26,141 INFO L470 AbstractCegarLoop]: Abstraction has 36 states and 44 transitions. [2022-02-23 23:22:26,141 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-02-23 23:22:26,141 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 44 transitions. [2022-02-23 23:22:26,142 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-02-23 23:22:26,142 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:26,142 INFO L514 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:22:26,142 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-02-23 23:22:26,142 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:26,142 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:26,143 INFO L85 PathProgramCache]: Analyzing trace with hash -820589269, now seen corresponding path program 1 times [2022-02-23 23:22:26,143 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:26,143 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [549034252] [2022-02-23 23:22:26,143 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:26,143 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:26,150 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:22:26,151 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [443737300] [2022-02-23 23:22:26,151 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:26,151 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:26,151 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:22:26,152 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) [2022-02-23 23:22:26,153 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-02-23 23:22:26,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:26,187 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 9 conjunts are in the unsatisfiable core [2022-02-23 23:22:26,190 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:22:26,339 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-02-23 23:22:26,340 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 23:22:26,340 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:26,340 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [549034252] [2022-02-23 23:22:26,340 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:22:26,341 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [443737300] [2022-02-23 23:22:26,341 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [443737300] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 23:22:26,343 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 23:22:26,343 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-02-23 23:22:26,347 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [909342317] [2022-02-23 23:22:26,347 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 23:22:26,347 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 23:22:26,347 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:26,348 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 23:22:26,348 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-02-23 23:22:26,348 INFO L87 Difference]: Start difference. First operand 36 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-02-23 23:22:26,388 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:22:26,388 INFO L93 Difference]: Finished difference Result 65 states and 87 transitions. [2022-02-23 23:22:26,388 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 23:22:26,388 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-02-23 23:22:26,389 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:22:26,390 INFO L225 Difference]: With dead ends: 65 [2022-02-23 23:22:26,390 INFO L226 Difference]: Without dead ends: 50 [2022-02-23 23:22:26,390 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-02-23 23:22:26,391 INFO L933 BasicCegarLoop]: 38 mSDtfsCounter, 10 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 23:22:26,391 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 131 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 23:22:26,392 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-02-23 23:22:26,409 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2022-02-23 23:22:26,409 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 29 states have (on average 1.2758620689655173) internal successors, (37), 31 states have internal predecessors, (37), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-02-23 23:22:26,410 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 64 transitions. [2022-02-23 23:22:26,410 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 64 transitions. Word has length 22 [2022-02-23 23:22:26,410 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:22:26,410 INFO L470 AbstractCegarLoop]: Abstraction has 50 states and 64 transitions. [2022-02-23 23:22:26,411 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-02-23 23:22:26,411 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-02-23 23:22:26,411 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-02-23 23:22:26,411 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:26,411 INFO L514 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:22:26,428 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-02-23 23:22:26,612 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:26,612 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:26,612 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:26,613 INFO L85 PathProgramCache]: Analyzing trace with hash 1259710898, now seen corresponding path program 1 times [2022-02-23 23:22:26,613 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:26,613 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [882520793] [2022-02-23 23:22:26,613 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:26,613 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:26,623 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:22:26,623 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [51401962] [2022-02-23 23:22:26,623 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:26,623 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:26,623 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:22:26,624 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) [2022-02-23 23:22:26,625 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-02-23 23:22:26,661 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:26,662 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-02-23 23:22:26,664 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:22:26,734 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-02-23 23:22:26,734 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 23:22:26,734 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:26,734 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [882520793] [2022-02-23 23:22:26,734 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:22:26,734 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [51401962] [2022-02-23 23:22:26,735 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [51401962] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 23:22:26,735 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 23:22:26,735 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-02-23 23:22:26,735 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2111413483] [2022-02-23 23:22:26,735 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 23:22:26,735 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 23:22:26,735 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:26,736 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 23:22:26,736 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-02-23 23:22:26,736 INFO L87 Difference]: Start difference. First operand 50 states and 64 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-02-23 23:22:26,758 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:22:26,758 INFO L93 Difference]: Finished difference Result 70 states and 80 transitions. [2022-02-23 23:22:26,763 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 23:22:26,763 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-02-23 23:22:26,763 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:22:26,764 INFO L225 Difference]: With dead ends: 70 [2022-02-23 23:22:26,764 INFO L226 Difference]: Without dead ends: 63 [2022-02-23 23:22:26,764 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-02-23 23:22:26,765 INFO L933 BasicCegarLoop]: 36 mSDtfsCounter, 3 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 23:22:26,765 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 124 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 23:22:26,766 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-02-23 23:22:26,770 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2022-02-23 23:22:26,770 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-02-23 23:22:26,771 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 72 transitions. [2022-02-23 23:22:26,771 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 72 transitions. Word has length 30 [2022-02-23 23:22:26,771 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:22:26,771 INFO L470 AbstractCegarLoop]: Abstraction has 62 states and 72 transitions. [2022-02-23 23:22:26,771 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-02-23 23:22:26,771 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 72 transitions. [2022-02-23 23:22:26,772 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-02-23 23:22:26,772 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:26,772 INFO L514 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:22:26,790 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-02-23 23:22:26,983 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2022-02-23 23:22:26,984 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:26,984 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:26,984 INFO L85 PathProgramCache]: Analyzing trace with hash 1260813165, now seen corresponding path program 1 times [2022-02-23 23:22:26,984 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:26,984 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1722135026] [2022-02-23 23:22:26,984 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:26,985 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:26,991 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:22:26,991 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [593230784] [2022-02-23 23:22:26,991 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:26,992 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:26,992 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:22:26,993 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) [2022-02-23 23:22:26,994 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-02-23 23:22:27,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:27,029 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 7 conjunts are in the unsatisfiable core [2022-02-23 23:22:27,031 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:22:27,100 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-02-23 23:22:27,101 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 23:22:27,101 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:27,101 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1722135026] [2022-02-23 23:22:27,101 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:22:27,101 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [593230784] [2022-02-23 23:22:27,101 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [593230784] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 23:22:27,101 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 23:22:27,101 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-02-23 23:22:27,101 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1005113024] [2022-02-23 23:22:27,101 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 23:22:27,102 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 23:22:27,102 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:27,102 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 23:22:27,102 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-02-23 23:22:27,102 INFO L87 Difference]: Start difference. First operand 62 states and 72 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-02-23 23:22:27,141 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:22:27,141 INFO L93 Difference]: Finished difference Result 76 states and 91 transitions. [2022-02-23 23:22:27,142 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 23:22:27,142 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-02-23 23:22:27,143 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:22:27,143 INFO L225 Difference]: With dead ends: 76 [2022-02-23 23:22:27,143 INFO L226 Difference]: Without dead ends: 64 [2022-02-23 23:22:27,144 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-02-23 23:22:27,144 INFO L933 BasicCegarLoop]: 29 mSDtfsCounter, 11 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 23:22:27,144 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 103 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 23:22:27,145 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2022-02-23 23:22:27,151 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 63. [2022-02-23 23:22:27,151 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 39 states have (on average 1.2307692307692308) internal successors, (48), 41 states have internal predecessors, (48), 15 states have call successors, (15), 9 states have call predecessors, (15), 8 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-02-23 23:22:27,152 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 76 transitions. [2022-02-23 23:22:27,152 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 76 transitions. Word has length 30 [2022-02-23 23:22:27,152 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:22:27,152 INFO L470 AbstractCegarLoop]: Abstraction has 63 states and 76 transitions. [2022-02-23 23:22:27,152 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-02-23 23:22:27,152 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 76 transitions. [2022-02-23 23:22:27,153 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-02-23 23:22:27,153 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:27,153 INFO L514 BasicCegarLoop]: trace histogram [5, 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] [2022-02-23 23:22:27,176 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-02-23 23:22:27,359 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:27,379 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:27,379 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:27,380 INFO L85 PathProgramCache]: Analyzing trace with hash 1811137592, now seen corresponding path program 1 times [2022-02-23 23:22:27,380 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:27,380 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1270134043] [2022-02-23 23:22:27,380 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:27,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:27,386 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:22:27,386 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1900005468] [2022-02-23 23:22:27,386 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:27,386 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:27,387 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:22:27,387 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) [2022-02-23 23:22:27,388 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-02-23 23:22:27,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:27,423 INFO L263 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 7 conjunts are in the unsatisfiable core [2022-02-23 23:22:27,424 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:22:27,489 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-02-23 23:22:27,490 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:22:27,572 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-02-23 23:22:27,572 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:27,572 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1270134043] [2022-02-23 23:22:27,572 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:22:27,575 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1900005468] [2022-02-23 23:22:27,575 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1900005468] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:22:27,575 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:22:27,575 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-02-23 23:22:27,575 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [387214964] [2022-02-23 23:22:27,575 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:22:27,575 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-02-23 23:22:27,576 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:27,576 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-02-23 23:22:27,576 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-02-23 23:22:27,576 INFO L87 Difference]: Start difference. First operand 63 states and 76 transitions. Second operand has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) [2022-02-23 23:22:27,642 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:22:27,642 INFO L93 Difference]: Finished difference Result 144 states and 177 transitions. [2022-02-23 23:22:27,642 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-02-23 23:22:27,642 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) Word has length 37 [2022-02-23 23:22:27,643 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:22:27,644 INFO L225 Difference]: With dead ends: 144 [2022-02-23 23:22:27,644 INFO L226 Difference]: Without dead ends: 119 [2022-02-23 23:22:27,645 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-02-23 23:22:27,645 INFO L933 BasicCegarLoop]: 45 mSDtfsCounter, 41 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 207 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 23:22:27,645 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 207 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 23:22:27,646 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2022-02-23 23:22:27,653 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 112. [2022-02-23 23:22:27,653 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 112 states, 71 states have (on average 1.2112676056338028) internal successors, (86), 74 states have internal predecessors, (86), 25 states have call successors, (25), 16 states have call predecessors, (25), 15 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2022-02-23 23:22:27,654 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 133 transitions. [2022-02-23 23:22:27,654 INFO L78 Accepts]: Start accepts. Automaton has 112 states and 133 transitions. Word has length 37 [2022-02-23 23:22:27,654 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:22:27,654 INFO L470 AbstractCegarLoop]: Abstraction has 112 states and 133 transitions. [2022-02-23 23:22:27,654 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 6 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (10), 5 states have call predecessors, (10), 4 states have call successors, (10) [2022-02-23 23:22:27,655 INFO L276 IsEmpty]: Start isEmpty. Operand 112 states and 133 transitions. [2022-02-23 23:22:27,655 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-02-23 23:22:27,655 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:27,655 INFO L514 BasicCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:22:27,672 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-02-23 23:22:27,867 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:27,867 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:27,867 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:27,868 INFO L85 PathProgramCache]: Analyzing trace with hash -599722260, now seen corresponding path program 1 times [2022-02-23 23:22:27,868 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:27,868 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [385387600] [2022-02-23 23:22:27,868 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:27,868 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:27,874 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:22:27,874 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [496685135] [2022-02-23 23:22:27,874 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:27,874 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:27,874 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:22:27,875 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) [2022-02-23 23:22:27,876 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-02-23 23:22:27,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:27,912 INFO L263 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 13 conjunts are in the unsatisfiable core [2022-02-23 23:22:27,913 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:22:28,038 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-02-23 23:22:28,038 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:22:28,127 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-02-23 23:22:28,127 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:28,127 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [385387600] [2022-02-23 23:22:28,127 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:22:28,127 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [496685135] [2022-02-23 23:22:28,127 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [496685135] provided 1 perfect and 1 imperfect interpolant sequences [2022-02-23 23:22:28,127 INFO L191 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-02-23 23:22:28,127 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-02-23 23:22:28,128 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1749765926] [2022-02-23 23:22:28,128 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 23:22:28,128 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 23:22:28,128 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:28,128 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 23:22:28,128 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-02-23 23:22:28,128 INFO L87 Difference]: Start difference. First operand 112 states and 133 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-02-23 23:22:28,170 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:22:28,170 INFO L93 Difference]: Finished difference Result 129 states and 154 transitions. [2022-02-23 23:22:28,170 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 23:22:28,170 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 40 [2022-02-23 23:22:28,170 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:22:28,171 INFO L225 Difference]: With dead ends: 129 [2022-02-23 23:22:28,171 INFO L226 Difference]: Without dead ends: 125 [2022-02-23 23:22:28,172 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 72 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-02-23 23:22:28,172 INFO L933 BasicCegarLoop]: 34 mSDtfsCounter, 11 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 23:22:28,172 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 113 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 23:22:28,173 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2022-02-23 23:22:28,180 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 122. [2022-02-23 23:22:28,180 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 78 states have (on average 1.1794871794871795) internal successors, (92), 81 states have internal predecessors, (92), 27 states have call successors, (27), 18 states have call predecessors, (27), 16 states have return successors, (24), 22 states have call predecessors, (24), 24 states have call successors, (24) [2022-02-23 23:22:28,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 143 transitions. [2022-02-23 23:22:28,181 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 143 transitions. Word has length 40 [2022-02-23 23:22:28,181 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:22:28,181 INFO L470 AbstractCegarLoop]: Abstraction has 122 states and 143 transitions. [2022-02-23 23:22:28,182 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-02-23 23:22:28,182 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 143 transitions. [2022-02-23 23:22:28,182 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2022-02-23 23:22:28,183 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:28,183 INFO L514 BasicCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:22:28,203 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-02-23 23:22:28,399 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:28,399 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:28,400 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:28,400 INFO L85 PathProgramCache]: Analyzing trace with hash 560903707, now seen corresponding path program 1 times [2022-02-23 23:22:28,400 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:28,400 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1552000133] [2022-02-23 23:22:28,400 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:28,400 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:28,406 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:22:28,406 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1379096256] [2022-02-23 23:22:28,406 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:28,407 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:28,407 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:22:28,408 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) [2022-02-23 23:22:28,408 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-02-23 23:22:28,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:28,445 INFO L263 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 9 conjunts are in the unsatisfiable core [2022-02-23 23:22:28,446 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:22:28,557 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 36 proven. 42 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2022-02-23 23:22:28,557 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:22:28,670 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-02-23 23:22:28,671 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:28,671 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1552000133] [2022-02-23 23:22:28,671 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:22:28,671 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1379096256] [2022-02-23 23:22:28,671 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1379096256] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:22:28,671 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:22:28,671 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2022-02-23 23:22:28,672 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [54097029] [2022-02-23 23:22:28,672 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:22:28,672 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-02-23 23:22:28,672 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:28,673 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-02-23 23:22:28,673 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-02-23 23:22:28,673 INFO L87 Difference]: Start difference. First operand 122 states and 143 transitions. Second operand has 10 states, 10 states have (on average 3.6) internal successors, (36), 10 states have internal predecessors, (36), 8 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (16), 7 states have call predecessors, (16), 6 states have call successors, (16) [2022-02-23 23:22:28,802 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:22:28,802 INFO L93 Difference]: Finished difference Result 245 states and 298 transitions. [2022-02-23 23:22:28,802 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-02-23 23:22:28,802 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.6) internal successors, (36), 10 states have internal predecessors, (36), 8 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (16), 7 states have call predecessors, (16), 6 states have call successors, (16) Word has length 53 [2022-02-23 23:22:28,803 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:22:28,805 INFO L225 Difference]: With dead ends: 245 [2022-02-23 23:22:28,805 INFO L226 Difference]: Without dead ends: 224 [2022-02-23 23:22:28,806 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=52, Invalid=104, Unknown=0, NotChecked=0, Total=156 [2022-02-23 23:22:28,806 INFO L933 BasicCegarLoop]: 59 mSDtfsCounter, 80 mSDsluCounter, 243 mSDsCounter, 0 mSdLazyCounter, 119 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 80 SdHoareTripleChecker+Valid, 302 SdHoareTripleChecker+Invalid, 143 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 119 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 23:22:28,807 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [80 Valid, 302 Invalid, 143 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 119 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 23:22:28,808 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 224 states. [2022-02-23 23:22:28,821 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 224 to 217. [2022-02-23 23:22:28,822 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 217 states, 139 states have (on average 1.1942446043165467) internal successors, (166), 148 states have internal predecessors, (166), 51 states have call successors, (51), 28 states have call predecessors, (51), 26 states have return successors, (46), 40 states have call predecessors, (46), 46 states have call successors, (46) [2022-02-23 23:22:28,823 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 217 states to 217 states and 263 transitions. [2022-02-23 23:22:28,823 INFO L78 Accepts]: Start accepts. Automaton has 217 states and 263 transitions. Word has length 53 [2022-02-23 23:22:28,823 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:22:28,823 INFO L470 AbstractCegarLoop]: Abstraction has 217 states and 263 transitions. [2022-02-23 23:22:28,823 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.6) internal successors, (36), 10 states have internal predecessors, (36), 8 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (16), 7 states have call predecessors, (16), 6 states have call successors, (16) [2022-02-23 23:22:28,823 INFO L276 IsEmpty]: Start isEmpty. Operand 217 states and 263 transitions. [2022-02-23 23:22:28,824 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2022-02-23 23:22:28,824 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:28,825 INFO L514 BasicCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:22:28,855 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-02-23 23:22:29,039 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:29,039 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:29,039 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:29,040 INFO L85 PathProgramCache]: Analyzing trace with hash -453219492, now seen corresponding path program 1 times [2022-02-23 23:22:29,040 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:29,040 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [867815345] [2022-02-23 23:22:29,040 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:29,040 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:29,046 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:22:29,046 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2066397104] [2022-02-23 23:22:29,046 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:29,046 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:29,046 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:22:29,047 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) [2022-02-23 23:22:29,048 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-02-23 23:22:29,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:29,088 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 25 conjunts are in the unsatisfiable core [2022-02-23 23:22:29,090 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:22:29,379 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-02-23 23:22:29,379 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:22:30,208 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-02-23 23:22:30,208 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:30,208 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [867815345] [2022-02-23 23:22:30,208 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:22:30,208 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2066397104] [2022-02-23 23:22:30,209 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2066397104] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:22:30,209 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:22:30,209 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-02-23 23:22:30,210 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1280094216] [2022-02-23 23:22:30,210 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:22:30,211 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-02-23 23:22:30,212 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:30,212 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-02-23 23:22:30,212 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-02-23 23:22:30,212 INFO L87 Difference]: Start difference. First operand 217 states and 263 transitions. Second operand has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-02-23 23:22:34,491 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:22:34,491 INFO L93 Difference]: Finished difference Result 371 states and 479 transitions. [2022-02-23 23:22:34,491 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-02-23 23:22:34,492 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) Word has length 62 [2022-02-23 23:22:34,492 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:22:34,493 INFO L225 Difference]: With dead ends: 371 [2022-02-23 23:22:34,493 INFO L226 Difference]: Without dead ends: 303 [2022-02-23 23:22:34,494 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 112 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=50, Invalid=132, Unknown=0, NotChecked=0, Total=182 [2022-02-23 23:22:34,495 INFO L933 BasicCegarLoop]: 51 mSDtfsCounter, 49 mSDsluCounter, 243 mSDsCounter, 0 mSdLazyCounter, 218 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 294 SdHoareTripleChecker+Invalid, 286 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 218 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-02-23 23:22:34,495 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 294 Invalid, 286 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 218 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-02-23 23:22:34,495 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 303 states. [2022-02-23 23:22:34,513 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 303 to 274. [2022-02-23 23:22:34,514 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 274 states, 185 states have (on average 1.2324324324324325) internal successors, (228), 191 states have internal predecessors, (228), 58 states have call successors, (58), 31 states have call predecessors, (58), 30 states have return successors, (55), 51 states have call predecessors, (55), 55 states have call successors, (55) [2022-02-23 23:22:34,515 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 274 states to 274 states and 341 transitions. [2022-02-23 23:22:34,515 INFO L78 Accepts]: Start accepts. Automaton has 274 states and 341 transitions. Word has length 62 [2022-02-23 23:22:34,515 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:22:34,515 INFO L470 AbstractCegarLoop]: Abstraction has 274 states and 341 transitions. [2022-02-23 23:22:34,515 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 9 states have internal predecessors, (34), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-02-23 23:22:34,516 INFO L276 IsEmpty]: Start isEmpty. Operand 274 states and 341 transitions. [2022-02-23 23:22:34,518 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2022-02-23 23:22:34,518 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:34,518 INFO L514 BasicCegarLoop]: trace histogram [11, 10, 10, 2, 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] [2022-02-23 23:22:34,538 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-02-23 23:22:34,738 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:34,739 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:34,739 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:34,739 INFO L85 PathProgramCache]: Analyzing trace with hash 929445032, now seen corresponding path program 1 times [2022-02-23 23:22:34,739 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:34,739 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1510981404] [2022-02-23 23:22:34,739 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:34,740 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:34,745 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:22:34,746 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1615003284] [2022-02-23 23:22:34,746 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:34,746 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:34,746 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:22:34,747 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) [2022-02-23 23:22:34,747 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-02-23 23:22:34,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:34,792 INFO L263 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 35 conjunts are in the unsatisfiable core [2022-02-23 23:22:34,794 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:22:35,153 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 66 proven. 13 refuted. 0 times theorem prover too weak. 132 trivial. 0 not checked. [2022-02-23 23:22:35,153 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:22:35,375 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 68 proven. 2 refuted. 0 times theorem prover too weak. 141 trivial. 0 not checked. [2022-02-23 23:22:35,376 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:35,376 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1510981404] [2022-02-23 23:22:35,376 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:22:35,376 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1615003284] [2022-02-23 23:22:35,376 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1615003284] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:22:35,376 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:22:35,376 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 16 [2022-02-23 23:22:35,377 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1246425403] [2022-02-23 23:22:35,377 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:22:35,378 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-02-23 23:22:35,378 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:35,378 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-02-23 23:22:35,378 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=189, Unknown=0, NotChecked=0, Total=240 [2022-02-23 23:22:35,379 INFO L87 Difference]: Start difference. First operand 274 states and 341 transitions. Second operand has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2022-02-23 23:22:35,720 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:22:35,720 INFO L93 Difference]: Finished difference Result 335 states and 416 transitions. [2022-02-23 23:22:35,720 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-02-23 23:22:35,720 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) Word has length 73 [2022-02-23 23:22:35,721 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:22:35,722 INFO L225 Difference]: With dead ends: 335 [2022-02-23 23:22:35,722 INFO L226 Difference]: Without dead ends: 239 [2022-02-23 23:22:35,723 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 129 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=76, Invalid=304, Unknown=0, NotChecked=0, Total=380 [2022-02-23 23:22:35,723 INFO L933 BasicCegarLoop]: 35 mSDtfsCounter, 54 mSDsluCounter, 229 mSDsCounter, 0 mSdLazyCounter, 364 mSolverCounterSat, 69 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 264 SdHoareTripleChecker+Invalid, 433 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 69 IncrementalHoareTripleChecker+Valid, 364 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-02-23 23:22:35,723 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [68 Valid, 264 Invalid, 433 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [69 Valid, 364 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-02-23 23:22:35,724 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 239 states. [2022-02-23 23:22:35,735 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 239 to 223. [2022-02-23 23:22:35,735 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 223 states, 150 states have (on average 1.1933333333333334) internal successors, (179), 154 states have internal predecessors, (179), 45 states have call successors, (45), 29 states have call predecessors, (45), 27 states have return successors, (42), 39 states have call predecessors, (42), 42 states have call successors, (42) [2022-02-23 23:22:35,736 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 223 states to 223 states and 266 transitions. [2022-02-23 23:22:35,736 INFO L78 Accepts]: Start accepts. Automaton has 223 states and 266 transitions. Word has length 73 [2022-02-23 23:22:35,737 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:22:35,737 INFO L470 AbstractCegarLoop]: Abstraction has 223 states and 266 transitions. [2022-02-23 23:22:35,737 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 3.0833333333333335) internal successors, (37), 11 states have internal predecessors, (37), 8 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2022-02-23 23:22:35,737 INFO L276 IsEmpty]: Start isEmpty. Operand 223 states and 266 transitions. [2022-02-23 23:22:35,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-02-23 23:22:35,737 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:35,738 INFO L514 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:22:35,756 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-02-23 23:22:35,954 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-02-23 23:22:35,954 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:35,954 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:35,955 INFO L85 PathProgramCache]: Analyzing trace with hash -1139963303, now seen corresponding path program 1 times [2022-02-23 23:22:35,955 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:35,955 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [261783487] [2022-02-23 23:22:35,955 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:35,955 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:35,965 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:22:35,965 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [442668163] [2022-02-23 23:22:35,965 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:35,965 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:35,966 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:22:35,967 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) [2022-02-23 23:22:35,968 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-02-23 23:22:36,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:22:36,006 INFO L263 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 4 conjunts are in the unsatisfiable core [2022-02-23 23:22:36,010 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:22:36,158 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 84 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2022-02-23 23:22:36,158 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 23:22:36,158 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:36,158 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [261783487] [2022-02-23 23:22:36,159 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:22:36,159 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [442668163] [2022-02-23 23:22:36,159 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [442668163] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 23:22:36,159 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 23:22:36,159 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-02-23 23:22:36,159 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [9801362] [2022-02-23 23:22:36,159 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 23:22:36,159 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 23:22:36,159 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:36,160 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 23:22:36,160 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-02-23 23:22:36,160 INFO L87 Difference]: Start difference. First operand 223 states and 266 transitions. Second operand has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-02-23 23:22:36,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:22:36,201 INFO L93 Difference]: Finished difference Result 242 states and 289 transitions. [2022-02-23 23:22:36,202 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 23:22:36,202 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 82 [2022-02-23 23:22:36,203 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:22:36,203 INFO L225 Difference]: With dead ends: 242 [2022-02-23 23:22:36,203 INFO L226 Difference]: Without dead ends: 222 [2022-02-23 23:22:36,204 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-02-23 23:22:36,205 INFO L933 BasicCegarLoop]: 57 mSDtfsCounter, 24 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 23:22:36,205 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 121 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 23:22:36,206 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 222 states. [2022-02-23 23:22:36,223 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 222 to 217. [2022-02-23 23:22:36,223 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 217 states, 147 states have (on average 1.163265306122449) internal successors, (171), 149 states have internal predecessors, (171), 43 states have call successors, (43), 27 states have call predecessors, (43), 26 states have return successors, (41), 40 states have call predecessors, (41), 41 states have call successors, (41) [2022-02-23 23:22:36,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 217 states to 217 states and 255 transitions. [2022-02-23 23:22:36,224 INFO L78 Accepts]: Start accepts. Automaton has 217 states and 255 transitions. Word has length 82 [2022-02-23 23:22:36,225 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:22:36,225 INFO L470 AbstractCegarLoop]: Abstraction has 217 states and 255 transitions. [2022-02-23 23:22:36,225 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-02-23 23:22:36,225 INFO L276 IsEmpty]: Start isEmpty. Operand 217 states and 255 transitions. [2022-02-23 23:22:36,225 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2022-02-23 23:22:36,225 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:22:36,225 INFO L514 BasicCegarLoop]: trace histogram [14, 13, 13, 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] [2022-02-23 23:22:36,243 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-02-23 23:22:36,443 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-02-23 23:22:36,444 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:22:36,444 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:22:36,444 INFO L85 PathProgramCache]: Analyzing trace with hash -2090333941, now seen corresponding path program 2 times [2022-02-23 23:22:36,444 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:22:36,444 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1605041927] [2022-02-23 23:22:36,444 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:22:36,444 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:22:36,450 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:22:36,450 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1174748564] [2022-02-23 23:22:36,450 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-02-23 23:22:36,450 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:22:36,450 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:22:36,451 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) [2022-02-23 23:22:36,478 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-02-23 23:22:36,498 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-02-23 23:22:36,498 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 23:22:36,499 INFO L263 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 39 conjunts are in the unsatisfiable core [2022-02-23 23:22:36,501 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:22:36,870 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 26 proven. 30 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-02-23 23:22:36,870 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:22:50,716 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 26 proven. 30 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-02-23 23:22:50,717 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:22:50,717 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1605041927] [2022-02-23 23:22:50,717 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:22:50,717 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1174748564] [2022-02-23 23:22:50,717 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1174748564] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:22:50,717 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:22:50,717 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2022-02-23 23:22:50,717 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1134555364] [2022-02-23 23:22:50,717 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:22:50,718 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-02-23 23:22:50,718 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:22:50,718 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-02-23 23:22:50,718 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2022-02-23 23:22:50,718 INFO L87 Difference]: Start difference. First operand 217 states and 255 transitions. Second operand has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) [2022-02-23 23:23:01,572 WARN L232 SmtUtils]: Spent 10.58s on a formula simplification. DAG size of input: 192 DAG size of output: 86 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-02-23 23:23:10,545 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-23 23:23:12,450 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.89s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-23 23:23:14,464 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-23 23:23:16,699 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-23 23:23:19,469 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-23 23:23:21,961 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-23 23:23:23,953 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.13s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-23 23:23:26,065 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-23 23:23:26,756 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:23:26,756 INFO L93 Difference]: Finished difference Result 332 states and 434 transitions. [2022-02-23 23:23:26,756 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-02-23 23:23:26,756 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) Word has length 94 [2022-02-23 23:23:26,757 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:23:26,758 INFO L225 Difference]: With dead ends: 332 [2022-02-23 23:23:26,758 INFO L226 Difference]: Without dead ends: 275 [2022-02-23 23:23:26,758 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 194 GetRequests, 170 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 18.7s TimeCoverageRelationStatistics Valid=126, Invalid=336, Unknown=0, NotChecked=0, Total=462 [2022-02-23 23:23:26,759 INFO L933 BasicCegarLoop]: 73 mSDtfsCounter, 130 mSDsluCounter, 587 mSDsCounter, 0 mSdLazyCounter, 518 mSolverCounterSat, 176 mSolverCounterUnsat, 6 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 19.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 141 SdHoareTripleChecker+Valid, 660 SdHoareTripleChecker+Invalid, 700 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 176 IncrementalHoareTripleChecker+Valid, 518 IncrementalHoareTripleChecker+Invalid, 6 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 19.6s IncrementalHoareTripleChecker+Time [2022-02-23 23:23:26,759 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [141 Valid, 660 Invalid, 700 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [176 Valid, 518 Invalid, 6 Unknown, 0 Unchecked, 19.6s Time] [2022-02-23 23:23:26,759 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 275 states. [2022-02-23 23:23:26,776 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 275 to 257. [2022-02-23 23:23:26,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 257 states, 172 states have (on average 1.2267441860465116) internal successors, (211), 177 states have internal predecessors, (211), 57 states have call successors, (57), 28 states have call predecessors, (57), 27 states have return successors, (55), 51 states have call predecessors, (55), 55 states have call successors, (55) [2022-02-23 23:23:26,777 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 257 states to 257 states and 323 transitions. [2022-02-23 23:23:26,777 INFO L78 Accepts]: Start accepts. Automaton has 257 states and 323 transitions. Word has length 94 [2022-02-23 23:23:26,778 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:23:26,778 INFO L470 AbstractCegarLoop]: Abstraction has 257 states and 323 transitions. [2022-02-23 23:23:26,778 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.0) internal successors, (48), 15 states have internal predecessors, (48), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) [2022-02-23 23:23:26,778 INFO L276 IsEmpty]: Start isEmpty. Operand 257 states and 323 transitions. [2022-02-23 23:23:26,779 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2022-02-23 23:23:26,779 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:23:26,779 INFO L514 BasicCegarLoop]: trace histogram [15, 14, 14, 5, 4, 4, 4, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:23:26,799 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-02-23 23:23:26,995 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-02-23 23:23:26,995 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:23:26,996 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:23:26,996 INFO L85 PathProgramCache]: Analyzing trace with hash -105290329, now seen corresponding path program 1 times [2022-02-23 23:23:26,996 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:23:26,996 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [153610729] [2022-02-23 23:23:26,996 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:23:26,996 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:23:27,002 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:23:27,002 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1842065886] [2022-02-23 23:23:27,002 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:23:27,002 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:27,002 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:23:27,003 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) [2022-02-23 23:23:27,004 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-02-23 23:23:27,049 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:23:27,050 INFO L263 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 13 conjunts are in the unsatisfiable core [2022-02-23 23:23:27,055 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:23:27,215 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 120 proven. 260 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2022-02-23 23:23:27,215 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:23:27,380 INFO L134 CoverageAnalysis]: Checked inductivity of 438 backedges. 28 proven. 44 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2022-02-23 23:23:27,380 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:23:27,380 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [153610729] [2022-02-23 23:23:27,380 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:23:27,380 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1842065886] [2022-02-23 23:23:27,380 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1842065886] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:23:27,380 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:23:27,380 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-02-23 23:23:27,380 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1370639590] [2022-02-23 23:23:27,380 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:23:27,381 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-02-23 23:23:27,381 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:23:27,381 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-02-23 23:23:27,381 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-02-23 23:23:27,381 INFO L87 Difference]: Start difference. First operand 257 states and 323 transitions. Second operand has 14 states, 14 states have (on average 4.214285714285714) internal successors, (59), 14 states have internal predecessors, (59), 12 states have call successors, (32), 8 states have call predecessors, (32), 8 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2022-02-23 23:23:27,638 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:23:27,638 INFO L93 Difference]: Finished difference Result 746 states and 1016 transitions. [2022-02-23 23:23:27,639 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-02-23 23:23:27,639 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.214285714285714) internal successors, (59), 14 states have internal predecessors, (59), 12 states have call successors, (32), 8 states have call predecessors, (32), 8 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) Word has length 100 [2022-02-23 23:23:27,639 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:23:27,641 INFO L225 Difference]: With dead ends: 746 [2022-02-23 23:23:27,641 INFO L226 Difference]: Without dead ends: 659 [2022-02-23 23:23:27,642 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 208 GetRequests, 187 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2022-02-23 23:23:27,642 INFO L933 BasicCegarLoop]: 80 mSDtfsCounter, 177 mSDsluCounter, 298 mSDsCounter, 0 mSdLazyCounter, 191 mSolverCounterSat, 89 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 177 SdHoareTripleChecker+Valid, 378 SdHoareTripleChecker+Invalid, 280 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 89 IncrementalHoareTripleChecker+Valid, 191 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-02-23 23:23:27,643 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [177 Valid, 378 Invalid, 280 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [89 Valid, 191 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-02-23 23:23:27,643 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 659 states. [2022-02-23 23:23:27,685 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 659 to 552. [2022-02-23 23:23:27,686 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 552 states, 361 states have (on average 1.2825484764542936) internal successors, (463), 378 states have internal predecessors, (463), 136 states have call successors, (136), 56 states have call predecessors, (136), 54 states have return successors, (131), 117 states have call predecessors, (131), 131 states have call successors, (131) [2022-02-23 23:23:27,688 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 552 states to 552 states and 730 transitions. [2022-02-23 23:23:27,688 INFO L78 Accepts]: Start accepts. Automaton has 552 states and 730 transitions. Word has length 100 [2022-02-23 23:23:27,688 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:23:27,688 INFO L470 AbstractCegarLoop]: Abstraction has 552 states and 730 transitions. [2022-02-23 23:23:27,688 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.214285714285714) internal successors, (59), 14 states have internal predecessors, (59), 12 states have call successors, (32), 8 states have call predecessors, (32), 8 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30) [2022-02-23 23:23:27,688 INFO L276 IsEmpty]: Start isEmpty. Operand 552 states and 730 transitions. [2022-02-23 23:23:27,690 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2022-02-23 23:23:27,690 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:23:27,690 INFO L514 BasicCegarLoop]: trace histogram [16, 15, 15, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:23:27,707 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-02-23 23:23:27,903 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-02-23 23:23:27,903 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:23:27,904 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:23:27,904 INFO L85 PathProgramCache]: Analyzing trace with hash 331614142, now seen corresponding path program 1 times [2022-02-23 23:23:27,904 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:23:27,904 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1043109135] [2022-02-23 23:23:27,904 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:23:27,904 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:23:27,914 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:23:27,914 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [690864992] [2022-02-23 23:23:27,914 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:23:27,914 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:27,915 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:23:27,916 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) [2022-02-23 23:23:27,917 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-02-23 23:23:27,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:23:27,962 INFO L263 TraceCheckSpWp]: Trace formula consists of 281 conjuncts, 17 conjunts are in the unsatisfiable core [2022-02-23 23:23:27,966 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:23:28,132 INFO L134 CoverageAnalysis]: Checked inductivity of 492 backedges. 30 proven. 414 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-02-23 23:23:28,132 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:23:28,331 INFO L134 CoverageAnalysis]: Checked inductivity of 492 backedges. 30 proven. 42 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2022-02-23 23:23:28,332 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:23:28,332 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1043109135] [2022-02-23 23:23:28,332 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:23:28,332 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [690864992] [2022-02-23 23:23:28,332 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [690864992] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:23:28,332 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:23:28,332 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 18 [2022-02-23 23:23:28,332 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [849316932] [2022-02-23 23:23:28,332 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:23:28,333 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-02-23 23:23:28,333 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:23:28,333 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-02-23 23:23:28,333 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=125, Invalid=181, Unknown=0, NotChecked=0, Total=306 [2022-02-23 23:23:28,333 INFO L87 Difference]: Start difference. First operand 552 states and 730 transitions. Second operand has 18 states, 18 states have (on average 4.222222222222222) internal successors, (76), 18 states have internal predecessors, (76), 16 states have call successors, (34), 10 states have call predecessors, (34), 9 states have return successors, (32), 14 states have call predecessors, (32), 13 states have call successors, (32) [2022-02-23 23:23:28,765 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:23:28,765 INFO L93 Difference]: Finished difference Result 1159 states and 1613 transitions. [2022-02-23 23:23:28,765 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2022-02-23 23:23:28,765 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 4.222222222222222) internal successors, (76), 18 states have internal predecessors, (76), 16 states have call successors, (34), 10 states have call predecessors, (34), 9 states have return successors, (32), 14 states have call predecessors, (32), 13 states have call successors, (32) Word has length 108 [2022-02-23 23:23:28,765 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:23:28,769 INFO L225 Difference]: With dead ends: 1159 [2022-02-23 23:23:28,769 INFO L226 Difference]: Without dead ends: 1122 [2022-02-23 23:23:28,770 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 199 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=259, Invalid=497, Unknown=0, NotChecked=0, Total=756 [2022-02-23 23:23:28,770 INFO L933 BasicCegarLoop]: 100 mSDtfsCounter, 314 mSDsluCounter, 403 mSDsCounter, 0 mSdLazyCounter, 296 mSolverCounterSat, 198 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 314 SdHoareTripleChecker+Valid, 503 SdHoareTripleChecker+Invalid, 494 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 198 IncrementalHoareTripleChecker+Valid, 296 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-02-23 23:23:28,770 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [314 Valid, 503 Invalid, 494 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [198 Valid, 296 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-02-23 23:23:28,771 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1122 states. [2022-02-23 23:23:28,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1122 to 1097. [2022-02-23 23:23:28,841 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1097 states, 729 states have (on average 1.2455418381344308) internal successors, (908), 758 states have internal predecessors, (908), 279 states have call successors, (279), 90 states have call predecessors, (279), 88 states have return successors, (270), 248 states have call predecessors, (270), 270 states have call successors, (270) [2022-02-23 23:23:28,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1097 states to 1097 states and 1457 transitions. [2022-02-23 23:23:28,845 INFO L78 Accepts]: Start accepts. Automaton has 1097 states and 1457 transitions. Word has length 108 [2022-02-23 23:23:28,845 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:23:28,845 INFO L470 AbstractCegarLoop]: Abstraction has 1097 states and 1457 transitions. [2022-02-23 23:23:28,845 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 4.222222222222222) internal successors, (76), 18 states have internal predecessors, (76), 16 states have call successors, (34), 10 states have call predecessors, (34), 9 states have return successors, (32), 14 states have call predecessors, (32), 13 states have call successors, (32) [2022-02-23 23:23:28,845 INFO L276 IsEmpty]: Start isEmpty. Operand 1097 states and 1457 transitions. [2022-02-23 23:23:28,846 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2022-02-23 23:23:28,846 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:23:28,846 INFO L514 BasicCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:23:28,862 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-02-23 23:23:29,059 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-02-23 23:23:29,059 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:23:29,060 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:23:29,060 INFO L85 PathProgramCache]: Analyzing trace with hash 1288142005, now seen corresponding path program 1 times [2022-02-23 23:23:29,060 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:23:29,060 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1072502680] [2022-02-23 23:23:29,060 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:23:29,060 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:23:29,071 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:23:29,072 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1341147260] [2022-02-23 23:23:29,072 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:23:29,072 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:29,072 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:23:29,073 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) [2022-02-23 23:23:29,074 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-02-23 23:23:29,115 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 23:23:29,116 INFO L263 TraceCheckSpWp]: Trace formula consists of 277 conjuncts, 14 conjunts are in the unsatisfiable core [2022-02-23 23:23:29,117 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:23:29,347 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-02-23 23:23:29,348 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:23:30,073 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-02-23 23:23:30,073 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:23:30,073 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1072502680] [2022-02-23 23:23:30,073 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:23:30,073 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1341147260] [2022-02-23 23:23:30,073 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1341147260] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:23:30,073 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:23:30,073 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-02-23 23:23:30,074 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1815361710] [2022-02-23 23:23:30,074 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:23:30,074 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-02-23 23:23:30,074 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:23:30,074 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-02-23 23:23:30,074 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2022-02-23 23:23:30,075 INFO L87 Difference]: Start difference. First operand 1097 states and 1457 transitions. Second operand has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 7 states have call successors, (36), 2 states have call predecessors, (36), 1 states have return successors, (33), 7 states have call predecessors, (33), 7 states have call successors, (33) [2022-02-23 23:23:30,390 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:23:30,391 INFO L93 Difference]: Finished difference Result 1103 states and 1463 transitions. [2022-02-23 23:23:30,391 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-02-23 23:23:30,391 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 7 states have call successors, (36), 2 states have call predecessors, (36), 1 states have return successors, (33), 7 states have call predecessors, (33), 7 states have call successors, (33) Word has length 110 [2022-02-23 23:23:30,391 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:23:30,394 INFO L225 Difference]: With dead ends: 1103 [2022-02-23 23:23:30,395 INFO L226 Difference]: Without dead ends: 1097 [2022-02-23 23:23:30,395 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 220 GetRequests, 207 SyntacticMatches, 4 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2022-02-23 23:23:30,395 INFO L933 BasicCegarLoop]: 65 mSDtfsCounter, 2 mSDsluCounter, 329 mSDsCounter, 0 mSdLazyCounter, 159 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 394 SdHoareTripleChecker+Invalid, 159 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 159 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-02-23 23:23:30,395 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 394 Invalid, 159 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 159 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-02-23 23:23:30,396 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1097 states. [2022-02-23 23:23:30,463 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1097 to 1097. [2022-02-23 23:23:30,465 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1097 states, 729 states have (on average 1.242798353909465) internal successors, (906), 758 states have internal predecessors, (906), 279 states have call successors, (279), 90 states have call predecessors, (279), 88 states have return successors, (270), 248 states have call predecessors, (270), 270 states have call successors, (270) [2022-02-23 23:23:30,468 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1097 states to 1097 states and 1455 transitions. [2022-02-23 23:23:30,468 INFO L78 Accepts]: Start accepts. Automaton has 1097 states and 1455 transitions. Word has length 110 [2022-02-23 23:23:30,468 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:23:30,468 INFO L470 AbstractCegarLoop]: Abstraction has 1097 states and 1455 transitions. [2022-02-23 23:23:30,469 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 5.0) internal successors, (50), 9 states have internal predecessors, (50), 7 states have call successors, (36), 2 states have call predecessors, (36), 1 states have return successors, (33), 7 states have call predecessors, (33), 7 states have call successors, (33) [2022-02-23 23:23:30,469 INFO L276 IsEmpty]: Start isEmpty. Operand 1097 states and 1455 transitions. [2022-02-23 23:23:30,470 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2022-02-23 23:23:30,470 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:23:30,470 INFO L514 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:23:30,486 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-02-23 23:23:30,686 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-02-23 23:23:30,686 INFO L402 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:23:30,687 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:23:30,687 INFO L85 PathProgramCache]: Analyzing trace with hash 848408867, now seen corresponding path program 2 times [2022-02-23 23:23:30,687 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:23:30,687 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [513154621] [2022-02-23 23:23:30,687 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:23:30,687 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:23:30,692 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:23:30,692 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [74575792] [2022-02-23 23:23:30,692 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-02-23 23:23:30,692 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:30,692 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:23:30,693 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) [2022-02-23 23:23:30,694 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-02-23 23:23:30,739 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-02-23 23:23:30,739 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 23:23:30,740 INFO L263 TraceCheckSpWp]: Trace formula consists of 310 conjuncts, 12 conjunts are in the unsatisfiable core [2022-02-23 23:23:30,741 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:23:30,876 INFO L134 CoverageAnalysis]: Checked inductivity of 699 backedges. 102 proven. 51 refuted. 0 times theorem prover too weak. 546 trivial. 0 not checked. [2022-02-23 23:23:30,876 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:23:31,160 INFO L134 CoverageAnalysis]: Checked inductivity of 699 backedges. 69 proven. 18 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2022-02-23 23:23:31,160 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:23:31,160 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [513154621] [2022-02-23 23:23:31,160 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:23:31,160 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [74575792] [2022-02-23 23:23:31,160 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [74575792] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:23:31,160 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:23:31,160 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-02-23 23:23:31,161 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1456674114] [2022-02-23 23:23:31,161 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:23:31,161 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-02-23 23:23:31,161 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:23:31,161 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-02-23 23:23:31,161 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-02-23 23:23:31,161 INFO L87 Difference]: Start difference. First operand 1097 states and 1455 transitions. Second operand has 9 states, 9 states have (on average 6.222222222222222) internal successors, (56), 9 states have internal predecessors, (56), 9 states have call successors, (37), 2 states have call predecessors, (37), 2 states have return successors, (35), 9 states have call predecessors, (35), 9 states have call successors, (35) [2022-02-23 23:23:31,308 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:23:31,309 INFO L93 Difference]: Finished difference Result 1320 states and 1738 transitions. [2022-02-23 23:23:31,309 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 23:23:31,309 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 6.222222222222222) internal successors, (56), 9 states have internal predecessors, (56), 9 states have call successors, (37), 2 states have call predecessors, (37), 2 states have return successors, (35), 9 states have call predecessors, (35), 9 states have call successors, (35) Word has length 124 [2022-02-23 23:23:31,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:23:31,312 INFO L225 Difference]: With dead ends: 1320 [2022-02-23 23:23:31,312 INFO L226 Difference]: Without dead ends: 907 [2022-02-23 23:23:31,314 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 247 GetRequests, 237 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-02-23 23:23:31,314 INFO L933 BasicCegarLoop]: 67 mSDtfsCounter, 4 mSDsluCounter, 180 mSDsCounter, 0 mSdLazyCounter, 73 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 247 SdHoareTripleChecker+Invalid, 80 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 73 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 23:23:31,315 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 247 Invalid, 80 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 73 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 23:23:31,315 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 907 states. [2022-02-23 23:23:31,381 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 907 to 905. [2022-02-23 23:23:31,382 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 905 states, 598 states have (on average 1.2040133779264215) internal successors, (720), 627 states have internal predecessors, (720), 221 states have call successors, (221), 87 states have call predecessors, (221), 85 states have return successors, (212), 190 states have call predecessors, (212), 212 states have call successors, (212) [2022-02-23 23:23:31,385 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 905 states to 905 states and 1153 transitions. [2022-02-23 23:23:31,386 INFO L78 Accepts]: Start accepts. Automaton has 905 states and 1153 transitions. Word has length 124 [2022-02-23 23:23:31,387 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:23:31,387 INFO L470 AbstractCegarLoop]: Abstraction has 905 states and 1153 transitions. [2022-02-23 23:23:31,387 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 6.222222222222222) internal successors, (56), 9 states have internal predecessors, (56), 9 states have call successors, (37), 2 states have call predecessors, (37), 2 states have return successors, (35), 9 states have call predecessors, (35), 9 states have call successors, (35) [2022-02-23 23:23:31,387 INFO L276 IsEmpty]: Start isEmpty. Operand 905 states and 1153 transitions. [2022-02-23 23:23:31,389 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 127 [2022-02-23 23:23:31,389 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:23:31,389 INFO L514 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:23:31,408 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-02-23 23:23:31,608 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable17,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:31,609 INFO L402 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:23:31,609 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:23:31,609 INFO L85 PathProgramCache]: Analyzing trace with hash 722879610, now seen corresponding path program 3 times [2022-02-23 23:23:31,609 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:23:31,609 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [422832320] [2022-02-23 23:23:31,610 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:23:31,610 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:23:31,622 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:23:31,623 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [717064385] [2022-02-23 23:23:31,623 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-02-23 23:23:31,623 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:31,623 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:23:31,624 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) [2022-02-23 23:23:31,625 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-02-23 23:23:31,705 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-02-23 23:23:31,705 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 23:23:31,707 INFO L263 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 24 conjunts are in the unsatisfiable core [2022-02-23 23:23:31,709 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:23:31,944 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-02-23 23:23:32,019 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-02-23 23:23:32,084 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-02-23 23:23:32,250 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 145 proven. 2 refuted. 0 times theorem prover too weak. 564 trivial. 0 not checked. [2022-02-23 23:23:32,250 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:23:43,876 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:23:43,876 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [422832320] [2022-02-23 23:23:43,876 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:23:43,876 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [717064385] [2022-02-23 23:23:43,876 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [717064385] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 23:23:43,876 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 23:23:43,876 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-02-23 23:23:43,876 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2087220235] [2022-02-23 23:23:43,876 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 23:23:43,877 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-02-23 23:23:43,877 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:23:43,877 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-02-23 23:23:43,877 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2022-02-23 23:23:43,877 INFO L87 Difference]: Start difference. First operand 905 states and 1153 transitions. Second operand has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 3 states have call successors, (8) [2022-02-23 23:23:43,994 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:23:43,994 INFO L93 Difference]: Finished difference Result 935 states and 1182 transitions. [2022-02-23 23:23:43,994 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-02-23 23:23:43,995 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 3 states have call successors, (8) Word has length 126 [2022-02-23 23:23:43,995 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:23:43,997 INFO L225 Difference]: With dead ends: 935 [2022-02-23 23:23:43,997 INFO L226 Difference]: Without dead ends: 921 [2022-02-23 23:23:43,998 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 120 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2022-02-23 23:23:43,998 INFO L933 BasicCegarLoop]: 23 mSDtfsCounter, 19 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 91 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 81 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 23:23:43,998 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 118 Invalid, 91 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 81 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 23:23:43,999 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 921 states. [2022-02-23 23:23:44,048 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 921 to 695. [2022-02-23 23:23:44,049 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 695 states, 468 states have (on average 1.1752136752136753) internal successors, (550), 470 states have internal predecessors, (550), 153 states have call successors, (153), 75 states have call predecessors, (153), 73 states have return successors, (150), 149 states have call predecessors, (150), 150 states have call successors, (150) [2022-02-23 23:23:44,051 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 695 states to 695 states and 853 transitions. [2022-02-23 23:23:44,051 INFO L78 Accepts]: Start accepts. Automaton has 695 states and 853 transitions. Word has length 126 [2022-02-23 23:23:44,051 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:23:44,051 INFO L470 AbstractCegarLoop]: Abstraction has 695 states and 853 transitions. [2022-02-23 23:23:44,051 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 8 states have internal predecessors, (24), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 3 states have call successors, (8) [2022-02-23 23:23:44,052 INFO L276 IsEmpty]: Start isEmpty. Operand 695 states and 853 transitions. [2022-02-23 23:23:44,052 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 129 [2022-02-23 23:23:44,052 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:23:44,052 INFO L514 BasicCegarLoop]: trace histogram [20, 19, 19, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:23:44,073 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-02-23 23:23:44,273 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:44,273 INFO L402 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:23:44,274 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:23:44,274 INFO L85 PathProgramCache]: Analyzing trace with hash -1722143882, now seen corresponding path program 3 times [2022-02-23 23:23:44,274 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:23:44,274 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1733450830] [2022-02-23 23:23:44,274 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:23:44,274 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:23:44,288 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:23:44,288 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [428323948] [2022-02-23 23:23:44,288 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-02-23 23:23:44,288 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:44,288 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:23:44,289 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) [2022-02-23 23:23:44,290 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-02-23 23:23:44,332 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-02-23 23:23:44,332 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 23:23:44,333 INFO L263 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 12 conjunts are in the unsatisfiable core [2022-02-23 23:23:44,335 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:23:44,512 INFO L134 CoverageAnalysis]: Checked inductivity of 774 backedges. 90 proven. 4 refuted. 0 times theorem prover too weak. 680 trivial. 0 not checked. [2022-02-23 23:23:44,512 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:23:44,693 INFO L134 CoverageAnalysis]: Checked inductivity of 774 backedges. 90 proven. 4 refuted. 0 times theorem prover too weak. 680 trivial. 0 not checked. [2022-02-23 23:23:44,693 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:23:44,693 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1733450830] [2022-02-23 23:23:44,693 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:23:44,693 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [428323948] [2022-02-23 23:23:44,693 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [428323948] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:23:44,693 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:23:44,694 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-02-23 23:23:44,694 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2014464418] [2022-02-23 23:23:44,694 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:23:44,694 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-02-23 23:23:44,694 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:23:44,694 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-02-23 23:23:44,694 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2022-02-23 23:23:44,695 INFO L87 Difference]: Start difference. First operand 695 states and 853 transitions. Second operand has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 4 states have call successors, (15) [2022-02-23 23:23:44,826 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:23:44,826 INFO L93 Difference]: Finished difference Result 771 states and 912 transitions. [2022-02-23 23:23:44,827 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-02-23 23:23:44,827 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 4 states have call successors, (15) Word has length 128 [2022-02-23 23:23:44,827 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:23:44,829 INFO L225 Difference]: With dead ends: 771 [2022-02-23 23:23:44,829 INFO L226 Difference]: Without dead ends: 755 [2022-02-23 23:23:44,829 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 259 GetRequests, 245 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2022-02-23 23:23:44,830 INFO L933 BasicCegarLoop]: 23 mSDtfsCounter, 27 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 152 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 175 SdHoareTripleChecker+Invalid, 168 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 152 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 23:23:44,830 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 175 Invalid, 168 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 152 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 23:23:44,830 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 755 states. [2022-02-23 23:23:44,871 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 755 to 539. [2022-02-23 23:23:44,872 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 539 states, 362 states have (on average 1.1049723756906078) internal successors, (400), 373 states have internal predecessors, (400), 103 states have call successors, (103), 74 states have call predecessors, (103), 73 states have return successors, (101), 91 states have call predecessors, (101), 101 states have call successors, (101) [2022-02-23 23:23:44,874 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 539 states to 539 states and 604 transitions. [2022-02-23 23:23:44,874 INFO L78 Accepts]: Start accepts. Automaton has 539 states and 604 transitions. Word has length 128 [2022-02-23 23:23:44,874 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:23:44,874 INFO L470 AbstractCegarLoop]: Abstraction has 539 states and 604 transitions. [2022-02-23 23:23:44,874 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 4 states have call successors, (15) [2022-02-23 23:23:44,874 INFO L276 IsEmpty]: Start isEmpty. Operand 539 states and 604 transitions. [2022-02-23 23:23:44,876 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 225 [2022-02-23 23:23:44,876 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:23:44,876 INFO L514 BasicCegarLoop]: trace histogram [33, 32, 32, 11, 10, 10, 10, 10, 10, 10, 10, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:23:44,897 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-02-23 23:23:45,095 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:45,095 INFO L402 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:23:45,096 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:23:45,096 INFO L85 PathProgramCache]: Analyzing trace with hash -206704767, now seen corresponding path program 2 times [2022-02-23 23:23:45,096 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:23:45,096 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1520111324] [2022-02-23 23:23:45,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:23:45,096 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:23:45,104 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:23:45,104 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [242803794] [2022-02-23 23:23:45,104 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-02-23 23:23:45,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:45,104 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:23:45,105 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) [2022-02-23 23:23:45,106 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-02-23 23:23:45,177 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-02-23 23:23:45,178 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 23:23:45,179 INFO L263 TraceCheckSpWp]: Trace formula consists of 549 conjuncts, 33 conjunts are in the unsatisfiable core [2022-02-23 23:23:45,183 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:23:45,547 INFO L134 CoverageAnalysis]: Checked inductivity of 2374 backedges. 64 proven. 2222 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-02-23 23:23:45,547 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:23:45,895 INFO L134 CoverageAnalysis]: Checked inductivity of 2374 backedges. 64 proven. 326 refuted. 0 times theorem prover too weak. 1984 trivial. 0 not checked. [2022-02-23 23:23:45,895 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:23:45,895 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1520111324] [2022-02-23 23:23:45,895 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:23:45,895 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [242803794] [2022-02-23 23:23:45,895 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [242803794] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:23:45,895 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:23:45,895 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 24 [2022-02-23 23:23:45,895 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [576185147] [2022-02-23 23:23:45,895 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:23:45,896 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2022-02-23 23:23:45,896 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:23:45,896 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2022-02-23 23:23:45,896 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=236, Invalid=316, Unknown=0, NotChecked=0, Total=552 [2022-02-23 23:23:45,897 INFO L87 Difference]: Start difference. First operand 539 states and 604 transitions. Second operand has 24 states, 24 states have (on average 5.916666666666667) internal successors, (142), 24 states have internal predecessors, (142), 22 states have call successors, (68), 17 states have call predecessors, (68), 16 states have return successors, (66), 20 states have call predecessors, (66), 20 states have call successors, (66) [2022-02-23 23:23:46,394 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:23:46,394 INFO L93 Difference]: Finished difference Result 829 states and 954 transitions. [2022-02-23 23:23:46,394 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2022-02-23 23:23:46,395 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 5.916666666666667) internal successors, (142), 24 states have internal predecessors, (142), 22 states have call successors, (68), 17 states have call predecessors, (68), 16 states have return successors, (66), 20 states have call predecessors, (66), 20 states have call successors, (66) Word has length 224 [2022-02-23 23:23:46,395 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:23:46,397 INFO L225 Difference]: With dead ends: 829 [2022-02-23 23:23:46,397 INFO L226 Difference]: Without dead ends: 816 [2022-02-23 23:23:46,398 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 462 GetRequests, 424 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 149 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=517, Invalid=965, Unknown=0, NotChecked=0, Total=1482 [2022-02-23 23:23:46,398 INFO L933 BasicCegarLoop]: 119 mSDtfsCounter, 345 mSDsluCounter, 480 mSDsCounter, 0 mSdLazyCounter, 397 mSolverCounterSat, 237 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 345 SdHoareTripleChecker+Valid, 599 SdHoareTripleChecker+Invalid, 634 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 237 IncrementalHoareTripleChecker+Valid, 397 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-02-23 23:23:46,399 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [345 Valid, 599 Invalid, 634 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [237 Valid, 397 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-02-23 23:23:46,399 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 816 states. [2022-02-23 23:23:46,468 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 816 to 815. [2022-02-23 23:23:46,469 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 815 states, 548 states have (on average 1.1131386861313868) internal successors, (610), 565 states have internal predecessors, (610), 157 states have call successors, (157), 110 states have call predecessors, (157), 109 states have return successors, (155), 139 states have call predecessors, (155), 155 states have call successors, (155) [2022-02-23 23:23:46,471 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 815 states to 815 states and 922 transitions. [2022-02-23 23:23:46,471 INFO L78 Accepts]: Start accepts. Automaton has 815 states and 922 transitions. Word has length 224 [2022-02-23 23:23:46,472 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:23:46,472 INFO L470 AbstractCegarLoop]: Abstraction has 815 states and 922 transitions. [2022-02-23 23:23:46,472 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 5.916666666666667) internal successors, (142), 24 states have internal predecessors, (142), 22 states have call successors, (68), 17 states have call predecessors, (68), 16 states have return successors, (66), 20 states have call predecessors, (66), 20 states have call successors, (66) [2022-02-23 23:23:46,472 INFO L276 IsEmpty]: Start isEmpty. Operand 815 states and 922 transitions. [2022-02-23 23:23:46,475 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 309 [2022-02-23 23:23:46,475 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:23:46,476 INFO L514 BasicCegarLoop]: trace histogram [45, 44, 44, 17, 16, 16, 16, 16, 16, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:23:46,495 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-02-23 23:23:46,691 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:46,692 INFO L402 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:23:46,692 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:23:46,692 INFO L85 PathProgramCache]: Analyzing trace with hash 1664620565, now seen corresponding path program 3 times [2022-02-23 23:23:46,692 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:23:46,692 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1004040054] [2022-02-23 23:23:46,692 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:23:46,692 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:23:46,701 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:23:46,701 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1991831309] [2022-02-23 23:23:46,701 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-02-23 23:23:46,701 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:46,702 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:23:46,702 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) [2022-02-23 23:23:46,703 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-02-23 23:23:47,107 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 28 check-sat command(s) [2022-02-23 23:23:47,107 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 23:23:47,112 INFO L263 TraceCheckSpWp]: Trace formula consists of 738 conjuncts, 22 conjunts are in the unsatisfiable core [2022-02-23 23:23:47,116 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:23:47,451 INFO L134 CoverageAnalysis]: Checked inductivity of 4660 backedges. 2247 proven. 69 refuted. 0 times theorem prover too weak. 2344 trivial. 0 not checked. [2022-02-23 23:23:47,451 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:23:49,293 INFO L134 CoverageAnalysis]: Checked inductivity of 4660 backedges. 491 proven. 85 refuted. 0 times theorem prover too weak. 4084 trivial. 0 not checked. [2022-02-23 23:23:49,293 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:23:49,293 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1004040054] [2022-02-23 23:23:49,293 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:23:49,293 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1991831309] [2022-02-23 23:23:49,293 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1991831309] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:23:49,293 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:23:49,294 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 8] total 11 [2022-02-23 23:23:49,294 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1754377300] [2022-02-23 23:23:49,294 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:23:49,294 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-02-23 23:23:49,294 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:23:49,294 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-02-23 23:23:49,295 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=74, Unknown=0, NotChecked=0, Total=110 [2022-02-23 23:23:49,295 INFO L87 Difference]: Start difference. First operand 815 states and 922 transitions. Second operand has 11 states, 11 states have (on average 6.818181818181818) internal successors, (75), 11 states have internal predecessors, (75), 11 states have call successors, (49), 2 states have call predecessors, (49), 2 states have return successors, (47), 11 states have call predecessors, (47), 11 states have call successors, (47) [2022-02-23 23:23:49,750 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:23:49,750 INFO L93 Difference]: Finished difference Result 1230 states and 1428 transitions. [2022-02-23 23:23:49,752 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-02-23 23:23:49,753 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 6.818181818181818) internal successors, (75), 11 states have internal predecessors, (75), 11 states have call successors, (49), 2 states have call predecessors, (49), 2 states have return successors, (47), 11 states have call predecessors, (47), 11 states have call successors, (47) Word has length 308 [2022-02-23 23:23:49,753 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:23:49,755 INFO L225 Difference]: With dead ends: 1230 [2022-02-23 23:23:49,755 INFO L226 Difference]: Without dead ends: 731 [2022-02-23 23:23:49,756 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 617 GetRequests, 603 SyntacticMatches, 3 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=49, Invalid=107, Unknown=0, NotChecked=0, Total=156 [2022-02-23 23:23:49,757 INFO L933 BasicCegarLoop]: 101 mSDtfsCounter, 19 mSDsluCounter, 411 mSDsCounter, 0 mSdLazyCounter, 265 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 512 SdHoareTripleChecker+Invalid, 277 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 265 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-02-23 23:23:49,757 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [19 Valid, 512 Invalid, 277 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 265 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-02-23 23:23:49,758 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 731 states. [2022-02-23 23:23:49,816 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 731 to 731. [2022-02-23 23:23:49,817 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 731 states, 491 states have (on average 1.1079429735234216) internal successors, (544), 505 states have internal predecessors, (544), 139 states have call successors, (139), 101 states have call predecessors, (139), 100 states have return successors, (137), 124 states have call predecessors, (137), 137 states have call successors, (137) [2022-02-23 23:23:49,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 731 states to 731 states and 820 transitions. [2022-02-23 23:23:49,818 INFO L78 Accepts]: Start accepts. Automaton has 731 states and 820 transitions. Word has length 308 [2022-02-23 23:23:49,819 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:23:49,819 INFO L470 AbstractCegarLoop]: Abstraction has 731 states and 820 transitions. [2022-02-23 23:23:49,819 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 6.818181818181818) internal successors, (75), 11 states have internal predecessors, (75), 11 states have call successors, (49), 2 states have call predecessors, (49), 2 states have return successors, (47), 11 states have call predecessors, (47), 11 states have call successors, (47) [2022-02-23 23:23:49,819 INFO L276 IsEmpty]: Start isEmpty. Operand 731 states and 820 transitions. [2022-02-23 23:23:49,821 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 321 [2022-02-23 23:23:49,821 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:23:49,822 INFO L514 BasicCegarLoop]: trace histogram [49, 48, 48, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:23:49,841 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2022-02-23 23:23:50,041 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:50,041 INFO L402 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:23:50,042 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:23:50,042 INFO L85 PathProgramCache]: Analyzing trace with hash -1611585699, now seen corresponding path program 2 times [2022-02-23 23:23:50,042 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:23:50,042 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [885076509] [2022-02-23 23:23:50,042 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:23:50,042 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:23:50,050 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:23:50,050 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1967686438] [2022-02-23 23:23:50,050 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-02-23 23:23:50,050 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:50,051 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:23:50,055 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) [2022-02-23 23:23:50,087 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2022-02-23 23:23:50,149 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-02-23 23:23:50,149 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 23:23:50,152 INFO L263 TraceCheckSpWp]: Trace formula consists of 747 conjuncts, 25 conjunts are in the unsatisfiable core [2022-02-23 23:23:50,155 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:23:50,579 INFO L134 CoverageAnalysis]: Checked inductivity of 5132 backedges. 2220 proven. 1910 refuted. 0 times theorem prover too weak. 1002 trivial. 0 not checked. [2022-02-23 23:23:50,579 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:23:51,061 INFO L134 CoverageAnalysis]: Checked inductivity of 5132 backedges. 96 proven. 290 refuted. 0 times theorem prover too weak. 4746 trivial. 0 not checked. [2022-02-23 23:23:51,061 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:23:51,061 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [885076509] [2022-02-23 23:23:51,061 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:23:51,061 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1967686438] [2022-02-23 23:23:51,061 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1967686438] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:23:51,061 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:23:51,061 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 24 [2022-02-23 23:23:51,061 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1351106367] [2022-02-23 23:23:51,062 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:23:51,062 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2022-02-23 23:23:51,062 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:23:51,062 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2022-02-23 23:23:51,063 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=236, Invalid=316, Unknown=0, NotChecked=0, Total=552 [2022-02-23 23:23:51,063 INFO L87 Difference]: Start difference. First operand 731 states and 820 transitions. Second operand has 24 states, 24 states have (on average 4.583333333333333) internal successors, (110), 24 states have internal predecessors, (110), 22 states have call successors, (68), 13 states have call predecessors, (68), 13 states have return successors, (66), 21 states have call predecessors, (66), 21 states have call successors, (66) [2022-02-23 23:23:51,610 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:23:51,610 INFO L93 Difference]: Finished difference Result 1022 states and 1148 transitions. [2022-02-23 23:23:51,610 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2022-02-23 23:23:51,610 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 4.583333333333333) internal successors, (110), 24 states have internal predecessors, (110), 22 states have call successors, (68), 13 states have call predecessors, (68), 13 states have return successors, (66), 21 states have call predecessors, (66), 21 states have call successors, (66) Word has length 320 [2022-02-23 23:23:51,611 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:23:51,613 INFO L225 Difference]: With dead ends: 1022 [2022-02-23 23:23:51,613 INFO L226 Difference]: Without dead ends: 733 [2022-02-23 23:23:51,614 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 658 GetRequests, 616 SyntacticMatches, 1 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 237 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=665, Invalid=1141, Unknown=0, NotChecked=0, Total=1806 [2022-02-23 23:23:51,614 INFO L933 BasicCegarLoop]: 113 mSDtfsCounter, 395 mSDsluCounter, 416 mSDsCounter, 0 mSdLazyCounter, 380 mSolverCounterSat, 245 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 395 SdHoareTripleChecker+Valid, 529 SdHoareTripleChecker+Invalid, 625 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 245 IncrementalHoareTripleChecker+Valid, 380 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-02-23 23:23:51,614 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [395 Valid, 529 Invalid, 625 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [245 Valid, 380 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-02-23 23:23:51,615 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 733 states. [2022-02-23 23:23:51,677 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 733 to 733. [2022-02-23 23:23:51,678 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 733 states, 493 states have (on average 1.0892494929006085) internal successors, (537), 507 states have internal predecessors, (537), 139 states have call successors, (139), 101 states have call predecessors, (139), 100 states have return successors, (137), 124 states have call predecessors, (137), 137 states have call successors, (137) [2022-02-23 23:23:51,680 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 733 states to 733 states and 813 transitions. [2022-02-23 23:23:51,680 INFO L78 Accepts]: Start accepts. Automaton has 733 states and 813 transitions. Word has length 320 [2022-02-23 23:23:51,680 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:23:51,680 INFO L470 AbstractCegarLoop]: Abstraction has 733 states and 813 transitions. [2022-02-23 23:23:51,681 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 4.583333333333333) internal successors, (110), 24 states have internal predecessors, (110), 22 states have call successors, (68), 13 states have call predecessors, (68), 13 states have return successors, (66), 21 states have call predecessors, (66), 21 states have call successors, (66) [2022-02-23 23:23:51,681 INFO L276 IsEmpty]: Start isEmpty. Operand 733 states and 813 transitions. [2022-02-23 23:23:51,683 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 321 [2022-02-23 23:23:51,683 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:23:51,683 INFO L514 BasicCegarLoop]: trace histogram [48, 47, 47, 14, 13, 13, 13, 13, 13, 13, 13, 7, 7, 7, 7, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:23:51,703 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2022-02-23 23:23:51,899 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable22,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:51,900 INFO L402 AbstractCegarLoop]: === Iteration 24 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:23:51,900 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:23:51,900 INFO L85 PathProgramCache]: Analyzing trace with hash 1950046478, now seen corresponding path program 4 times [2022-02-23 23:23:51,900 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:23:51,900 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [973011939] [2022-02-23 23:23:51,900 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:23:51,900 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:23:51,908 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:23:51,908 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [494576530] [2022-02-23 23:23:51,908 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-02-23 23:23:51,908 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:23:51,908 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:23:51,913 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) [2022-02-23 23:23:51,939 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2022-02-23 23:24:06,501 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-02-23 23:24:06,502 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 23:24:06,521 INFO L263 TraceCheckSpWp]: Trace formula consists of 759 conjuncts, 30 conjunts are in the unsatisfiable core [2022-02-23 23:24:06,525 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:24:06,901 INFO L134 CoverageAnalysis]: Checked inductivity of 5038 backedges. 2016 proven. 246 refuted. 0 times theorem prover too weak. 2776 trivial. 0 not checked. [2022-02-23 23:24:06,902 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:24:08,698 INFO L134 CoverageAnalysis]: Checked inductivity of 5038 backedges. 389 proven. 217 refuted. 0 times theorem prover too weak. 4432 trivial. 0 not checked. [2022-02-23 23:24:08,699 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:24:08,699 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [973011939] [2022-02-23 23:24:08,699 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:24:08,699 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [494576530] [2022-02-23 23:24:08,699 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [494576530] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:24:08,699 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:24:08,699 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2022-02-23 23:24:08,699 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1042003374] [2022-02-23 23:24:08,699 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:24:08,700 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-02-23 23:24:08,700 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:24:08,700 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-02-23 23:24:08,700 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=164, Unknown=0, NotChecked=0, Total=210 [2022-02-23 23:24:08,701 INFO L87 Difference]: Start difference. First operand 733 states and 813 transitions. Second operand has 15 states, 15 states have (on average 7.066666666666666) internal successors, (106), 15 states have internal predecessors, (106), 15 states have call successors, (72), 2 states have call predecessors, (72), 2 states have return successors, (70), 15 states have call predecessors, (70), 15 states have call successors, (70) [2022-02-23 23:24:08,939 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:24:08,939 INFO L93 Difference]: Finished difference Result 956 states and 1087 transitions. [2022-02-23 23:24:08,939 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-02-23 23:24:08,940 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 7.066666666666666) internal successors, (106), 15 states have internal predecessors, (106), 15 states have call successors, (72), 2 states have call predecessors, (72), 2 states have return successors, (70), 15 states have call predecessors, (70), 15 states have call successors, (70) Word has length 320 [2022-02-23 23:24:08,940 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:24:08,943 INFO L225 Difference]: With dead ends: 956 [2022-02-23 23:24:08,943 INFO L226 Difference]: Without dead ends: 705 [2022-02-23 23:24:08,944 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 639 GetRequests, 623 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=46, Invalid=164, Unknown=0, NotChecked=0, Total=210 [2022-02-23 23:24:08,945 INFO L933 BasicCegarLoop]: 126 mSDtfsCounter, 18 mSDsluCounter, 451 mSDsCounter, 0 mSdLazyCounter, 294 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 577 SdHoareTripleChecker+Invalid, 300 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 294 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-02-23 23:24:08,946 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [18 Valid, 577 Invalid, 300 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 294 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-02-23 23:24:08,946 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 705 states. [2022-02-23 23:24:09,001 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 705 to 705. [2022-02-23 23:24:09,002 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 705 states, 474 states have (on average 1.0864978902953586) internal successors, (515), 487 states have internal predecessors, (515), 133 states have call successors, (133), 98 states have call predecessors, (133), 97 states have return successors, (131), 119 states have call predecessors, (131), 131 states have call successors, (131) [2022-02-23 23:24:09,003 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 705 states to 705 states and 779 transitions. [2022-02-23 23:24:09,003 INFO L78 Accepts]: Start accepts. Automaton has 705 states and 779 transitions. Word has length 320 [2022-02-23 23:24:09,004 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:24:09,004 INFO L470 AbstractCegarLoop]: Abstraction has 705 states and 779 transitions. [2022-02-23 23:24:09,004 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 7.066666666666666) internal successors, (106), 15 states have internal predecessors, (106), 15 states have call successors, (72), 2 states have call predecessors, (72), 2 states have return successors, (70), 15 states have call predecessors, (70), 15 states have call successors, (70) [2022-02-23 23:24:09,004 INFO L276 IsEmpty]: Start isEmpty. Operand 705 states and 779 transitions. [2022-02-23 23:24:09,007 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 325 [2022-02-23 23:24:09,007 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:24:09,007 INFO L514 BasicCegarLoop]: trace histogram [49, 48, 48, 13, 12, 12, 12, 12, 12, 12, 12, 8, 8, 8, 8, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:24:09,020 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2022-02-23 23:24:09,219 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable23 [2022-02-23 23:24:09,220 INFO L402 AbstractCegarLoop]: === Iteration 25 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:24:09,220 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:24:09,220 INFO L85 PathProgramCache]: Analyzing trace with hash 179823329, now seen corresponding path program 5 times [2022-02-23 23:24:09,220 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:24:09,220 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1852287132] [2022-02-23 23:24:09,220 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:24:09,221 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:24:09,230 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:24:09,230 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2076109544] [2022-02-23 23:24:09,230 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-02-23 23:24:09,230 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:24:09,230 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:24:09,231 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-02-23 23:24:09,232 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2022-02-23 23:24:21,942 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 24 check-sat command(s) [2022-02-23 23:24:21,943 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 23:24:21,958 INFO L263 TraceCheckSpWp]: Trace formula consists of 763 conjuncts, 38 conjunts are in the unsatisfiable core [2022-02-23 23:24:21,962 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:24:22,326 INFO L134 CoverageAnalysis]: Checked inductivity of 5196 backedges. 1571 proven. 329 refuted. 0 times theorem prover too weak. 3296 trivial. 0 not checked. [2022-02-23 23:24:22,326 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:24:26,886 INFO L134 CoverageAnalysis]: Checked inductivity of 5196 backedges. 397 proven. 239 refuted. 0 times theorem prover too weak. 4560 trivial. 0 not checked. [2022-02-23 23:24:26,886 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 23:24:26,886 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1852287132] [2022-02-23 23:24:26,886 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 23:24:26,886 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2076109544] [2022-02-23 23:24:26,886 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2076109544] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 23:24:26,886 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 23:24:26,887 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2022-02-23 23:24:26,887 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1015444558] [2022-02-23 23:24:26,887 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 23:24:26,887 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-02-23 23:24:26,887 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 23:24:26,887 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-02-23 23:24:26,888 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=199, Unknown=0, NotChecked=0, Total=272 [2022-02-23 23:24:26,888 INFO L87 Difference]: Start difference. First operand 705 states and 779 transitions. Second operand has 17 states, 17 states have (on average 7.0588235294117645) internal successors, (120), 17 states have internal predecessors, (120), 17 states have call successors, (82), 2 states have call predecessors, (82), 2 states have return successors, (80), 17 states have call predecessors, (80), 17 states have call successors, (80) [2022-02-23 23:24:27,196 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 23:24:27,196 INFO L93 Difference]: Finished difference Result 892 states and 1017 transitions. [2022-02-23 23:24:27,196 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-02-23 23:24:27,197 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 7.0588235294117645) internal successors, (120), 17 states have internal predecessors, (120), 17 states have call successors, (82), 2 states have call predecessors, (82), 2 states have return successors, (80), 17 states have call predecessors, (80), 17 states have call successors, (80) Word has length 324 [2022-02-23 23:24:27,197 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 23:24:27,199 INFO L225 Difference]: With dead ends: 892 [2022-02-23 23:24:27,199 INFO L226 Difference]: Without dead ends: 677 [2022-02-23 23:24:27,199 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 647 GetRequests, 626 SyntacticMatches, 6 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=73, Invalid=199, Unknown=0, NotChecked=0, Total=272 [2022-02-23 23:24:27,200 INFO L933 BasicCegarLoop]: 141 mSDtfsCounter, 22 mSDsluCounter, 606 mSDsCounter, 0 mSdLazyCounter, 406 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 747 SdHoareTripleChecker+Invalid, 413 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 406 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-02-23 23:24:27,200 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 747 Invalid, 413 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 406 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-02-23 23:24:27,200 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 677 states. [2022-02-23 23:24:27,251 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 677 to 677. [2022-02-23 23:24:27,253 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 677 states, 455 states have (on average 1.0835164835164834) internal successors, (493), 467 states have internal predecessors, (493), 127 states have call successors, (127), 95 states have call predecessors, (127), 94 states have return successors, (125), 114 states have call predecessors, (125), 125 states have call successors, (125) [2022-02-23 23:24:27,254 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 677 states to 677 states and 745 transitions. [2022-02-23 23:24:27,254 INFO L78 Accepts]: Start accepts. Automaton has 677 states and 745 transitions. Word has length 324 [2022-02-23 23:24:27,254 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 23:24:27,254 INFO L470 AbstractCegarLoop]: Abstraction has 677 states and 745 transitions. [2022-02-23 23:24:27,255 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 7.0588235294117645) internal successors, (120), 17 states have internal predecessors, (120), 17 states have call successors, (82), 2 states have call predecessors, (82), 2 states have return successors, (80), 17 states have call predecessors, (80), 17 states have call successors, (80) [2022-02-23 23:24:27,255 INFO L276 IsEmpty]: Start isEmpty. Operand 677 states and 745 transitions. [2022-02-23 23:24:27,256 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 329 [2022-02-23 23:24:27,256 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 23:24:27,256 INFO L514 BasicCegarLoop]: trace histogram [50, 49, 49, 12, 11, 11, 11, 11, 11, 11, 11, 9, 9, 9, 9, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 23:24:27,267 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2022-02-23 23:24:27,467 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable24 [2022-02-23 23:24:27,467 INFO L402 AbstractCegarLoop]: === Iteration 26 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 23:24:27,468 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 23:24:27,468 INFO L85 PathProgramCache]: Analyzing trace with hash -1085750924, now seen corresponding path program 6 times [2022-02-23 23:24:27,468 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 23:24:27,468 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [658118258] [2022-02-23 23:24:27,468 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 23:24:27,468 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 23:24:27,480 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 23:24:27,480 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [799039854] [2022-02-23 23:24:27,480 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-02-23 23:24:27,480 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 23:24:27,481 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 23:24:27,481 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-02-23 23:24:27,482 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2022-02-23 23:24:27,788 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 22 check-sat command(s) [2022-02-23 23:24:27,788 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 23:24:27,792 INFO L263 TraceCheckSpWp]: Trace formula consists of 767 conjuncts, 115 conjunts are in the unsatisfiable core [2022-02-23 23:24:27,796 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 23:24:29,214 INFO L134 CoverageAnalysis]: Checked inductivity of 5370 backedges. 1317 proven. 541 refuted. 0 times theorem prover too weak. 3512 trivial. 0 not checked. [2022-02-23 23:24:29,214 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 23:24:55,499 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-02-23 23:25:33,907 WARN L232 SmtUtils]: Spent 18.10s on a formula simplification that was a NOOP. DAG size: 165 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-02-23 23:26:32,936 WARN L232 SmtUtils]: Spent 27.79s on a formula simplification that was a NOOP. DAG size: 104 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate)