/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/hard-ll_valuebound10.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7968f31 [2022-03-17 21:45:05,784 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-17 21:45:05,785 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-17 21:45:05,822 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-17 21:45:05,822 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-17 21:45:05,824 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-17 21:45:05,828 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-17 21:45:05,834 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-17 21:45:05,835 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-17 21:45:05,838 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-17 21:45:05,839 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-17 21:45:05,839 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-17 21:45:05,840 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-17 21:45:05,840 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-17 21:45:05,841 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-17 21:45:05,842 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-17 21:45:05,842 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-17 21:45:05,843 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-17 21:45:05,844 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-17 21:45:05,845 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-17 21:45:05,846 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-17 21:45:05,852 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-17 21:45:05,853 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-17 21:45:05,854 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-17 21:45:05,855 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-17 21:45:05,865 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-17 21:45:05,865 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-17 21:45:05,865 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-17 21:45:05,866 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-17 21:45:05,867 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-17 21:45:05,868 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-17 21:45:05,868 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-17 21:45:05,868 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-17 21:45:05,869 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-17 21:45:05,869 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-17 21:45:05,870 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-17 21:45:05,870 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-17 21:45:05,870 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-17 21:45:05,871 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-17 21:45:05,871 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-17 21:45:05,871 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-17 21:45:05,872 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-17 21:45:05,872 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-03-17 21:45:05,899 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-17 21:45:05,900 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-17 21:45:05,902 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-17 21:45:05,902 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-17 21:45:05,903 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-17 21:45:05,903 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-17 21:45:05,903 INFO L138 SettingsManager]: * Use SBE=true [2022-03-17 21:45:05,903 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-17 21:45:05,903 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-17 21:45:05,904 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-17 21:45:05,904 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-17 21:45:05,904 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-17 21:45:05,904 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-17 21:45:05,904 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-17 21:45:05,905 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-17 21:45:05,905 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-17 21:45:05,905 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-17 21:45:05,905 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-17 21:45:05,905 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-17 21:45:05,905 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 21:45:05,905 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-17 21:45:05,906 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-03-17 21:45:05,906 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-17 21:45:05,906 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-17 21:45:05,906 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-17 21:45:05,906 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-17 21:45:05,906 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-03-17 21:45:05,907 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-03-17 21:45:05,908 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-17 21:45:05,908 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-03-17 21:45:06,133 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-17 21:45:06,153 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-17 21:45:06,155 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-17 21:45:06,155 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-17 21:45:06,157 INFO L275 PluginConnector]: CDTParser initialized [2022-03-17 21:45:06,158 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound10.c [2022-03-17 21:45:06,235 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/07fe5e19f/8b776ff9ad784a25b58b07784df83bfe/FLAGd9d493c18 [2022-03-17 21:45:06,586 INFO L306 CDTParser]: Found 1 translation units. [2022-03-17 21:45:06,587 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound10.c [2022-03-17 21:45:06,595 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/07fe5e19f/8b776ff9ad784a25b58b07784df83bfe/FLAGd9d493c18 [2022-03-17 21:45:06,604 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/07fe5e19f/8b776ff9ad784a25b58b07784df83bfe [2022-03-17 21:45:06,606 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-17 21:45:06,607 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-17 21:45:06,609 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-17 21:45:06,609 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-17 21:45:06,614 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-17 21:45:06,614 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 09:45:06" (1/1) ... [2022-03-17 21:45:06,615 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4e171342 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:06, skipping insertion in model container [2022-03-17 21:45:06,615 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 09:45:06" (1/1) ... [2022-03-17 21:45:06,622 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-17 21:45:06,641 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-17 21:45:06,857 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/hard-ll_valuebound10.c[538,551] [2022-03-17 21:45:06,872 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 21:45:06,877 INFO L203 MainTranslator]: Completed pre-run [2022-03-17 21:45:06,886 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/hard-ll_valuebound10.c[538,551] [2022-03-17 21:45:06,892 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 21:45:06,902 INFO L208 MainTranslator]: Completed translation [2022-03-17 21:45:06,902 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:06 WrapperNode [2022-03-17 21:45:06,903 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-17 21:45:06,904 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-17 21:45:06,904 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-17 21:45:06,904 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-17 21:45:06,913 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:06" (1/1) ... [2022-03-17 21:45:06,913 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:06" (1/1) ... [2022-03-17 21:45:06,918 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:06" (1/1) ... [2022-03-17 21:45:06,919 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:06" (1/1) ... [2022-03-17 21:45:06,922 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:06" (1/1) ... [2022-03-17 21:45:06,925 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:06" (1/1) ... [2022-03-17 21:45:06,926 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:06" (1/1) ... [2022-03-17 21:45:06,927 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-17 21:45:06,928 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-17 21:45:06,928 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-17 21:45:06,928 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-17 21:45:06,929 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:06" (1/1) ... [2022-03-17 21:45:06,934 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 21:45:06,943 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:45:06,956 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-03-17 21:45:06,960 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-03-17 21:45:06,986 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-17 21:45:06,986 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-17 21:45:06,986 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-17 21:45:06,986 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-17 21:45:06,987 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-17 21:45:06,987 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-17 21:45:06,987 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-17 21:45:06,987 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-17 21:45:06,987 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-17 21:45:06,987 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-17 21:45:06,987 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-03-17 21:45:06,988 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-17 21:45:06,988 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-17 21:45:06,988 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-17 21:45:06,988 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-17 21:45:06,988 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-17 21:45:06,988 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-17 21:45:06,988 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-17 21:45:06,988 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-17 21:45:06,989 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-17 21:45:07,041 INFO L234 CfgBuilder]: Building ICFG [2022-03-17 21:45:07,042 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-17 21:45:07,139 INFO L275 CfgBuilder]: Performing block encoding [2022-03-17 21:45:07,144 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-17 21:45:07,144 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-17 21:45:07,146 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 09:45:07 BoogieIcfgContainer [2022-03-17 21:45:07,146 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-17 21:45:07,147 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-17 21:45:07,147 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-17 21:45:07,147 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-17 21:45:07,155 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 09:45:07" (1/1) ... [2022-03-17 21:45:07,194 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 09:45:07 BasicIcfg [2022-03-17 21:45:07,194 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-17 21:45:07,196 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-17 21:45:07,196 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-17 21:45:07,198 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-17 21:45:07,198 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 17.03 09:45:06" (1/4) ... [2022-03-17 21:45:07,199 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@69588e7c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 09:45:07, skipping insertion in model container [2022-03-17 21:45:07,199 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 09:45:06" (2/4) ... [2022-03-17 21:45:07,199 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@69588e7c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 09:45:07, skipping insertion in model container [2022-03-17 21:45:07,199 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 09:45:07" (3/4) ... [2022-03-17 21:45:07,199 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@69588e7c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 17.03 09:45:07, skipping insertion in model container [2022-03-17 21:45:07,199 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 09:45:07" (4/4) ... [2022-03-17 21:45:07,200 INFO L111 eAbstractionObserver]: Analyzing ICFG hard-ll_valuebound10.cqvasr [2022-03-17 21:45:07,219 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-03-17 21:45:07,220 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-17 21:45:07,278 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-17 21:45:07,283 INFO L340 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 [2022-03-17 21:45:07,283 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-17 21:45:07,297 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-17 21:45:07,301 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-17 21:45:07,301 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:07,302 INFO L500 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:45:07,302 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:07,306 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:07,306 INFO L85 PathProgramCache]: Analyzing trace with hash 1011787902, now seen corresponding path program 1 times [2022-03-17 21:45:07,313 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:07,315 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1749345691] [2022-03-17 21:45:07,315 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:07,316 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:07,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:07,448 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-17 21:45:07,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:07,458 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-17 21:45:07,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:07,465 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-17 21:45:07,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:07,470 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-17 21:45:07,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:07,477 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-17 21:45:07,477 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:07,477 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1749345691] [2022-03-17 21:45:07,478 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1749345691] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:45:07,478 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:45:07,478 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-17 21:45:07,479 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [214987030] [2022-03-17 21:45:07,480 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:07,483 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-17 21:45:07,484 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:07,504 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-17 21:45:07,504 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-17 21:45:07,506 INFO L87 Difference]: Start difference. First operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-17 21:45:07,575 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:07,575 INFO L93 Difference]: Finished difference Result 69 states and 110 transitions. [2022-03-17 21:45:07,584 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-17 21:45:07,585 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 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 28 [2022-03-17 21:45:07,585 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:07,591 INFO L225 Difference]: With dead ends: 69 [2022-03-17 21:45:07,591 INFO L226 Difference]: Without dead ends: 33 [2022-03-17 21:45:07,593 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 12 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-03-17 21:45:07,596 INFO L912 BasicCegarLoop]: 38 mSDtfsCounter, 21 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:45:07,597 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 41 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:45:07,613 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-03-17 21:45:07,629 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-03-17 21:45:07,630 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-17 21:45:07,631 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2022-03-17 21:45:07,632 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 28 [2022-03-17 21:45:07,632 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:07,633 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2022-03-17 21:45:07,633 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-17 21:45:07,633 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-03-17 21:45:07,634 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-17 21:45:07,634 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:07,635 INFO L500 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:45:07,635 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-17 21:45:07,635 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:07,636 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:07,636 INFO L85 PathProgramCache]: Analyzing trace with hash -1710049411, now seen corresponding path program 1 times [2022-03-17 21:45:07,636 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:07,636 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1921311695] [2022-03-17 21:45:07,636 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:07,636 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:07,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:07,715 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-17 21:45:07,718 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:07,726 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-17 21:45:07,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:07,739 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-17 21:45:07,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:07,759 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-17 21:45:07,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:07,764 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-17 21:45:07,765 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:07,765 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1921311695] [2022-03-17 21:45:07,765 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1921311695] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:45:07,765 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:45:07,765 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-17 21:45:07,766 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1212491807] [2022-03-17 21:45:07,766 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:07,767 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-17 21:45:07,767 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:07,768 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-17 21:45:07,768 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-17 21:45:07,768 INFO L87 Difference]: Start difference. First operand 33 states and 43 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-03-17 21:45:07,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:07,925 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-03-17 21:45:07,925 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-17 21:45:07,926 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2022-03-17 21:45:07,926 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:07,927 INFO L225 Difference]: With dead ends: 46 [2022-03-17 21:45:07,927 INFO L226 Difference]: Without dead ends: 44 [2022-03-17 21:45:07,927 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 9 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-03-17 21:45:07,929 INFO L912 BasicCegarLoop]: 31 mSDtfsCounter, 38 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 155 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 21:45:07,929 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 48 Invalid, 155 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 21:45:07,930 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-03-17 21:45:07,938 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-03-17 21:45:07,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-17 21:45:07,939 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 46 transitions. [2022-03-17 21:45:07,939 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 46 transitions. Word has length 28 [2022-03-17 21:45:07,939 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:07,940 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 46 transitions. [2022-03-17 21:45:07,940 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-03-17 21:45:07,940 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 46 transitions. [2022-03-17 21:45:07,941 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-03-17 21:45:07,941 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:07,941 INFO L500 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:45:07,941 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-17 21:45:07,941 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:07,942 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:07,942 INFO L85 PathProgramCache]: Analyzing trace with hash 1042498848, now seen corresponding path program 1 times [2022-03-17 21:45:07,942 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:07,942 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2102742101] [2022-03-17 21:45:07,942 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:07,942 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:07,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:08,010 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-17 21:45:08,012 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:08,026 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-17 21:45:08,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:08,033 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-17 21:45:08,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:08,042 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-17 21:45:08,043 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:08,048 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2022-03-17 21:45:08,051 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:08,059 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-17 21:45:08,059 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:08,060 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2102742101] [2022-03-17 21:45:08,060 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2102742101] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:45:08,060 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:45:08,060 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-17 21:45:08,060 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1197511114] [2022-03-17 21:45:08,060 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:08,061 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-17 21:45:08,061 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:08,061 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-17 21:45:08,062 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-17 21:45:08,062 INFO L87 Difference]: Start difference. First operand 37 states and 46 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-17 21:45:08,246 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:08,246 INFO L93 Difference]: Finished difference Result 50 states and 63 transitions. [2022-03-17 21:45:08,246 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-17 21:45:08,246 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-03-17 21:45:08,247 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:08,250 INFO L225 Difference]: With dead ends: 50 [2022-03-17 21:45:08,250 INFO L226 Difference]: Without dead ends: 48 [2022-03-17 21:45:08,251 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 11 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-03-17 21:45:08,258 INFO L912 BasicCegarLoop]: 31 mSDtfsCounter, 33 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 21:45:08,259 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 48 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 132 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 21:45:08,261 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-03-17 21:45:08,274 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 41. [2022-03-17 21:45:08,274 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-17 21:45:08,275 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2022-03-17 21:45:08,275 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 33 [2022-03-17 21:45:08,275 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:08,276 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2022-03-17 21:45:08,276 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-17 21:45:08,276 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2022-03-17 21:45:08,277 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-03-17 21:45:08,277 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:08,277 INFO L500 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:45:08,277 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-03-17 21:45:08,277 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:08,278 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:08,278 INFO L85 PathProgramCache]: Analyzing trace with hash 1436069466, now seen corresponding path program 1 times [2022-03-17 21:45:08,278 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:08,278 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [325632447] [2022-03-17 21:45:08,278 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:08,278 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:08,292 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:45:08,292 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [242513208] [2022-03-17 21:45:08,292 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:08,292 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:08,293 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:45:08,295 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-03-17 21:45:08,304 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-03-17 21:45:08,357 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:08,359 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-17 21:45:08,373 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:45:08,653 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2022-03-17 21:45:08,654 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 21:45:08,654 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:08,654 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [325632447] [2022-03-17 21:45:08,654 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:45:08,654 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [242513208] [2022-03-17 21:45:08,655 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [242513208] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:45:08,655 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:45:08,655 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-03-17 21:45:08,655 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2027832003] [2022-03-17 21:45:08,655 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:08,656 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-17 21:45:08,656 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:08,656 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-17 21:45:08,656 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2022-03-17 21:45:08,657 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-17 21:45:08,796 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:08,797 INFO L93 Difference]: Finished difference Result 69 states and 89 transitions. [2022-03-17 21:45:08,797 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-17 21:45:08,797 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) Word has length 38 [2022-03-17 21:45:08,798 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:08,799 INFO L225 Difference]: With dead ends: 69 [2022-03-17 21:45:08,800 INFO L226 Difference]: Without dead ends: 55 [2022-03-17 21:45:08,801 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2022-03-17 21:45:08,809 INFO L912 BasicCegarLoop]: 40 mSDtfsCounter, 20 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 225 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 21:45:08,810 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 225 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 99 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 21:45:08,811 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-03-17 21:45:08,826 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-03-17 21:45:08,827 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 30 states have (on average 1.1666666666666667) internal successors, (35), 32 states have internal predecessors, (35), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-03-17 21:45:08,832 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-03-17 21:45:08,833 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 38 [2022-03-17 21:45:08,833 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:08,834 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-03-17 21:45:08,834 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-17 21:45:08,836 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-03-17 21:45:08,838 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-03-17 21:45:08,840 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:08,840 INFO L500 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:45:08,868 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-03-17 21:45:09,065 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:09,065 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:09,065 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:09,066 INFO L85 PathProgramCache]: Analyzing trace with hash 5711864, now seen corresponding path program 1 times [2022-03-17 21:45:09,066 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:09,066 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [575621529] [2022-03-17 21:45:09,066 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:09,066 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:09,077 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:45:09,078 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [582538663] [2022-03-17 21:45:09,078 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:09,078 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:09,078 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:45:09,087 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-03-17 21:45:09,090 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-03-17 21:45:09,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:09,128 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-17 21:45:09,131 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:45:09,385 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 9 proven. 3 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-03-17 21:45:09,386 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:45:09,562 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-17 21:45:09,563 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:09,564 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [575621529] [2022-03-17 21:45:09,564 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:45:09,564 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [582538663] [2022-03-17 21:45:09,566 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [582538663] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-17 21:45:09,566 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-17 21:45:09,566 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [9] total 11 [2022-03-17 21:45:09,566 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2122361689] [2022-03-17 21:45:09,566 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:09,567 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-17 21:45:09,567 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:09,567 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-17 21:45:09,567 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-03-17 21:45:09,568 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-17 21:45:09,626 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:09,626 INFO L93 Difference]: Finished difference Result 68 states and 85 transitions. [2022-03-17 21:45:09,626 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 21:45:09,627 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 45 [2022-03-17 21:45:09,627 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:09,628 INFO L225 Difference]: With dead ends: 68 [2022-03-17 21:45:09,628 INFO L226 Difference]: Without dead ends: 66 [2022-03-17 21:45:09,628 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-03-17 21:45:09,629 INFO L912 BasicCegarLoop]: 42 mSDtfsCounter, 16 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:45:09,629 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 145 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:45:09,630 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-03-17 21:45:09,640 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 64. [2022-03-17 21:45:09,640 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 36 states have (on average 1.1944444444444444) internal successors, (43), 38 states have internal predecessors, (43), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-03-17 21:45:09,641 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 80 transitions. [2022-03-17 21:45:09,641 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 80 transitions. Word has length 45 [2022-03-17 21:45:09,641 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:09,642 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 80 transitions. [2022-03-17 21:45:09,642 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-17 21:45:09,642 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 80 transitions. [2022-03-17 21:45:09,643 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-03-17 21:45:09,643 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:09,643 INFO L500 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:45:09,668 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-03-17 21:45:09,866 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:09,866 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:09,866 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:09,867 INFO L85 PathProgramCache]: Analyzing trace with hash 1597443315, now seen corresponding path program 1 times [2022-03-17 21:45:09,867 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:09,867 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [660686562] [2022-03-17 21:45:09,867 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:09,867 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:09,886 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:45:09,887 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [247909585] [2022-03-17 21:45:09,887 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:09,887 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:09,887 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:45:09,889 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-03-17 21:45:09,892 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-03-17 21:45:09,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:09,963 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 16 conjunts are in the unsatisfiable core [2022-03-17 21:45:09,967 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:45:10,188 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 16 proven. 4 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2022-03-17 21:45:10,189 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:45:10,318 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2022-03-17 21:45:10,318 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:10,318 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [660686562] [2022-03-17 21:45:10,318 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:45:10,318 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [247909585] [2022-03-17 21:45:10,319 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [247909585] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-17 21:45:10,319 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-17 21:45:10,319 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-03-17 21:45:10,319 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [184053573] [2022-03-17 21:45:10,319 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:10,321 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:45:10,321 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:10,321 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:45:10,321 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-03-17 21:45:10,322 INFO L87 Difference]: Start difference. First operand 64 states and 80 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-17 21:45:10,369 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:10,370 INFO L93 Difference]: Finished difference Result 76 states and 95 transitions. [2022-03-17 21:45:10,370 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 21:45:10,370 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 55 [2022-03-17 21:45:10,371 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:10,373 INFO L225 Difference]: With dead ends: 76 [2022-03-17 21:45:10,373 INFO L226 Difference]: Without dead ends: 74 [2022-03-17 21:45:10,374 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 99 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-03-17 21:45:10,375 INFO L912 BasicCegarLoop]: 41 mSDtfsCounter, 8 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:45:10,375 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 141 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:45:10,376 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2022-03-17 21:45:10,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2022-03-17 21:45:10,400 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 40 states have (on average 1.175) internal successors, (47), 43 states have internal predecessors, (47), 22 states have call successors, (22), 9 states have call predecessors, (22), 8 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-03-17 21:45:10,401 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 88 transitions. [2022-03-17 21:45:10,401 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 88 transitions. Word has length 55 [2022-03-17 21:45:10,402 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:10,402 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 88 transitions. [2022-03-17 21:45:10,402 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-17 21:45:10,402 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 88 transitions. [2022-03-17 21:45:10,404 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-03-17 21:45:10,404 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:10,405 INFO L500 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:45:10,432 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-03-17 21:45:10,627 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:10,628 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:10,628 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:10,628 INFO L85 PathProgramCache]: Analyzing trace with hash 810354846, now seen corresponding path program 1 times [2022-03-17 21:45:10,628 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:10,628 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [629457215] [2022-03-17 21:45:10,628 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:10,628 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:10,644 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:45:10,645 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2135831650] [2022-03-17 21:45:10,645 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:10,645 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:10,645 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:45:10,652 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-03-17 21:45:10,654 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-03-17 21:45:10,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:10,692 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 21:45:10,694 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:45:10,831 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-03-17 21:45:10,831 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 21:45:10,831 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:45:10,832 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [629457215] [2022-03-17 21:45:10,832 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:45:10,832 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2135831650] [2022-03-17 21:45:10,832 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2135831650] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:45:10,832 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:45:10,832 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-17 21:45:10,832 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1838671740] [2022-03-17 21:45:10,832 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:45:10,834 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:45:10,834 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:45:10,834 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:45:10,834 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-17 21:45:10,834 INFO L87 Difference]: Start difference. First operand 71 states and 88 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-03-17 21:45:10,892 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:45:10,892 INFO L93 Difference]: Finished difference Result 79 states and 96 transitions. [2022-03-17 21:45:10,892 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 21:45:10,892 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 56 [2022-03-17 21:45:10,894 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:45:10,896 INFO L225 Difference]: With dead ends: 79 [2022-03-17 21:45:10,896 INFO L226 Difference]: Without dead ends: 72 [2022-03-17 21:45:10,896 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 52 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-03-17 21:45:10,897 INFO L912 BasicCegarLoop]: 36 mSDtfsCounter, 8 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:45:10,897 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 132 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:45:10,899 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2022-03-17 21:45:10,907 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 71. [2022-03-17 21:45:10,907 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 41 states have (on average 1.146341463414634) internal successors, (47), 44 states have internal predecessors, (47), 20 states have call successors, (20), 10 states have call predecessors, (20), 9 states have return successors, (18), 16 states have call predecessors, (18), 18 states have call successors, (18) [2022-03-17 21:45:10,908 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 85 transitions. [2022-03-17 21:45:10,908 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 85 transitions. Word has length 56 [2022-03-17 21:45:10,908 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:45:10,908 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 85 transitions. [2022-03-17 21:45:10,909 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-03-17 21:45:10,909 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 85 transitions. [2022-03-17 21:45:10,910 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-03-17 21:45:10,910 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:45:10,910 INFO L500 BasicCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:45:10,935 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-03-17 21:45:11,123 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:11,123 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:45:11,124 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:45:11,124 INFO L85 PathProgramCache]: Analyzing trace with hash 1689231171, now seen corresponding path program 1 times [2022-03-17 21:45:11,124 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:45:11,124 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [142596576] [2022-03-17 21:45:11,124 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:11,124 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:45:11,133 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:45:11,134 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1188987848] [2022-03-17 21:45:11,134 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:45:11,134 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:45:11,134 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:45:11,138 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-03-17 21:45:11,138 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-03-17 21:45:11,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:45:11,213 INFO L263 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 30 conjunts are in the unsatisfiable core [2022-03-17 21:45:11,215 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:45:11,968 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 36 proven. 8 refuted. 0 times theorem prover too weak. 103 trivial. 0 not checked. [2022-03-17 21:45:11,968 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:45:48,112 WARN L232 SmtUtils]: Spent 23.52s on a formula simplification that was a NOOP. DAG size: 53 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 21:46:44,250 WARN L232 SmtUtils]: Spent 15.28s on a formula simplification that was a NOOP. DAG size: 54 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 21:47:34,123 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 36 proven. 8 refuted. 0 times theorem prover too weak. 103 trivial. 0 not checked. [2022-03-17 21:47:34,124 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:47:34,124 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [142596576] [2022-03-17 21:47:34,124 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:47:34,124 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1188987848] [2022-03-17 21:47:34,124 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1188987848] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:47:34,124 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:47:34,124 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12] total 18 [2022-03-17 21:47:34,125 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [477202679] [2022-03-17 21:47:34,125 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:47:34,125 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-03-17 21:47:34,125 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:47:34,126 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-03-17 21:47:34,126 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=241, Unknown=0, NotChecked=0, Total=306 [2022-03-17 21:47:34,126 INFO L87 Difference]: Start difference. First operand 71 states and 85 transitions. Second operand has 18 states, 18 states have (on average 2.0) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) [2022-03-17 21:47:36,561 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.47s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 21:47:47,616 WARN L232 SmtUtils]: Spent 10.90s on a formula simplification. DAG size of input: 57 DAG size of output: 27 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 21:48:09,795 WARN L232 SmtUtils]: Spent 20.28s on a formula simplification that was a NOOP. DAG size: 70 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 21:48:19,686 WARN L232 SmtUtils]: Spent 8.10s on a formula simplification. DAG size of input: 58 DAG size of output: 27 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 21:48:21,322 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.38s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 21:48:27,588 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:48:27,589 INFO L93 Difference]: Finished difference Result 148 states and 194 transitions. [2022-03-17 21:48:27,589 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2022-03-17 21:48:27,589 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 2.0) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) Word has length 75 [2022-03-17 21:48:27,590 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:48:27,591 INFO L225 Difference]: With dead ends: 148 [2022-03-17 21:48:27,591 INFO L226 Difference]: Without dead ends: 121 [2022-03-17 21:48:27,592 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 131 SyntacticMatches, 2 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 111 ImplicationChecksByTransitivity, 87.5s TimeCoverageRelationStatistics Valid=136, Invalid=514, Unknown=0, NotChecked=0, Total=650 [2022-03-17 21:48:27,592 INFO L912 BasicCegarLoop]: 37 mSDtfsCounter, 64 mSDsluCounter, 240 mSDsCounter, 0 mSdLazyCounter, 399 mSolverCounterSat, 142 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 277 SdHoareTripleChecker+Invalid, 541 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 142 IncrementalHoareTripleChecker+Valid, 399 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.8s IncrementalHoareTripleChecker+Time [2022-03-17 21:48:27,592 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [69 Valid, 277 Invalid, 541 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [142 Valid, 399 Invalid, 0 Unknown, 0 Unchecked, 7.8s Time] [2022-03-17 21:48:27,593 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2022-03-17 21:48:27,603 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 103. [2022-03-17 21:48:27,604 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 60 states have (on average 1.15) internal successors, (69), 65 states have internal predecessors, (69), 30 states have call successors, (30), 13 states have call predecessors, (30), 12 states have return successors, (28), 24 states have call predecessors, (28), 28 states have call successors, (28) [2022-03-17 21:48:27,604 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 127 transitions. [2022-03-17 21:48:27,604 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 127 transitions. Word has length 75 [2022-03-17 21:48:27,605 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:48:27,605 INFO L478 AbstractCegarLoop]: Abstraction has 103 states and 127 transitions. [2022-03-17 21:48:27,605 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 2.0) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) [2022-03-17 21:48:27,605 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 127 transitions. [2022-03-17 21:48:27,606 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2022-03-17 21:48:27,606 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:48:27,606 INFO L500 BasicCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:48:27,629 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-03-17 21:48:27,829 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:27,829 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:48:27,830 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:48:27,830 INFO L85 PathProgramCache]: Analyzing trace with hash -102783885, now seen corresponding path program 1 times [2022-03-17 21:48:27,830 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:48:27,830 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [709588859] [2022-03-17 21:48:27,830 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:27,830 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:48:27,845 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:48:27,845 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1207971595] [2022-03-17 21:48:27,845 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:27,845 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:27,845 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:48:27,849 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-03-17 21:48:27,850 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-03-17 21:48:27,898 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:48:27,901 INFO L263 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-17 21:48:27,903 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:48:28,143 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 20 proven. 4 refuted. 0 times theorem prover too weak. 197 trivial. 0 not checked. [2022-03-17 21:48:28,143 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:48:28,398 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 20 proven. 4 refuted. 0 times theorem prover too weak. 197 trivial. 0 not checked. [2022-03-17 21:48:28,399 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:48:28,399 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [709588859] [2022-03-17 21:48:28,399 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:48:28,399 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1207971595] [2022-03-17 21:48:28,399 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1207971595] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:48:28,399 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:48:28,399 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2022-03-17 21:48:28,399 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [453986839] [2022-03-17 21:48:28,399 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:48:28,400 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-17 21:48:28,400 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:48:28,401 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-17 21:48:28,401 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2022-03-17 21:48:28,401 INFO L87 Difference]: Start difference. First operand 103 states and 127 transitions. Second operand has 9 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2022-03-17 21:48:28,544 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:48:28,545 INFO L93 Difference]: Finished difference Result 116 states and 143 transitions. [2022-03-17 21:48:28,545 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-17 21:48:28,545 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) Word has length 86 [2022-03-17 21:48:28,545 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:48:28,546 INFO L225 Difference]: With dead ends: 116 [2022-03-17 21:48:28,546 INFO L226 Difference]: Without dead ends: 114 [2022-03-17 21:48:28,547 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 162 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2022-03-17 21:48:28,547 INFO L912 BasicCegarLoop]: 44 mSDtfsCounter, 15 mSDsluCounter, 182 mSDsCounter, 0 mSdLazyCounter, 94 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 226 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 94 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 21:48:28,547 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 226 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 94 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 21:48:28,548 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2022-03-17 21:48:28,560 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 107. [2022-03-17 21:48:28,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 62 states have (on average 1.1612903225806452) internal successors, (72), 67 states have internal predecessors, (72), 32 states have call successors, (32), 13 states have call predecessors, (32), 12 states have return successors, (30), 26 states have call predecessors, (30), 30 states have call successors, (30) [2022-03-17 21:48:28,561 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 134 transitions. [2022-03-17 21:48:28,561 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 134 transitions. Word has length 86 [2022-03-17 21:48:28,562 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:48:28,562 INFO L478 AbstractCegarLoop]: Abstraction has 107 states and 134 transitions. [2022-03-17 21:48:28,562 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2022-03-17 21:48:28,562 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 134 transitions. [2022-03-17 21:48:28,563 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2022-03-17 21:48:28,563 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:48:28,563 INFO L500 BasicCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:48:28,586 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2022-03-17 21:48:28,779 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:28,779 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:48:28,780 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:48:28,780 INFO L85 PathProgramCache]: Analyzing trace with hash 1406960063, now seen corresponding path program 2 times [2022-03-17 21:48:28,780 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:48:28,780 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [876898780] [2022-03-17 21:48:28,780 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:28,780 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:48:28,788 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:48:28,788 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1883724310] [2022-03-17 21:48:28,788 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-17 21:48:28,788 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:28,788 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:48:28,797 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-03-17 21:48:28,798 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-03-17 21:48:28,840 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-17 21:48:28,841 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 21:48:28,841 INFO L263 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 21:48:28,843 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:48:28,954 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2022-03-17 21:48:28,954 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:48:29,109 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2022-03-17 21:48:29,109 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:48:29,110 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [876898780] [2022-03-17 21:48:29,110 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:48:29,110 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1883724310] [2022-03-17 21:48:29,110 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1883724310] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:48:29,110 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:48:29,110 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2022-03-17 21:48:29,110 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2143340848] [2022-03-17 21:48:29,110 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:48:29,111 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:48:29,111 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:48:29,111 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:48:29,111 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-17 21:48:29,111 INFO L87 Difference]: Start difference. First operand 107 states and 134 transitions. Second operand has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 5 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 4 states have call predecessors, (19), 4 states have call successors, (19) [2022-03-17 21:48:29,194 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:48:29,194 INFO L93 Difference]: Finished difference Result 130 states and 164 transitions. [2022-03-17 21:48:29,194 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-03-17 21:48:29,194 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 5 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 4 states have call predecessors, (19), 4 states have call successors, (19) Word has length 88 [2022-03-17 21:48:29,195 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:48:29,196 INFO L225 Difference]: With dead ends: 130 [2022-03-17 21:48:29,196 INFO L226 Difference]: Without dead ends: 111 [2022-03-17 21:48:29,196 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 171 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-17 21:48:29,197 INFO L912 BasicCegarLoop]: 56 mSDtfsCounter, 1 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 181 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 21:48:29,197 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 181 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 21:48:29,198 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2022-03-17 21:48:29,209 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 111. [2022-03-17 21:48:29,209 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 64 states have (on average 1.15625) internal successors, (74), 69 states have internal predecessors, (74), 34 states have call successors, (34), 13 states have call predecessors, (34), 12 states have return successors, (32), 28 states have call predecessors, (32), 32 states have call successors, (32) [2022-03-17 21:48:29,210 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 140 transitions. [2022-03-17 21:48:29,210 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 140 transitions. Word has length 88 [2022-03-17 21:48:29,211 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:48:29,211 INFO L478 AbstractCegarLoop]: Abstraction has 111 states and 140 transitions. [2022-03-17 21:48:29,211 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 5 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 4 states have call predecessors, (19), 4 states have call successors, (19) [2022-03-17 21:48:29,211 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 140 transitions. [2022-03-17 21:48:29,212 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-03-17 21:48:29,212 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:48:29,212 INFO L500 BasicCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:48:29,237 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-03-17 21:48:29,433 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:29,434 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:48:29,434 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:48:29,434 INFO L85 PathProgramCache]: Analyzing trace with hash 966352941, now seen corresponding path program 1 times [2022-03-17 21:48:29,434 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:48:29,434 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [256679559] [2022-03-17 21:48:29,434 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:29,435 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:48:29,442 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:48:29,442 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [165081407] [2022-03-17 21:48:29,442 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:29,442 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:29,443 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:48:29,444 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-03-17 21:48:29,461 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-03-17 21:48:29,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:48:29,489 INFO L263 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-17 21:48:29,491 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:48:29,738 INFO L134 CoverageAnalysis]: Checked inductivity of 263 backedges. 22 proven. 9 refuted. 0 times theorem prover too weak. 232 trivial. 0 not checked. [2022-03-17 21:48:29,739 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:48:30,116 INFO L134 CoverageAnalysis]: Checked inductivity of 263 backedges. 22 proven. 9 refuted. 0 times theorem prover too weak. 232 trivial. 0 not checked. [2022-03-17 21:48:30,116 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:48:30,116 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [256679559] [2022-03-17 21:48:30,117 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:48:30,117 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [165081407] [2022-03-17 21:48:30,117 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [165081407] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:48:30,117 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:48:30,117 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2022-03-17 21:48:30,117 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1926362220] [2022-03-17 21:48:30,117 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:48:30,118 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-17 21:48:30,118 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:48:30,118 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-17 21:48:30,118 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-03-17 21:48:30,118 INFO L87 Difference]: Start difference. First operand 111 states and 140 transitions. Second operand has 11 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 8 states have call successors, (29), 2 states have call predecessors, (29), 1 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2022-03-17 21:48:30,368 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:48:30,368 INFO L93 Difference]: Finished difference Result 119 states and 148 transitions. [2022-03-17 21:48:30,368 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-17 21:48:30,369 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 8 states have call successors, (29), 2 states have call predecessors, (29), 1 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 91 [2022-03-17 21:48:30,369 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:48:30,369 INFO L225 Difference]: With dead ends: 119 [2022-03-17 21:48:30,370 INFO L226 Difference]: Without dead ends: 102 [2022-03-17 21:48:30,370 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 171 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=139, Unknown=0, NotChecked=0, Total=182 [2022-03-17 21:48:30,370 INFO L912 BasicCegarLoop]: 58 mSDtfsCounter, 10 mSDsluCounter, 308 mSDsCounter, 0 mSdLazyCounter, 119 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 366 SdHoareTripleChecker+Invalid, 131 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 119 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-17 21:48:30,371 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 366 Invalid, 131 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 119 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-17 21:48:30,371 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2022-03-17 21:48:30,382 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 102. [2022-03-17 21:48:30,382 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 59 states have (on average 1.152542372881356) internal successors, (68), 64 states have internal predecessors, (68), 30 states have call successors, (30), 13 states have call predecessors, (30), 12 states have return successors, (28), 24 states have call predecessors, (28), 28 states have call successors, (28) [2022-03-17 21:48:30,383 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 126 transitions. [2022-03-17 21:48:30,383 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 126 transitions. Word has length 91 [2022-03-17 21:48:30,383 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:48:30,383 INFO L478 AbstractCegarLoop]: Abstraction has 102 states and 126 transitions. [2022-03-17 21:48:30,383 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 8 states have call successors, (29), 2 states have call predecessors, (29), 1 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2022-03-17 21:48:30,383 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 126 transitions. [2022-03-17 21:48:30,384 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2022-03-17 21:48:30,384 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:48:30,384 INFO L500 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 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, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:48:30,407 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-03-17 21:48:30,599 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-03-17 21:48:30,599 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:48:30,599 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:48:30,599 INFO L85 PathProgramCache]: Analyzing trace with hash -1871497790, now seen corresponding path program 1 times [2022-03-17 21:48:30,599 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:48:30,600 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [378814533] [2022-03-17 21:48:30,600 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:30,600 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:48:30,606 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:48:30,607 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [914748474] [2022-03-17 21:48:30,607 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:30,607 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:30,611 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:48:30,612 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-03-17 21:48:30,613 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-03-17 21:48:30,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:48:30,656 INFO L263 TraceCheckSpWp]: Trace formula consists of 212 conjuncts, 4 conjunts are in the unsatisfiable core [2022-03-17 21:48:30,658 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:48:30,814 INFO L134 CoverageAnalysis]: Checked inductivity of 315 backedges. 81 proven. 0 refuted. 0 times theorem prover too weak. 234 trivial. 0 not checked. [2022-03-17 21:48:30,814 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 21:48:30,814 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:48:30,814 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [378814533] [2022-03-17 21:48:30,814 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:48:30,814 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [914748474] [2022-03-17 21:48:30,814 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [914748474] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:48:30,814 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:48:30,815 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-17 21:48:30,815 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1815611916] [2022-03-17 21:48:30,815 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:48:30,815 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:48:30,815 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:48:30,815 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:48:30,815 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-03-17 21:48:30,816 INFO L87 Difference]: Start difference. First operand 102 states and 126 transitions. Second operand has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-03-17 21:48:30,866 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:48:30,867 INFO L93 Difference]: Finished difference Result 116 states and 141 transitions. [2022-03-17 21:48:30,867 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 21:48:30,867 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 95 [2022-03-17 21:48:30,867 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:48:30,868 INFO L225 Difference]: With dead ends: 116 [2022-03-17 21:48:30,868 INFO L226 Difference]: Without dead ends: 104 [2022-03-17 21:48:30,868 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 91 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-03-17 21:48:30,869 INFO L912 BasicCegarLoop]: 57 mSDtfsCounter, 9 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:48:30,869 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 163 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:48:30,869 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2022-03-17 21:48:30,878 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 104. [2022-03-17 21:48:30,878 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 61 states have (on average 1.1311475409836065) internal successors, (69), 64 states have internal predecessors, (69), 30 states have call successors, (30), 13 states have call predecessors, (30), 12 states have return successors, (28), 26 states have call predecessors, (28), 28 states have call successors, (28) [2022-03-17 21:48:30,879 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 127 transitions. [2022-03-17 21:48:30,879 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 127 transitions. Word has length 95 [2022-03-17 21:48:30,879 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:48:30,879 INFO L478 AbstractCegarLoop]: Abstraction has 104 states and 127 transitions. [2022-03-17 21:48:30,879 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-03-17 21:48:30,879 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 127 transitions. [2022-03-17 21:48:30,880 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2022-03-17 21:48:30,880 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:48:30,880 INFO L500 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:48:30,908 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-03-17 21:48:31,106 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:31,106 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:48:31,106 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:48:31,106 INFO L85 PathProgramCache]: Analyzing trace with hash -317970408, now seen corresponding path program 3 times [2022-03-17 21:48:31,106 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:48:31,106 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [764469664] [2022-03-17 21:48:31,106 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:48:31,107 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:48:31,114 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:48:31,114 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1764025572] [2022-03-17 21:48:31,114 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-17 21:48:31,115 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:48:31,115 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:48:31,119 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-03-17 21:48:31,120 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-03-17 21:48:31,194 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-17 21:48:31,194 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 21:48:31,196 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 40 conjunts are in the unsatisfiable core [2022-03-17 21:48:31,198 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:48:31,868 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 32 proven. 24 refuted. 0 times theorem prover too weak. 318 trivial. 0 not checked. [2022-03-17 21:48:31,868 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:49:17,164 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 26 proven. 24 refuted. 0 times theorem prover too weak. 324 trivial. 0 not checked. [2022-03-17 21:49:17,165 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:49:17,165 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [764469664] [2022-03-17 21:49:17,165 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:49:17,165 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1764025572] [2022-03-17 21:49:17,165 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1764025572] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:49:17,165 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:49:17,165 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 19 [2022-03-17 21:49:17,165 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1253038676] [2022-03-17 21:49:17,165 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:49:17,166 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-03-17 21:49:17,166 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:49:17,166 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-03-17 21:49:17,166 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=276, Unknown=2, NotChecked=0, Total=342 [2022-03-17 21:49:17,167 INFO L87 Difference]: Start difference. First operand 104 states and 127 transitions. Second operand has 19 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 17 states have internal predecessors, (44), 11 states have call successors, (33), 2 states have call predecessors, (33), 2 states have return successors, (31), 10 states have call predecessors, (31), 9 states have call successors, (31) [2022-03-17 21:50:25,494 WARN L232 SmtUtils]: Spent 1.11m on a formula simplification. DAG size of input: 196 DAG size of output: 46 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 21:50:27,498 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-03-17 21:50:29,608 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-03-17 21:50:31,664 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-03-17 21:50:34,089 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-03-17 21:50:49,088 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-03-17 21:50:53,011 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-03-17 21:50:57,966 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-03-17 21:51:00,729 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-03-17 21:51:03,578 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-03-17 21:51:04,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:51:04,724 INFO L93 Difference]: Finished difference Result 255 states and 341 transitions. [2022-03-17 21:51:04,725 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2022-03-17 21:51:04,725 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 17 states have internal predecessors, (44), 11 states have call successors, (33), 2 states have call predecessors, (33), 2 states have return successors, (31), 10 states have call predecessors, (31), 9 states have call successors, (31) Word has length 105 [2022-03-17 21:51:04,725 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:51:04,727 INFO L225 Difference]: With dead ends: 255 [2022-03-17 21:51:04,727 INFO L226 Difference]: Without dead ends: 202 [2022-03-17 21:51:04,728 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 220 GetRequests, 189 SyntacticMatches, 3 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 163 ImplicationChecksByTransitivity, 87.5s TimeCoverageRelationStatistics Valid=160, Invalid=708, Unknown=2, NotChecked=0, Total=870 [2022-03-17 21:51:04,730 INFO L912 BasicCegarLoop]: 75 mSDtfsCounter, 111 mSDsluCounter, 639 mSDsCounter, 0 mSdLazyCounter, 774 mSolverCounterSat, 216 mSolverCounterUnsat, 9 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 29.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 128 SdHoareTripleChecker+Valid, 714 SdHoareTripleChecker+Invalid, 999 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 216 IncrementalHoareTripleChecker+Valid, 774 IncrementalHoareTripleChecker+Invalid, 9 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 29.9s IncrementalHoareTripleChecker+Time [2022-03-17 21:51:04,731 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [128 Valid, 714 Invalid, 999 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [216 Valid, 774 Invalid, 9 Unknown, 0 Unchecked, 29.9s Time] [2022-03-17 21:51:04,731 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 202 states. [2022-03-17 21:51:04,750 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 202 to 163. [2022-03-17 21:51:04,751 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 163 states, 98 states have (on average 1.1428571428571428) internal successors, (112), 103 states have internal predecessors, (112), 46 states have call successors, (46), 19 states have call predecessors, (46), 18 states have return successors, (44), 40 states have call predecessors, (44), 44 states have call successors, (44) [2022-03-17 21:51:04,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 202 transitions. [2022-03-17 21:51:04,752 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 202 transitions. Word has length 105 [2022-03-17 21:51:04,752 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:51:04,752 INFO L478 AbstractCegarLoop]: Abstraction has 163 states and 202 transitions. [2022-03-17 21:51:04,752 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 17 states have internal predecessors, (44), 11 states have call successors, (33), 2 states have call predecessors, (33), 2 states have return successors, (31), 10 states have call predecessors, (31), 9 states have call successors, (31) [2022-03-17 21:51:04,752 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 202 transitions. [2022-03-17 21:51:04,753 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2022-03-17 21:51:04,753 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:51:04,754 INFO L500 BasicCegarLoop]: trace histogram [16, 15, 15, 3, 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, 1, 1, 1, 1, 1, 1] [2022-03-17 21:51:04,779 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-03-17 21:51:04,968 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-03-17 21:51:04,968 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:51:04,968 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:51:04,968 INFO L85 PathProgramCache]: Analyzing trace with hash -1498631042, now seen corresponding path program 2 times [2022-03-17 21:51:04,969 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:51:04,969 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1730777394] [2022-03-17 21:51:04,969 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:51:04,969 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:51:04,983 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:51:04,984 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1927432636] [2022-03-17 21:51:04,984 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-17 21:51:04,984 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:51:04,984 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:51:04,993 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-03-17 21:51:04,994 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-03-17 21:51:05,106 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-17 21:51:05,107 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 21:51:05,108 INFO L263 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 49 conjunts are in the unsatisfiable core [2022-03-17 21:51:05,111 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:51:09,888 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 106 proven. 30 refuted. 0 times theorem prover too weak. 354 trivial. 0 not checked. [2022-03-17 21:51:09,888 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:51:10,297 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 110 proven. 2 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2022-03-17 21:51:10,297 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:51:10,297 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1730777394] [2022-03-17 21:51:10,298 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:51:10,298 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1927432636] [2022-03-17 21:51:10,298 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1927432636] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:51:10,298 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:51:10,298 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 9] total 20 [2022-03-17 21:51:10,298 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1555013938] [2022-03-17 21:51:10,298 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:51:10,298 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-03-17 21:51:10,298 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:51:10,299 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-03-17 21:51:10,299 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=302, Unknown=0, NotChecked=0, Total=380 [2022-03-17 21:51:10,299 INFO L87 Difference]: Start difference. First operand 163 states and 202 transitions. Second operand has 20 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 10 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 8 states have call successors, (26) [2022-03-17 21:51:11,490 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:51:11,490 INFO L93 Difference]: Finished difference Result 239 states and 289 transitions. [2022-03-17 21:51:11,490 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-03-17 21:51:11,491 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 10 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 8 states have call successors, (26) Word has length 116 [2022-03-17 21:51:11,491 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:51:11,495 INFO L225 Difference]: With dead ends: 239 [2022-03-17 21:51:11,496 INFO L226 Difference]: Without dead ends: 161 [2022-03-17 21:51:11,496 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 233 GetRequests, 211 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=91, Invalid=371, Unknown=0, NotChecked=0, Total=462 [2022-03-17 21:51:11,496 INFO L912 BasicCegarLoop]: 46 mSDtfsCounter, 43 mSDsluCounter, 221 mSDsCounter, 0 mSdLazyCounter, 423 mSolverCounterSat, 97 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 267 SdHoareTripleChecker+Invalid, 520 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 97 IncrementalHoareTripleChecker+Valid, 423 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2022-03-17 21:51:11,497 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [56 Valid, 267 Invalid, 520 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [97 Valid, 423 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2022-03-17 21:51:11,497 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2022-03-17 21:51:11,513 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 143. [2022-03-17 21:51:11,513 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 143 states, 88 states have (on average 1.1136363636363635) internal successors, (98), 92 states have internal predecessors, (98), 35 states have call successors, (35), 20 states have call predecessors, (35), 19 states have return successors, (33), 30 states have call predecessors, (33), 33 states have call successors, (33) [2022-03-17 21:51:11,514 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 143 states to 143 states and 166 transitions. [2022-03-17 21:51:11,514 INFO L78 Accepts]: Start accepts. Automaton has 143 states and 166 transitions. Word has length 116 [2022-03-17 21:51:11,514 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:51:11,514 INFO L478 AbstractCegarLoop]: Abstraction has 143 states and 166 transitions. [2022-03-17 21:51:11,515 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 10 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 8 states have call successors, (26) [2022-03-17 21:51:11,515 INFO L276 IsEmpty]: Start isEmpty. Operand 143 states and 166 transitions. [2022-03-17 21:51:11,516 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2022-03-17 21:51:11,516 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:51:11,516 INFO L500 BasicCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:51:11,538 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-03-17 21:51:11,729 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-03-17 21:51:11,729 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:51:11,729 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:51:11,729 INFO L85 PathProgramCache]: Analyzing trace with hash -1262534496, now seen corresponding path program 1 times [2022-03-17 21:51:11,729 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:51:11,730 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [627058961] [2022-03-17 21:51:11,730 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:51:11,730 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:51:11,736 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:51:11,736 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [435738599] [2022-03-17 21:51:11,736 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:51:11,737 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:51:11,737 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:51:11,738 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-03-17 21:51:11,739 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-03-17 21:51:11,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 21:51:11,782 INFO L263 TraceCheckSpWp]: Trace formula consists of 270 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-17 21:51:11,784 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:51:11,999 INFO L134 CoverageAnalysis]: Checked inductivity of 563 backedges. 162 proven. 0 refuted. 0 times theorem prover too weak. 401 trivial. 0 not checked. [2022-03-17 21:51:11,999 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 21:51:12,003 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:51:12,003 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [627058961] [2022-03-17 21:51:12,003 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:51:12,003 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [435738599] [2022-03-17 21:51:12,003 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [435738599] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 21:51:12,003 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 21:51:12,003 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-17 21:51:12,003 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1784128376] [2022-03-17 21:51:12,003 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 21:51:12,004 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 21:51:12,004 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:51:12,004 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 21:51:12,004 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2022-03-17 21:51:12,004 INFO L87 Difference]: Start difference. First operand 143 states and 166 transitions. Second operand has 5 states, 5 states have (on average 5.4) internal successors, (27), 5 states have internal predecessors, (27), 4 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2022-03-17 21:51:12,060 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 21:51:12,061 INFO L93 Difference]: Finished difference Result 166 states and 192 transitions. [2022-03-17 21:51:12,061 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 21:51:12,061 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.4) internal successors, (27), 5 states have internal predecessors, (27), 4 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 122 [2022-03-17 21:51:12,061 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 21:51:12,062 INFO L225 Difference]: With dead ends: 166 [2022-03-17 21:51:12,062 INFO L226 Difference]: Without dead ends: 130 [2022-03-17 21:51:12,062 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 118 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2022-03-17 21:51:12,063 INFO L912 BasicCegarLoop]: 49 mSDtfsCounter, 2 mSDsluCounter, 119 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 168 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 21:51:12,063 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 168 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 21:51:12,063 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2022-03-17 21:51:12,079 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 130. [2022-03-17 21:51:12,079 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 80 states have (on average 1.0875) internal successors, (87), 84 states have internal predecessors, (87), 31 states have call successors, (31), 19 states have call predecessors, (31), 18 states have return successors, (29), 26 states have call predecessors, (29), 29 states have call successors, (29) [2022-03-17 21:51:12,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 147 transitions. [2022-03-17 21:51:12,083 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 147 transitions. Word has length 122 [2022-03-17 21:51:12,084 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 21:51:12,084 INFO L478 AbstractCegarLoop]: Abstraction has 130 states and 147 transitions. [2022-03-17 21:51:12,085 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.4) internal successors, (27), 5 states have internal predecessors, (27), 4 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2022-03-17 21:51:12,085 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 147 transitions. [2022-03-17 21:51:12,086 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2022-03-17 21:51:12,086 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 21:51:12,087 INFO L500 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 21:51:12,113 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-03-17 21:51:12,309 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-03-17 21:51:12,309 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 21:51:12,310 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 21:51:12,310 INFO L85 PathProgramCache]: Analyzing trace with hash -715358301, now seen corresponding path program 4 times [2022-03-17 21:51:12,310 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 21:51:12,310 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1644541583] [2022-03-17 21:51:12,310 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 21:51:12,310 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 21:51:12,317 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 21:51:12,318 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1943694445] [2022-03-17 21:51:12,318 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-17 21:51:12,318 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 21:51:12,318 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 21:51:12,320 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-03-17 21:51:12,330 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-03-17 21:51:12,384 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-17 21:51:12,384 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 21:51:12,385 INFO L263 TraceCheckSpWp]: Trace formula consists of 303 conjuncts, 56 conjunts are in the unsatisfiable core [2022-03-17 21:51:12,387 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 21:51:13,661 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 36 proven. 57 refuted. 0 times theorem prover too weak. 618 trivial. 0 not checked. [2022-03-17 21:51:13,662 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 21:51:33,412 WARN L232 SmtUtils]: Spent 7.42s on a formula simplification that was a NOOP. DAG size: 147 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 21:52:02,973 WARN L232 SmtUtils]: Spent 5.50s on a formula simplification that was a NOOP. DAG size: 150 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 21:53:19,914 WARN L232 SmtUtils]: Spent 29.18s on a formula simplification that was a NOOP. DAG size: 451 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 21:55:08,792 WARN L232 SmtUtils]: Spent 7.97s on a formula simplification that was a NOOP. DAG size: 119 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 21:55:46,441 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 36 proven. 51 refuted. 0 times theorem prover too weak. 624 trivial. 0 not checked. [2022-03-17 21:55:46,441 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 21:55:46,442 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1644541583] [2022-03-17 21:55:46,442 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 21:55:46,442 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1943694445] [2022-03-17 21:55:46,442 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1943694445] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 21:55:46,442 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 21:55:46,442 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 15] total 29 [2022-03-17 21:55:46,442 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [32777643] [2022-03-17 21:55:46,442 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 21:55:46,442 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2022-03-17 21:55:46,443 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 21:55:46,443 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2022-03-17 21:55:46,443 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=168, Invalid=644, Unknown=0, NotChecked=0, Total=812 [2022-03-17 21:55:46,444 INFO L87 Difference]: Start difference. First operand 130 states and 147 transitions. Second operand has 29 states, 29 states have (on average 1.896551724137931) internal successors, (55), 28 states have internal predecessors, (55), 18 states have call successors, (45), 2 states have call predecessors, (45), 2 states have return successors, (43), 16 states have call predecessors, (43), 16 states have call successors, (43)