/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/egcd2-ll_valuebound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7390193 [2022-04-05 07:37:19,087 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-05 07:37:19,089 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-05 07:37:19,117 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-05 07:37:19,117 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-05 07:37:19,118 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-05 07:37:19,119 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-05 07:37:19,120 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-05 07:37:19,121 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-05 07:37:19,121 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-05 07:37:19,122 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-05 07:37:19,122 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-05 07:37:19,122 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-05 07:37:19,123 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-05 07:37:19,123 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-05 07:37:19,124 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-05 07:37:19,125 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-05 07:37:19,125 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-05 07:37:19,126 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-05 07:37:19,127 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-05 07:37:19,128 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-05 07:37:19,131 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-05 07:37:19,131 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-05 07:37:19,132 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-05 07:37:19,132 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-05 07:37:19,134 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-05 07:37:19,134 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-05 07:37:19,135 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-05 07:37:19,135 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-05 07:37:19,135 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-05 07:37:19,136 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-05 07:37:19,136 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-05 07:37:19,137 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-05 07:37:19,137 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-05 07:37:19,138 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-05 07:37:19,138 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-05 07:37:19,138 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-05 07:37:19,139 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-05 07:37:19,139 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-05 07:37:19,139 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-05 07:37:19,140 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-05 07:37:19,148 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-05 07:37:19,148 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-04-05 07:37:19,166 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-05 07:37:19,166 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-05 07:37:19,166 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-05 07:37:19,167 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-05 07:37:19,167 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-05 07:37:19,167 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-05 07:37:19,167 INFO L138 SettingsManager]: * Use SBE=true [2022-04-05 07:37:19,167 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-05 07:37:19,167 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-05 07:37:19,167 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-05 07:37:19,168 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-05 07:37:19,168 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-05 07:37:19,168 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-05 07:37:19,168 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-05 07:37:19,168 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-05 07:37:19,168 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-05 07:37:19,168 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-05 07:37:19,168 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-05 07:37:19,168 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-05 07:37:19,168 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 07:37:19,168 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-05 07:37:19,168 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-05 07:37:19,169 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-05 07:37:19,169 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-05 07:37:19,169 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-05 07:37:19,169 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-05 07:37:19,169 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-04-05 07:37:19,169 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-04-05 07:37:19,169 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-05 07:37:19,169 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-04-05 07:37:19,313 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-05 07:37:19,334 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-05 07:37:19,335 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-05 07:37:19,336 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-05 07:37:19,339 INFO L275 PluginConnector]: CDTParser initialized [2022-04-05 07:37:19,340 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound100.c [2022-04-05 07:37:19,395 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f24aa4d6f/fe41a37177f2440ebc16bb25a66487eb/FLAG117dc76f8 [2022-04-05 07:37:19,759 INFO L306 CDTParser]: Found 1 translation units. [2022-04-05 07:37:19,759 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound100.c [2022-04-05 07:37:19,763 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f24aa4d6f/fe41a37177f2440ebc16bb25a66487eb/FLAG117dc76f8 [2022-04-05 07:37:19,772 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f24aa4d6f/fe41a37177f2440ebc16bb25a66487eb [2022-04-05 07:37:19,773 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-05 07:37:19,774 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-05 07:37:19,778 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-05 07:37:19,778 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-05 07:37:19,780 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-05 07:37:19,780 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 07:37:19" (1/1) ... [2022-04-05 07:37:19,781 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4335718 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 07:37:19, skipping insertion in model container [2022-04-05 07:37:19,781 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 07:37:19" (1/1) ... [2022-04-05 07:37:19,786 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-05 07:37:19,799 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-05 07:37:19,928 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/egcd2-ll_valuebound100.c[490,503] [2022-04-05 07:37:19,941 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 07:37:19,946 INFO L203 MainTranslator]: Completed pre-run [2022-04-05 07:37:19,954 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/egcd2-ll_valuebound100.c[490,503] [2022-04-05 07:37:19,960 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 07:37:19,969 INFO L208 MainTranslator]: Completed translation [2022-04-05 07:37:19,969 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 07:37:19 WrapperNode [2022-04-05 07:37:19,969 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-05 07:37:19,970 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-05 07:37:19,970 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-05 07:37:19,970 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-05 07:37:19,977 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 07:37:19" (1/1) ... [2022-04-05 07:37:19,978 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 07:37:19" (1/1) ... [2022-04-05 07:37:19,982 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 07:37:19" (1/1) ... [2022-04-05 07:37:19,982 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 07:37:19" (1/1) ... [2022-04-05 07:37:19,985 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 07:37:19" (1/1) ... [2022-04-05 07:37:19,990 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 07:37:19" (1/1) ... [2022-04-05 07:37:19,990 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 07:37:19" (1/1) ... [2022-04-05 07:37:19,991 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-05 07:37:19,992 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-05 07:37:19,992 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-05 07:37:19,992 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-05 07:37:19,993 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 07:37:19" (1/1) ... [2022-04-05 07:37:20,008 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 07:37:20,023 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:20,035 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-04-05 07:37:20,037 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-04-05 07:37:20,067 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-05 07:37:20,067 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-05 07:37:20,067 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-05 07:37:20,068 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-05 07:37:20,068 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-05 07:37:20,068 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-05 07:37:20,068 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-05 07:37:20,068 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-05 07:37:20,068 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-05 07:37:20,068 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-05 07:37:20,068 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-05 07:37:20,068 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-05 07:37:20,068 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-05 07:37:20,068 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-05 07:37:20,068 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-05 07:37:20,069 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-05 07:37:20,069 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-05 07:37:20,069 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-05 07:37:20,069 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-05 07:37:20,069 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-05 07:37:20,117 INFO L234 CfgBuilder]: Building ICFG [2022-04-05 07:37:20,119 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-05 07:37:20,233 INFO L275 CfgBuilder]: Performing block encoding [2022-04-05 07:37:20,237 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-05 07:37:20,238 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-05 07:37:20,239 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 07:37:20 BoogieIcfgContainer [2022-04-05 07:37:20,239 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-05 07:37:20,239 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-05 07:37:20,240 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-05 07:37:20,240 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-05 07:37:20,243 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 07:37:20" (1/1) ... [2022-04-05 07:37:20,245 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_QVASR [2022-04-05 07:37:20,263 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 07:37:20 BasicIcfg [2022-04-05 07:37:20,263 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-05 07:37:20,272 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-05 07:37:20,272 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-05 07:37:20,274 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-05 07:37:20,274 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.04 07:37:19" (1/4) ... [2022-04-05 07:37:20,275 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6cf2e2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 07:37:20, skipping insertion in model container [2022-04-05 07:37:20,275 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 07:37:19" (2/4) ... [2022-04-05 07:37:20,275 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6cf2e2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 07:37:20, skipping insertion in model container [2022-04-05 07:37:20,275 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 07:37:20" (3/4) ... [2022-04-05 07:37:20,275 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6cf2e2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 05.04 07:37:20, skipping insertion in model container [2022-04-05 07:37:20,275 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 07:37:20" (4/4) ... [2022-04-05 07:37:20,276 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll_valuebound100.cqvasr [2022-04-05 07:37:20,279 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-05 07:37:20,279 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-05 07:37:20,319 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-05 07:37:20,330 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-04-05 07:37:20,330 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-05 07:37:20,346 INFO L276 IsEmpty]: Start isEmpty. Operand has 40 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-05 07:37:20,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-04-05 07:37:20,350 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:20,351 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 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-04-05 07:37:20,351 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:20,357 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:20,357 INFO L85 PathProgramCache]: Analyzing trace with hash -1630657446, now seen corresponding path program 1 times [2022-04-05 07:37:20,364 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:20,365 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1557544310] [2022-04-05 07:37:20,365 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:20,365 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:20,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:20,525 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 07:37:20,530 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:20,539 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-05 07:37:20,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:20,544 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-05 07:37:20,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:20,549 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-05 07:37:20,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:20,554 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-04-05 07:37:20,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:20,565 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2022-04-05 07:37:20,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:20,573 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2022-04-05 07:37:20,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:20,581 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-05 07:37:20,582 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:20,582 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1557544310] [2022-04-05 07:37:20,582 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1557544310] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 07:37:20,582 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 07:37:20,583 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-05 07:37:20,584 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1049078094] [2022-04-05 07:37:20,584 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 07:37:20,587 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-05 07:37:20,587 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:20,614 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-05 07:37:20,614 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-05 07:37:20,616 INFO L87 Difference]: Start difference. First operand has 40 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) 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, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-05 07:37:20,686 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:20,687 INFO L93 Difference]: Finished difference Result 73 states and 118 transitions. [2022-04-05 07:37:20,688 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-05 07:37:20,689 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, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 43 [2022-04-05 07:37:20,689 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:20,693 INFO L225 Difference]: With dead ends: 73 [2022-04-05 07:37:20,693 INFO L226 Difference]: Without dead ends: 35 [2022-04-05 07:37:20,695 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 21 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-04-05 07:37:20,697 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 07:37:20,698 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 42 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 07:37:20,707 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-04-05 07:37:20,721 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2022-04-05 07:37:20,722 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-05 07:37:20,723 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 46 transitions. [2022-04-05 07:37:20,723 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 46 transitions. Word has length 43 [2022-04-05 07:37:20,724 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:20,724 INFO L478 AbstractCegarLoop]: Abstraction has 35 states and 46 transitions. [2022-04-05 07:37:20,724 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, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-05 07:37:20,724 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 46 transitions. [2022-04-05 07:37:20,725 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-04-05 07:37:20,725 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:20,725 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 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-04-05 07:37:20,726 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-05 07:37:20,726 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:20,726 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:20,726 INFO L85 PathProgramCache]: Analyzing trace with hash -1790145708, now seen corresponding path program 1 times [2022-04-05 07:37:20,726 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:20,726 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1024804179] [2022-04-05 07:37:20,727 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:20,727 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:20,742 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:20,742 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [921834276] [2022-04-05 07:37:20,742 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:20,742 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:20,742 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:20,745 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-04-05 07:37:20,746 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-04-05 07:37:20,801 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:20,803 INFO L263 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-05 07:37:20,806 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:20,953 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-05 07:37:20,953 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:37:21,090 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-05 07:37:21,091 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:21,091 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1024804179] [2022-04-05 07:37:21,091 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:37:21,091 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [921834276] [2022-04-05 07:37:21,091 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [921834276] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 07:37:21,092 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 07:37:21,092 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2022-04-05 07:37:21,092 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [122624521] [2022-04-05 07:37:21,093 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 07:37:21,093 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-05 07:37:21,093 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:21,094 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-05 07:37:21,094 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-05 07:37:21,094 INFO L87 Difference]: Start difference. First operand 35 states and 46 transitions. Second operand has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-05 07:37:21,203 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:21,203 INFO L93 Difference]: Finished difference Result 52 states and 69 transitions. [2022-04-05 07:37:21,203 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-05 07:37:21,203 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 44 [2022-04-05 07:37:21,204 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:21,204 INFO L225 Difference]: With dead ends: 52 [2022-04-05 07:37:21,204 INFO L226 Difference]: Without dead ends: 44 [2022-04-05 07:37:21,205 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 81 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-04-05 07:37:21,205 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 19 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 113 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 124 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 113 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 07:37:21,206 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 152 Invalid, 124 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 113 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 07:37:21,206 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-05 07:37:21,212 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-04-05 07:37:21,212 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 19 states have (on average 1.1578947368421053) internal successors, (22), 20 states have internal predecessors, (22), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-05 07:37:21,213 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 48 transitions. [2022-04-05 07:37:21,213 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 48 transitions. Word has length 44 [2022-04-05 07:37:21,223 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:21,224 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 48 transitions. [2022-04-05 07:37:21,224 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-05 07:37:21,224 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 48 transitions. [2022-04-05 07:37:21,225 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-04-05 07:37:21,225 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:21,225 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 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-04-05 07:37:21,243 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-04-05 07:37:21,440 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:21,440 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:21,441 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:21,441 INFO L85 PathProgramCache]: Analyzing trace with hash 375385207, now seen corresponding path program 1 times [2022-04-05 07:37:21,441 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:21,441 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [833400517] [2022-04-05 07:37:21,441 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:21,442 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:21,458 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:21,459 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1074886857] [2022-04-05 07:37:21,459 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:21,471 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:21,471 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:21,473 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-04-05 07:37:21,474 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-04-05 07:37:21,514 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:21,516 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-05 07:37:21,517 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:21,632 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-05 07:37:21,633 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:37:21,749 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-05 07:37:21,749 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:21,749 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [833400517] [2022-04-05 07:37:21,749 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:37:21,751 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1074886857] [2022-04-05 07:37:21,751 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1074886857] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-05 07:37:21,751 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-05 07:37:21,751 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-04-05 07:37:21,751 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [459954285] [2022-04-05 07:37:21,751 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 07:37:21,752 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 07:37:21,752 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:21,752 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 07:37:21,752 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2022-04-05 07:37:21,753 INFO L87 Difference]: Start difference. First operand 37 states and 48 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2022-04-05 07:37:21,791 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:21,791 INFO L93 Difference]: Finished difference Result 43 states and 53 transitions. [2022-04-05 07:37:21,791 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 07:37:21,792 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) Word has length 45 [2022-04-05 07:37:21,792 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:21,793 INFO L225 Difference]: With dead ends: 43 [2022-04-05 07:37:21,793 INFO L226 Difference]: Without dead ends: 41 [2022-04-05 07:37:21,794 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 80 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-04-05 07:37:21,796 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 137 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-04-05 07:37:21,797 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 137 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 07:37:21,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-04-05 07:37:21,811 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-04-05 07:37:21,811 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 23 states have internal predecessors, (25), 14 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-05 07:37:21,814 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 51 transitions. [2022-04-05 07:37:21,814 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 51 transitions. Word has length 45 [2022-04-05 07:37:21,814 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:21,815 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 51 transitions. [2022-04-05 07:37:21,815 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2022-04-05 07:37:21,815 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 51 transitions. [2022-04-05 07:37:21,816 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-04-05 07:37:21,816 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:21,816 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 07:37:21,834 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-04-05 07:37:22,021 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-04-05 07:37:22,021 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:22,022 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:22,022 INFO L85 PathProgramCache]: Analyzing trace with hash -788787523, now seen corresponding path program 1 times [2022-04-05 07:37:22,022 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:22,022 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1876004626] [2022-04-05 07:37:22,022 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:22,022 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:22,032 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:22,033 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1124570378] [2022-04-05 07:37:22,033 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:22,033 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:22,033 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:22,034 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-04-05 07:37:22,035 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-04-05 07:37:22,074 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:22,075 INFO L263 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-05 07:37:22,076 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:22,220 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 7 proven. 10 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-05 07:37:22,221 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:37:22,297 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:22,298 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1876004626] [2022-04-05 07:37:22,298 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:37:22,298 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1124570378] [2022-04-05 07:37:22,298 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1124570378] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 07:37:22,298 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 07:37:22,298 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-04-05 07:37:22,298 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [791389207] [2022-04-05 07:37:22,298 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 07:37:22,299 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-05 07:37:22,299 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:22,299 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-05 07:37:22,299 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2022-04-05 07:37:22,299 INFO L87 Difference]: Start difference. First operand 41 states and 51 transitions. Second operand has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-05 07:37:22,424 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:22,424 INFO L93 Difference]: Finished difference Result 54 states and 68 transitions. [2022-04-05 07:37:22,427 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-05 07:37:22,427 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 50 [2022-04-05 07:37:22,427 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:22,428 INFO L225 Difference]: With dead ends: 54 [2022-04-05 07:37:22,428 INFO L226 Difference]: Without dead ends: 52 [2022-04-05 07:37:22,428 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 44 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2022-04-05 07:37:22,429 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 26 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 225 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 168 SdHoareTripleChecker+Invalid, 233 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 225 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 07:37:22,429 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 168 Invalid, 233 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 225 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 07:37:22,429 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-05 07:37:22,434 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 51. [2022-04-05 07:37:22,434 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 28 states have internal predecessors, (31), 18 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-05 07:37:22,435 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 65 transitions. [2022-04-05 07:37:22,435 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 65 transitions. Word has length 50 [2022-04-05 07:37:22,435 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:22,435 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 65 transitions. [2022-04-05 07:37:22,435 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-05 07:37:22,435 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 65 transitions. [2022-04-05 07:37:22,436 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-04-05 07:37:22,436 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:22,436 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 07:37:22,455 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-04-05 07:37:22,644 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:22,645 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:22,645 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:22,645 INFO L85 PathProgramCache]: Analyzing trace with hash -735644649, now seen corresponding path program 1 times [2022-04-05 07:37:22,645 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:22,645 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1880387017] [2022-04-05 07:37:22,646 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:22,646 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:22,654 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:22,654 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1284543194] [2022-04-05 07:37:22,655 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:22,655 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:22,655 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:22,655 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-04-05 07:37:22,656 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-04-05 07:37:22,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:22,692 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-05 07:37:22,694 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:22,882 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 7 proven. 21 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-05 07:37:22,882 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:37:23,014 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-04-05 07:37:23,014 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:23,014 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1880387017] [2022-04-05 07:37:23,015 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:37:23,015 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1284543194] [2022-04-05 07:37:23,015 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1284543194] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-05 07:37:23,015 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-05 07:37:23,015 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-04-05 07:37:23,015 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1735190558] [2022-04-05 07:37:23,015 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 07:37:23,016 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 07:37:23,016 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:23,017 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 07:37:23,017 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-04-05 07:37:23,017 INFO L87 Difference]: Start difference. First operand 51 states and 65 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 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-04-05 07:37:23,064 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:23,065 INFO L93 Difference]: Finished difference Result 58 states and 71 transitions. [2022-04-05 07:37:23,065 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 07:37:23,065 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 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 55 [2022-04-05 07:37:23,065 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:23,067 INFO L225 Difference]: With dead ends: 58 [2022-04-05 07:37:23,067 INFO L226 Difference]: Without dead ends: 56 [2022-04-05 07:37:23,067 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 100 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-04-05 07:37:23,068 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 7 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 07:37:23,070 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 149 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 07:37:23,071 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2022-04-05 07:37:23,084 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2022-04-05 07:37:23,084 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 31 states have internal predecessors, (34), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-05 07:37:23,085 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-04-05 07:37:23,085 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 55 [2022-04-05 07:37:23,086 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:23,086 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-04-05 07:37:23,087 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 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-04-05 07:37:23,087 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-04-05 07:37:23,090 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2022-04-05 07:37:23,090 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:23,091 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 07:37:23,113 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-04-05 07:37:23,307 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:23,307 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:23,308 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:23,308 INFO L85 PathProgramCache]: Analyzing trace with hash -1700404515, now seen corresponding path program 1 times [2022-04-05 07:37:23,308 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:23,308 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1419780010] [2022-04-05 07:37:23,308 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:23,308 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:23,317 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:23,317 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [244906080] [2022-04-05 07:37:23,317 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:23,317 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:23,317 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:23,318 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-04-05 07:37:23,319 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-04-05 07:37:23,355 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:23,356 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 23 conjunts are in the unsatisfiable core [2022-04-05 07:37:23,358 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:23,506 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2022-04-05 07:37:23,506 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:37:23,582 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:23,582 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1419780010] [2022-04-05 07:37:23,583 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:37:23,583 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [244906080] [2022-04-05 07:37:23,583 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [244906080] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 07:37:23,583 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 07:37:23,583 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-04-05 07:37:23,583 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [356335265] [2022-04-05 07:37:23,583 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 07:37:23,583 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-05 07:37:23,583 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:23,584 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-05 07:37:23,584 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2022-04-05 07:37:23,584 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-04-05 07:37:23,668 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:23,668 INFO L93 Difference]: Finished difference Result 62 states and 74 transitions. [2022-04-05 07:37:23,668 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-05 07:37:23,669 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 60 [2022-04-05 07:37:23,671 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:23,672 INFO L225 Difference]: With dead ends: 62 [2022-04-05 07:37:23,673 INFO L226 Difference]: Without dead ends: 60 [2022-04-05 07:37:23,673 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 56 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2022-04-05 07:37:23,674 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 12 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 106 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 106 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 07:37:23,675 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 138 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 07:37:23,675 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2022-04-05 07:37:23,688 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2022-04-05 07:37:23,689 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 33 states have (on average 1.121212121212121) internal successors, (37), 34 states have internal predecessors, (37), 18 states have call successors, (18), 8 states have call predecessors, (18), 7 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-05 07:37:23,691 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 71 transitions. [2022-04-05 07:37:23,691 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 71 transitions. Word has length 60 [2022-04-05 07:37:23,692 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:23,693 INFO L478 AbstractCegarLoop]: Abstraction has 59 states and 71 transitions. [2022-04-05 07:37:23,693 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-04-05 07:37:23,694 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 71 transitions. [2022-04-05 07:37:23,696 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2022-04-05 07:37:23,697 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:23,697 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 07:37:23,715 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-04-05 07:37:23,903 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:23,904 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:23,904 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:23,904 INFO L85 PathProgramCache]: Analyzing trace with hash 2004479621, now seen corresponding path program 1 times [2022-04-05 07:37:23,904 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:23,904 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [481055586] [2022-04-05 07:37:23,905 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:23,905 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:23,913 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:23,913 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1740099470] [2022-04-05 07:37:23,913 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:23,913 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:23,914 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:23,914 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-04-05 07:37:23,915 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-04-05 07:37:23,952 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:23,953 INFO L263 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-05 07:37:23,954 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:24,057 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-04-05 07:37:24,057 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:37:24,163 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-04-05 07:37:24,163 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:24,163 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [481055586] [2022-04-05 07:37:24,163 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:37:24,163 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1740099470] [2022-04-05 07:37:24,163 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1740099470] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 07:37:24,163 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 07:37:24,163 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-04-05 07:37:24,164 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1939400716] [2022-04-05 07:37:24,164 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 07:37:24,165 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-05 07:37:24,165 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:24,165 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-05 07:37:24,165 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-04-05 07:37:24,165 INFO L87 Difference]: Start difference. First operand 59 states and 71 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-04-05 07:37:24,313 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:24,313 INFO L93 Difference]: Finished difference Result 106 states and 146 transitions. [2022-04-05 07:37:24,313 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-05 07:37:24,313 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) Word has length 69 [2022-04-05 07:37:24,313 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:24,314 INFO L225 Difference]: With dead ends: 106 [2022-04-05 07:37:24,314 INFO L226 Difference]: Without dead ends: 98 [2022-04-05 07:37:24,314 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 129 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2022-04-05 07:37:24,315 INFO L913 BasicCegarLoop]: 60 mSDtfsCounter, 30 mSDsluCounter, 199 mSDsCounter, 0 mSdLazyCounter, 174 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 259 SdHoareTripleChecker+Invalid, 227 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 07:37:24,315 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 259 Invalid, 227 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 174 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 07:37:24,315 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2022-04-05 07:37:24,323 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 89. [2022-04-05 07:37:24,323 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 47 states have (on average 1.1914893617021276) internal successors, (56), 48 states have internal predecessors, (56), 34 states have call successors, (34), 8 states have call predecessors, (34), 7 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2022-04-05 07:37:24,324 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 122 transitions. [2022-04-05 07:37:24,324 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 122 transitions. Word has length 69 [2022-04-05 07:37:24,324 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:24,324 INFO L478 AbstractCegarLoop]: Abstraction has 89 states and 122 transitions. [2022-04-05 07:37:24,324 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-04-05 07:37:24,325 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 122 transitions. [2022-04-05 07:37:24,325 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-04-05 07:37:24,325 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:24,325 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 07:37:24,344 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-05 07:37:24,539 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:24,540 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:24,540 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:24,540 INFO L85 PathProgramCache]: Analyzing trace with hash -966489810, now seen corresponding path program 1 times [2022-04-05 07:37:24,540 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:24,540 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [424858363] [2022-04-05 07:37:24,540 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:24,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:24,548 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:24,548 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1936584191] [2022-04-05 07:37:24,548 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:24,548 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:24,548 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:24,555 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-04-05 07:37:24,556 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-04-05 07:37:24,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:24,598 INFO L263 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 18 conjunts are in the unsatisfiable core [2022-04-05 07:37:24,599 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:24,763 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 15 proven. 12 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-04-05 07:37:24,763 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:37:24,910 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-04-05 07:37:24,910 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:24,910 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [424858363] [2022-04-05 07:37:24,910 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:37:24,910 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1936584191] [2022-04-05 07:37:24,910 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1936584191] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 07:37:24,910 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 07:37:24,910 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-04-05 07:37:24,910 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1113073145] [2022-04-05 07:37:24,911 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 07:37:24,911 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-05 07:37:24,911 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:24,911 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-05 07:37:24,911 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2022-04-05 07:37:24,911 INFO L87 Difference]: Start difference. First operand 89 states and 122 transitions. Second operand has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) [2022-04-05 07:37:25,148 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:25,148 INFO L93 Difference]: Finished difference Result 132 states and 187 transitions. [2022-04-05 07:37:25,149 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-05 07:37:25,149 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) Word has length 75 [2022-04-05 07:37:25,150 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:25,151 INFO L225 Difference]: With dead ends: 132 [2022-04-05 07:37:25,151 INFO L226 Difference]: Without dead ends: 128 [2022-04-05 07:37:25,152 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 141 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=58, Invalid=214, Unknown=0, NotChecked=0, Total=272 [2022-04-05 07:37:25,152 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 26 mSDsluCounter, 257 mSDsCounter, 0 mSdLazyCounter, 409 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 303 SdHoareTripleChecker+Invalid, 440 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 409 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-05 07:37:25,152 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 303 Invalid, 440 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 409 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-05 07:37:25,153 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2022-04-05 07:37:25,162 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 96. [2022-04-05 07:37:25,162 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 51 states have (on average 1.1764705882352942) internal successors, (60), 53 states have internal predecessors, (60), 36 states have call successors, (36), 9 states have call predecessors, (36), 8 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2022-04-05 07:37:25,163 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 130 transitions. [2022-04-05 07:37:25,163 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 130 transitions. Word has length 75 [2022-04-05 07:37:25,163 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:25,163 INFO L478 AbstractCegarLoop]: Abstraction has 96 states and 130 transitions. [2022-04-05 07:37:25,163 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) [2022-04-05 07:37:25,163 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 130 transitions. [2022-04-05 07:37:25,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2022-04-05 07:37:25,164 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:25,164 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 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, 1, 1, 1] [2022-04-05 07:37:25,183 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-04-05 07:37:25,383 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:25,384 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:25,384 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:25,384 INFO L85 PathProgramCache]: Analyzing trace with hash -271689658, now seen corresponding path program 2 times [2022-04-05 07:37:25,384 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:25,384 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1186246470] [2022-04-05 07:37:25,384 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:25,384 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:25,392 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:25,392 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1184393343] [2022-04-05 07:37:25,392 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 07:37:25,392 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:25,392 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:25,393 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-04-05 07:37:25,394 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-04-05 07:37:25,437 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 07:37:25,437 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 07:37:25,438 INFO L263 TraceCheckSpWp]: Trace formula consists of 213 conjuncts, 33 conjunts are in the unsatisfiable core [2022-04-05 07:37:25,440 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:25,838 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 15 proven. 18 refuted. 0 times theorem prover too weak. 105 trivial. 0 not checked. [2022-04-05 07:37:25,838 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:37:25,999 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2022-04-05 07:37:25,999 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:25,999 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1186246470] [2022-04-05 07:37:25,999 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:37:25,999 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1184393343] [2022-04-05 07:37:25,999 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1184393343] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 07:37:25,999 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 07:37:25,999 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 7] total 13 [2022-04-05 07:37:25,999 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [675554540] [2022-04-05 07:37:25,999 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 07:37:26,000 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-05 07:37:26,000 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:26,000 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-05 07:37:26,000 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2022-04-05 07:37:26,001 INFO L87 Difference]: Start difference. First operand 96 states and 130 transitions. Second operand has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2022-04-05 07:37:27,404 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:27,404 INFO L93 Difference]: Finished difference Result 128 states and 169 transitions. [2022-04-05 07:37:27,411 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-05 07:37:27,411 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 80 [2022-04-05 07:37:27,411 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:27,412 INFO L225 Difference]: With dead ends: 128 [2022-04-05 07:37:27,412 INFO L226 Difference]: Without dead ends: 126 [2022-04-05 07:37:27,412 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 167 GetRequests, 147 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 56 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=88, Invalid=332, Unknown=0, NotChecked=0, Total=420 [2022-04-05 07:37:27,413 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 40 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 349 mSolverCounterSat, 73 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 213 SdHoareTripleChecker+Invalid, 422 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 73 IncrementalHoareTripleChecker+Valid, 349 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2022-04-05 07:37:27,414 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [40 Valid, 213 Invalid, 422 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [73 Valid, 349 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2022-04-05 07:37:27,414 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2022-04-05 07:37:27,425 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 108. [2022-04-05 07:37:27,426 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 60 states have (on average 1.15) internal successors, (69), 62 states have internal predecessors, (69), 36 states have call successors, (36), 12 states have call predecessors, (36), 11 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2022-04-05 07:37:27,426 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 139 transitions. [2022-04-05 07:37:27,426 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 139 transitions. Word has length 80 [2022-04-05 07:37:27,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:27,428 INFO L478 AbstractCegarLoop]: Abstraction has 108 states and 139 transitions. [2022-04-05 07:37:27,428 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2022-04-05 07:37:27,428 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 139 transitions. [2022-04-05 07:37:27,428 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2022-04-05 07:37:27,429 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:27,429 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 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, 1] [2022-04-05 07:37:27,449 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-04-05 07:37:27,632 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,SelfDestructingSolverStorable8 [2022-04-05 07:37:27,633 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:27,633 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:27,633 INFO L85 PathProgramCache]: Analyzing trace with hash -1540307954, now seen corresponding path program 3 times [2022-04-05 07:37:27,633 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:27,633 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [404845369] [2022-04-05 07:37:27,633 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:27,633 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:27,640 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:27,641 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [693249843] [2022-04-05 07:37:27,641 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 07:37:27,641 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:27,641 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:27,644 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-04-05 07:37:27,644 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-04-05 07:37:27,689 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-04-05 07:37:27,689 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 07:37:27,690 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 36 conjunts are in the unsatisfiable core [2022-04-05 07:37:27,693 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:27,990 INFO L134 CoverageAnalysis]: Checked inductivity of 165 backedges. 31 proven. 8 refuted. 0 times theorem prover too weak. 126 trivial. 0 not checked. [2022-04-05 07:37:27,990 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:37:28,059 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:28,060 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [404845369] [2022-04-05 07:37:28,060 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:37:28,060 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [693249843] [2022-04-05 07:37:28,060 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [693249843] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 07:37:28,060 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 07:37:28,060 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-05 07:37:28,060 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [791597683] [2022-04-05 07:37:28,060 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 07:37:28,061 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-05 07:37:28,061 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:28,061 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-05 07:37:28,061 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-04-05 07:37:28,061 INFO L87 Difference]: Start difference. First operand 108 states and 139 transitions. Second operand has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2022-04-05 07:37:28,457 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:28,457 INFO L93 Difference]: Finished difference Result 144 states and 181 transitions. [2022-04-05 07:37:28,457 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-05 07:37:28,457 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 85 [2022-04-05 07:37:28,457 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:28,458 INFO L225 Difference]: With dead ends: 144 [2022-04-05 07:37:28,458 INFO L226 Difference]: Without dead ends: 142 [2022-04-05 07:37:28,459 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2022-04-05 07:37:28,459 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 20 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 244 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 258 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 244 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-05 07:37:28,459 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [25 Valid, 180 Invalid, 258 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 244 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-05 07:37:28,460 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2022-04-05 07:37:28,475 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 139. [2022-04-05 07:37:28,475 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 79 states have (on average 1.139240506329114) internal successors, (90), 81 states have internal predecessors, (90), 44 states have call successors, (44), 16 states have call predecessors, (44), 15 states have return successors, (42), 41 states have call predecessors, (42), 42 states have call successors, (42) [2022-04-05 07:37:28,477 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 176 transitions. [2022-04-05 07:37:28,477 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 176 transitions. Word has length 85 [2022-04-05 07:37:28,477 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:28,477 INFO L478 AbstractCegarLoop]: Abstraction has 139 states and 176 transitions. [2022-04-05 07:37:28,477 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2022-04-05 07:37:28,478 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 176 transitions. [2022-04-05 07:37:28,478 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-04-05 07:37:28,478 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:28,478 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 6, 6, 6, 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, 1, 1, 1, 1] [2022-04-05 07:37:28,497 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-04-05 07:37:28,683 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-04-05 07:37:28,684 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:28,684 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:28,684 INFO L85 PathProgramCache]: Analyzing trace with hash -757951041, now seen corresponding path program 1 times [2022-04-05 07:37:28,684 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:28,684 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1660745317] [2022-04-05 07:37:28,684 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:28,684 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:28,692 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:28,692 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1584781731] [2022-04-05 07:37:28,692 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:28,692 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:28,692 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:28,693 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-04-05 07:37:28,695 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-04-05 07:37:28,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:28,740 INFO L263 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 37 conjunts are in the unsatisfiable core [2022-04-05 07:37:28,744 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:29,097 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2022-04-05 07:37:29,097 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:37:29,418 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2022-04-05 07:37:29,418 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:29,419 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1660745317] [2022-04-05 07:37:29,419 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:37:29,419 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1584781731] [2022-04-05 07:37:29,419 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1584781731] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 07:37:29,419 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 07:37:29,419 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2022-04-05 07:37:29,419 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1494786147] [2022-04-05 07:37:29,419 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 07:37:29,420 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-05 07:37:29,420 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:29,420 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-05 07:37:29,420 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2022-04-05 07:37:29,420 INFO L87 Difference]: Start difference. First operand 139 states and 176 transitions. Second operand has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2022-04-05 07:37:31,097 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:31,097 INFO L93 Difference]: Finished difference Result 228 states and 311 transitions. [2022-04-05 07:37:31,098 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-04-05 07:37:31,098 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) Word has length 91 [2022-04-05 07:37:31,098 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:31,099 INFO L225 Difference]: With dead ends: 228 [2022-04-05 07:37:31,099 INFO L226 Difference]: Without dead ends: 220 [2022-04-05 07:37:31,100 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 168 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=178, Invalid=692, Unknown=0, NotChecked=0, Total=870 [2022-04-05 07:37:31,100 INFO L913 BasicCegarLoop]: 78 mSDtfsCounter, 53 mSDsluCounter, 240 mSDsCounter, 0 mSdLazyCounter, 557 mSolverCounterSat, 133 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 318 SdHoareTripleChecker+Invalid, 690 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 133 IncrementalHoareTripleChecker+Valid, 557 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2022-04-05 07:37:31,100 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [57 Valid, 318 Invalid, 690 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [133 Valid, 557 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2022-04-05 07:37:31,101 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states. [2022-04-05 07:37:31,129 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 216. [2022-04-05 07:37:31,130 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 116 states have (on average 1.1810344827586208) internal successors, (137), 117 states have internal predecessors, (137), 81 states have call successors, (81), 19 states have call predecessors, (81), 18 states have return successors, (79), 79 states have call predecessors, (79), 79 states have call successors, (79) [2022-04-05 07:37:31,131 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 297 transitions. [2022-04-05 07:37:31,131 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 297 transitions. Word has length 91 [2022-04-05 07:37:31,131 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:31,131 INFO L478 AbstractCegarLoop]: Abstraction has 216 states and 297 transitions. [2022-04-05 07:37:31,131 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2022-04-05 07:37:31,132 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 297 transitions. [2022-04-05 07:37:31,132 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2022-04-05 07:37:31,132 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:31,132 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 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, 1, 1, 1, 1, 1, 1] [2022-04-05 07:37:31,153 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-04-05 07:37:31,353 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,SelfDestructingSolverStorable10 [2022-04-05 07:37:31,353 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:31,354 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:31,354 INFO L85 PathProgramCache]: Analyzing trace with hash 1708635976, now seen corresponding path program 1 times [2022-04-05 07:37:31,354 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:31,354 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [245600828] [2022-04-05 07:37:31,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:31,354 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:31,361 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:31,361 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1987597918] [2022-04-05 07:37:31,361 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:31,361 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:31,361 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:31,365 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-04-05 07:37:31,366 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-04-05 07:37:31,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 07:37:31,434 INFO L263 TraceCheckSpWp]: Trace formula consists of 264 conjuncts, 42 conjunts are in the unsatisfiable core [2022-04-05 07:37:31,436 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:31,995 INFO L134 CoverageAnalysis]: Checked inductivity of 320 backedges. 51 proven. 19 refuted. 0 times theorem prover too weak. 250 trivial. 0 not checked. [2022-04-05 07:37:31,995 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:37:32,258 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-05 07:37:32,619 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:32,619 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [245600828] [2022-04-05 07:37:32,619 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:37:32,619 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1987597918] [2022-04-05 07:37:32,619 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1987597918] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 07:37:32,619 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 07:37:32,619 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-04-05 07:37:32,619 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1301629143] [2022-04-05 07:37:32,619 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 07:37:32,620 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-05 07:37:32,620 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:32,620 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-05 07:37:32,620 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=164, Unknown=0, NotChecked=0, Total=210 [2022-04-05 07:37:32,620 INFO L87 Difference]: Start difference. First operand 216 states and 297 transitions. Second operand has 11 states, 10 states have (on average 2.7) internal successors, (27), 9 states have internal predecessors, (27), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 5 states have call successors, (18) [2022-04-05 07:37:33,226 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:33,226 INFO L93 Difference]: Finished difference Result 226 states and 306 transitions. [2022-04-05 07:37:33,226 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-05 07:37:33,226 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.7) internal successors, (27), 9 states have internal predecessors, (27), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 5 states have call successors, (18) Word has length 107 [2022-04-05 07:37:33,227 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:33,228 INFO L225 Difference]: With dead ends: 226 [2022-04-05 07:37:33,228 INFO L226 Difference]: Without dead ends: 224 [2022-04-05 07:37:33,228 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 117 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=73, Invalid=269, Unknown=0, NotChecked=0, Total=342 [2022-04-05 07:37:33,228 INFO L913 BasicCegarLoop]: 48 mSDtfsCounter, 24 mSDsluCounter, 183 mSDsCounter, 0 mSdLazyCounter, 474 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 231 SdHoareTripleChecker+Invalid, 504 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 474 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-04-05 07:37:33,228 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 231 Invalid, 504 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 474 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-04-05 07:37:33,229 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 224 states. [2022-04-05 07:37:33,271 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 224 to 220. [2022-04-05 07:37:33,271 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 220 states, 119 states have (on average 1.1764705882352942) internal successors, (140), 120 states have internal predecessors, (140), 81 states have call successors, (81), 20 states have call predecessors, (81), 19 states have return successors, (79), 79 states have call predecessors, (79), 79 states have call successors, (79) [2022-04-05 07:37:33,272 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 220 states to 220 states and 300 transitions. [2022-04-05 07:37:33,273 INFO L78 Accepts]: Start accepts. Automaton has 220 states and 300 transitions. Word has length 107 [2022-04-05 07:37:33,273 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:33,273 INFO L478 AbstractCegarLoop]: Abstraction has 220 states and 300 transitions. [2022-04-05 07:37:33,273 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.7) internal successors, (27), 9 states have internal predecessors, (27), 6 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 6 states have call predecessors, (18), 5 states have call successors, (18) [2022-04-05 07:37:33,273 INFO L276 IsEmpty]: Start isEmpty. Operand 220 states and 300 transitions. [2022-04-05 07:37:33,274 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2022-04-05 07:37:33,274 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:33,274 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 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, 1, 1, 1] [2022-04-05 07:37:33,291 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-04-05 07:37:33,481 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,SelfDestructingSolverStorable11 [2022-04-05 07:37:33,481 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:33,482 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:33,482 INFO L85 PathProgramCache]: Analyzing trace with hash -426906627, now seen corresponding path program 4 times [2022-04-05 07:37:33,482 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:33,482 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1632552121] [2022-04-05 07:37:33,482 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:33,482 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:33,491 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:33,492 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1577090909] [2022-04-05 07:37:33,492 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-05 07:37:33,492 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:33,492 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:33,495 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-04-05 07:37:33,495 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-04-05 07:37:33,536 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-05 07:37:33,537 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 07:37:33,537 INFO L263 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-05 07:37:33,539 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:33,665 INFO L134 CoverageAnalysis]: Checked inductivity of 325 backedges. 135 proven. 0 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2022-04-05 07:37:33,665 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 07:37:33,665 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:33,665 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1632552121] [2022-04-05 07:37:33,666 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:37:33,666 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1577090909] [2022-04-05 07:37:33,666 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1577090909] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 07:37:33,666 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 07:37:33,666 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 07:37:33,666 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [727317205] [2022-04-05 07:37:33,666 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 07:37:33,666 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 07:37:33,666 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:33,666 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 07:37:33,667 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-05 07:37:33,667 INFO L87 Difference]: Start difference. First operand 220 states and 300 transitions. Second operand has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) [2022-04-05 07:37:33,749 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:33,749 INFO L93 Difference]: Finished difference Result 281 states and 378 transitions. [2022-04-05 07:37:33,749 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-05 07:37:33,750 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) Word has length 110 [2022-04-05 07:37:33,750 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:33,751 INFO L225 Difference]: With dead ends: 281 [2022-04-05 07:37:33,751 INFO L226 Difference]: Without dead ends: 201 [2022-04-05 07:37:33,751 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 106 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2022-04-05 07:37:33,752 INFO L913 BasicCegarLoop]: 56 mSDtfsCounter, 6 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 07:37:33,752 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 161 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 07:37:33,752 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 201 states. [2022-04-05 07:37:33,772 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 201 to 154. [2022-04-05 07:37:33,772 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 84 states have (on average 1.130952380952381) internal successors, (95), 85 states have internal predecessors, (95), 53 states have call successors, (53), 17 states have call predecessors, (53), 16 states have return successors, (51), 51 states have call predecessors, (51), 51 states have call successors, (51) [2022-04-05 07:37:33,773 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 199 transitions. [2022-04-05 07:37:33,773 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 199 transitions. Word has length 110 [2022-04-05 07:37:33,773 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:33,773 INFO L478 AbstractCegarLoop]: Abstraction has 154 states and 199 transitions. [2022-04-05 07:37:33,773 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 3 states have call predecessors, (18), 3 states have call successors, (18) [2022-04-05 07:37:33,773 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 199 transitions. [2022-04-05 07:37:33,774 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2022-04-05 07:37:33,774 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:33,774 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 3, 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-04-05 07:37:33,795 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-04-05 07:37:33,982 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,SelfDestructingSolverStorable12 [2022-04-05 07:37:33,982 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:33,982 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:33,982 INFO L85 PathProgramCache]: Analyzing trace with hash -1431100670, now seen corresponding path program 2 times [2022-04-05 07:37:33,982 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:33,982 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1514288877] [2022-04-05 07:37:33,982 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:33,983 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:33,992 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:33,992 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1424920396] [2022-04-05 07:37:33,992 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 07:37:33,992 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:33,992 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:34,000 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-04-05 07:37:34,001 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-04-05 07:37:34,069 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 07:37:34,069 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 07:37:34,071 INFO L263 TraceCheckSpWp]: Trace formula consists of 306 conjuncts, 71 conjunts are in the unsatisfiable core [2022-04-05 07:37:34,073 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:35,244 INFO L134 CoverageAnalysis]: Checked inductivity of 545 backedges. 142 proven. 88 refuted. 0 times theorem prover too weak. 315 trivial. 0 not checked. [2022-04-05 07:37:35,244 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:37:36,417 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-05 07:37:42,207 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:37:42,207 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1514288877] [2022-04-05 07:37:42,207 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:37:42,208 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1424920396] [2022-04-05 07:37:42,208 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1424920396] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 07:37:42,208 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 07:37:42,208 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2022-04-05 07:37:42,208 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1912408769] [2022-04-05 07:37:42,208 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 07:37:42,208 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-04-05 07:37:42,208 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:37:42,209 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-04-05 07:37:42,209 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=437, Unknown=1, NotChecked=0, Total=552 [2022-04-05 07:37:42,209 INFO L87 Difference]: Start difference. First operand 154 states and 199 transitions. Second operand has 16 states, 16 states have (on average 2.0) internal successors, (32), 13 states have internal predecessors, (32), 8 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (22), 7 states have call predecessors, (22), 8 states have call successors, (22) [2022-04-05 07:37:44,288 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:37:44,288 INFO L93 Difference]: Finished difference Result 194 states and 250 transitions. [2022-04-05 07:37:44,288 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-04-05 07:37:44,289 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.0) internal successors, (32), 13 states have internal predecessors, (32), 8 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (22), 7 states have call predecessors, (22), 8 states have call successors, (22) Word has length 129 [2022-04-05 07:37:44,289 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:37:44,289 INFO L225 Difference]: With dead ends: 194 [2022-04-05 07:37:44,290 INFO L226 Difference]: Without dead ends: 192 [2022-04-05 07:37:44,290 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 142 SyntacticMatches, 4 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 180 ImplicationChecksByTransitivity, 7.2s TimeCoverageRelationStatistics Valid=159, Invalid=652, Unknown=1, NotChecked=0, Total=812 [2022-04-05 07:37:44,290 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 39 mSDsluCounter, 169 mSDsCounter, 0 mSdLazyCounter, 711 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 764 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 711 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2022-04-05 07:37:44,290 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [49 Valid, 212 Invalid, 764 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 711 Invalid, 0 Unknown, 0 Unchecked, 1.6s Time] [2022-04-05 07:37:44,291 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 192 states. [2022-04-05 07:37:44,310 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 192 to 154. [2022-04-05 07:37:44,310 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 84 states have (on average 1.130952380952381) internal successors, (95), 85 states have internal predecessors, (95), 53 states have call successors, (53), 17 states have call predecessors, (53), 16 states have return successors, (51), 51 states have call predecessors, (51), 51 states have call successors, (51) [2022-04-05 07:37:44,311 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 199 transitions. [2022-04-05 07:37:44,311 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 199 transitions. Word has length 129 [2022-04-05 07:37:44,311 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:37:44,311 INFO L478 AbstractCegarLoop]: Abstraction has 154 states and 199 transitions. [2022-04-05 07:37:44,312 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.0) internal successors, (32), 13 states have internal predecessors, (32), 8 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (22), 7 states have call predecessors, (22), 8 states have call successors, (22) [2022-04-05 07:37:44,312 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 199 transitions. [2022-04-05 07:37:44,312 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 133 [2022-04-05 07:37:44,312 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:37:44,312 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 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, 1] [2022-04-05 07:37:44,333 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2022-04-05 07:37:44,527 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-04-05 07:37:44,527 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:37:44,528 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:37:44,528 INFO L85 PathProgramCache]: Analyzing trace with hash -1491357193, now seen corresponding path program 3 times [2022-04-05 07:37:44,528 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:37:44,528 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2036707991] [2022-04-05 07:37:44,528 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:37:44,528 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:37:44,535 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:37:44,535 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [900780438] [2022-04-05 07:37:44,535 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 07:37:44,535 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:37:44,535 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:37:44,536 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 07:37:44,537 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-04-05 07:37:44,591 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-04-05 07:37:44,591 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 07:37:44,593 INFO L263 TraceCheckSpWp]: Trace formula consists of 210 conjuncts, 69 conjunts are in the unsatisfiable core [2022-04-05 07:37:44,595 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:37:45,428 INFO L134 CoverageAnalysis]: Checked inductivity of 550 backedges. 100 proven. 48 refuted. 0 times theorem prover too weak. 402 trivial. 0 not checked. [2022-04-05 07:37:45,428 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:38:23,352 INFO L134 CoverageAnalysis]: Checked inductivity of 550 backedges. 100 proven. 45 refuted. 3 times theorem prover too weak. 402 trivial. 0 not checked. [2022-04-05 07:38:23,353 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:38:23,353 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2036707991] [2022-04-05 07:38:23,353 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:38:23,353 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [900780438] [2022-04-05 07:38:23,353 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [900780438] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 07:38:23,353 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 07:38:23,353 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14] total 22 [2022-04-05 07:38:23,353 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1098917008] [2022-04-05 07:38:23,353 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 07:38:23,354 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-04-05 07:38:23,354 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:38:23,355 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-04-05 07:38:23,355 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=353, Unknown=4, NotChecked=0, Total=462 [2022-04-05 07:38:23,355 INFO L87 Difference]: Start difference. First operand 154 states and 199 transitions. Second operand has 22 states, 21 states have (on average 2.380952380952381) internal successors, (50), 20 states have internal predecessors, (50), 12 states have call successors, (42), 2 states have call predecessors, (42), 2 states have return successors, (39), 13 states have call predecessors, (39), 11 states have call successors, (39) [2022-04-05 07:38:25,371 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-04-05 07:38:26,999 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.60s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:38:29,723 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-04-05 07:38:31,916 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-04-05 07:38:33,856 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.85s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:38:35,988 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-04-05 07:38:40,832 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.88s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:38:42,841 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-04-05 07:38:44,993 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-04-05 07:39:15,942 WARN L232 SmtUtils]: Spent 27.35s on a formula simplification that was a NOOP. DAG size: 130 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 07:39:18,748 WARN L833 $PredicateComparison]: unable to prove that (let ((.cse16 (* (- 1) c_main_~s~0 c_main_~y~0)) (.cse14 (* c_main_~p~0 c_main_~x~0)) (.cse15 (* c_main_~r~0 c_main_~y~0)) (.cse17 (* (- 1) c_main_~q~0 c_main_~x~0)) (.cse1 (* c_main_~q~0 c_main_~x~0)) (.cse2 (* c_main_~s~0 c_main_~y~0))) (let ((.cse0 (= (+ .cse1 .cse2 (* c_main_~b~0 c_main_~y~0)) (+ (* c_main_~q~0 c_main_~xy~0) (* c_main_~yy~0 c_main_~s~0) c_main_~b~0))) (.cse13 (+ c_main_~b~0 .cse16 .cse14 .cse15 .cse17))) (let ((.cse10 (* (- 1) c_main_~r~0)) (.cse11 (* (- 1) c_main_~p~0)) (.cse18 (not (= .cse13 c_main_~a~0))) (.cse23 (not .cse0))) (and (or .cse0 (not (= c_main_~b~0 (+ .cse1 .cse2)))) (let ((.cse12 (* (- 1) c_main_~q~0 c_main_~k~0)) (.cse9 (* c_main_~s~0 c_main_~k~0))) (let ((.cse3 (+ c_main_~r~0 (* (- 1) .cse9))) (.cse4 (+ c_main_~p~0 .cse12))) (or (not (= (+ (* .cse3 c_main_~y~0) (* .cse4 c_main_~x~0) (* c_main_~c~0 c_main_~y~0)) (+ (* c_main_~xy~0 .cse4) c_main_~c~0 (* c_main_~yy~0 .cse3)))) (let ((.cse6 (+ c_main_~q~0 .cse11 (* (- 1) .cse12))) (.cse8 (+ c_main_~s~0 .cse9 .cse10))) (let ((.cse5 (* .cse8 c_main_~y~0)) (.cse7 (* .cse6 c_main_~x~0))) (= (+ .cse5 (* .cse6 c_main_~xy~0) .cse7 (* c_main_~yy~0 .cse8)) (+ (* (+ .cse5 .cse7) c_main_~y~0) .cse5 .cse7)))) (not (= (+ (* (- 1) .cse3 c_main_~y~0) .cse1 c_main_~c~0 .cse2 (* (- 1) .cse4 c_main_~x~0)) c_main_~b~0))))) (or (not (= (+ (* .cse13 c_main_~y~0) .cse14 .cse15) (+ c_main_~b~0 (* c_main_~yy~0 c_main_~r~0) .cse16 .cse14 .cse15 .cse17 (* c_main_~xy~0 c_main_~p~0)))) .cse18 (let ((.cse21 (+ c_main_~q~0 .cse11)) (.cse22 (+ c_main_~s~0 .cse10))) (let ((.cse19 (* c_main_~y~0 .cse22)) (.cse20 (* .cse21 c_main_~x~0))) (= (+ (* (+ .cse19 .cse20) c_main_~y~0) .cse19 .cse20) (+ .cse19 (* c_main_~xy~0 .cse21) .cse20 (* c_main_~yy~0 .cse22)))))) (or .cse23 .cse18 (let ((.cse24 (+ (* (- 1) c_main_~q~0) c_main_~p~0)) (.cse27 (+ (* (- 1) c_main_~s~0) c_main_~r~0))) (let ((.cse25 (* .cse27 c_main_~y~0)) (.cse26 (* .cse24 c_main_~x~0))) (= (+ (* .cse24 c_main_~xy~0) .cse25 .cse26 (* c_main_~yy~0 .cse27)) (+ .cse25 .cse26 (* (+ .cse25 .cse26) c_main_~y~0)))))) (let ((.cse33 (+ c_main_~k~0 1))) (let ((.cse30 (+ (* (- 1) (* c_main_~s~0 .cse33)) c_main_~r~0)) (.cse29 (+ (* (- 1) c_main_~q~0 .cse33) c_main_~p~0))) (let ((.cse28 (* .cse29 c_main_~x~0)) (.cse31 (* .cse30 c_main_~y~0))) (let ((.cse32 (+ .cse28 .cse31))) (or .cse23 (= (+ .cse28 (* .cse29 c_main_~xy~0) (* c_main_~yy~0 .cse30) .cse31) (+ (* .cse32 c_main_~y~0) .cse28 .cse31)) (not (= .cse32 (+ (* (- 1) c_main_~b~0) c_main_~c~0)))))))))))) is different from false [2022-04-05 07:40:02,308 WARN L232 SmtUtils]: Spent 19.12s on a formula simplification that was a NOOP. DAG size: 108 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 07:40:04,326 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:40:30,143 WARN L232 SmtUtils]: Spent 12.42s on a formula simplification that was a NOOP. DAG size: 63 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 07:40:32,153 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:40:34,247 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-04-05 07:40:36,618 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-04-05 07:40:38,065 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.35s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:40:48,466 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-04-05 07:40:50,473 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:40:52,475 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-04-05 07:40:55,881 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-04-05 07:41:03,837 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:41:07,205 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:41:14,085 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.32s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:41:26,027 WARN L232 SmtUtils]: Spent 8.42s on a formula simplification. DAG size of input: 107 DAG size of output: 81 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 07:42:18,096 WARN L232 SmtUtils]: Spent 30.84s on a formula simplification. DAG size of input: 86 DAG size of output: 85 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 07:42:20,113 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-04-05 07:42:25,371 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.83s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:42:26,379 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.00s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:42:28,540 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-04-05 07:42:28,545 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:42:28,546 INFO L93 Difference]: Finished difference Result 259 states and 341 transitions. [2022-04-05 07:42:28,546 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2022-04-05 07:42:28,547 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 2.380952380952381) internal successors, (50), 20 states have internal predecessors, (50), 12 states have call successors, (42), 2 states have call predecessors, (42), 2 states have return successors, (39), 13 states have call predecessors, (39), 11 states have call successors, (39) Word has length 132 [2022-04-05 07:42:28,547 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:42:28,548 INFO L225 Difference]: With dead ends: 259 [2022-04-05 07:42:28,548 INFO L226 Difference]: Without dead ends: 255 [2022-04-05 07:42:28,549 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 282 GetRequests, 242 SyntacticMatches, 2 SemanticMatches, 38 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 189 ImplicationChecksByTransitivity, 202.1s TimeCoverageRelationStatistics Valid=393, Invalid=1066, Unknown=27, NotChecked=74, Total=1560 [2022-04-05 07:42:28,549 INFO L913 BasicCegarLoop]: 50 mSDtfsCounter, 87 mSDsluCounter, 263 mSDsCounter, 0 mSdLazyCounter, 839 mSolverCounterSat, 186 mSolverCounterUnsat, 19 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 61.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 99 SdHoareTripleChecker+Valid, 313 SdHoareTripleChecker+Invalid, 1045 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 186 IncrementalHoareTripleChecker+Valid, 839 IncrementalHoareTripleChecker+Invalid, 19 IncrementalHoareTripleChecker+Unknown, 1 IncrementalHoareTripleChecker+Unchecked, 61.2s IncrementalHoareTripleChecker+Time [2022-04-05 07:42:28,550 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [99 Valid, 313 Invalid, 1045 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [186 Valid, 839 Invalid, 19 Unknown, 1 Unchecked, 61.2s Time] [2022-04-05 07:42:28,550 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 255 states. [2022-04-05 07:42:28,627 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 255 to 193. [2022-04-05 07:42:28,628 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 193 states, 107 states have (on average 1.1121495327102804) internal successors, (119), 107 states have internal predecessors, (119), 65 states have call successors, (65), 22 states have call predecessors, (65), 20 states have return successors, (63), 63 states have call predecessors, (63), 63 states have call successors, (63) [2022-04-05 07:42:28,629 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 193 states to 193 states and 247 transitions. [2022-04-05 07:42:28,629 INFO L78 Accepts]: Start accepts. Automaton has 193 states and 247 transitions. Word has length 132 [2022-04-05 07:42:28,629 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:42:28,629 INFO L478 AbstractCegarLoop]: Abstraction has 193 states and 247 transitions. [2022-04-05 07:42:28,630 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 2.380952380952381) internal successors, (50), 20 states have internal predecessors, (50), 12 states have call successors, (42), 2 states have call predecessors, (42), 2 states have return successors, (39), 13 states have call predecessors, (39), 11 states have call successors, (39) [2022-04-05 07:42:28,630 INFO L276 IsEmpty]: Start isEmpty. Operand 193 states and 247 transitions. [2022-04-05 07:42:28,631 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2022-04-05 07:42:28,631 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:42:28,631 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 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-04-05 07:42:28,656 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-04-05 07:42:28,847 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:42:28,847 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:42:28,848 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:42:28,848 INFO L85 PathProgramCache]: Analyzing trace with hash -928796440, now seen corresponding path program 2 times [2022-04-05 07:42:28,848 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:42:28,848 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2140465878] [2022-04-05 07:42:28,848 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:42:28,848 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:42:28,858 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:42:28,858 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2000694558] [2022-04-05 07:42:28,858 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 07:42:28,858 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:42:28,858 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:42:28,861 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 07:42:28,862 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-04-05 07:42:28,929 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 07:42:28,929 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 07:42:28,931 INFO L263 TraceCheckSpWp]: Trace formula consists of 333 conjuncts, 67 conjunts are in the unsatisfiable core [2022-04-05 07:42:28,934 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:42:30,740 INFO L134 CoverageAnalysis]: Checked inductivity of 615 backedges. 69 proven. 90 refuted. 0 times theorem prover too weak. 456 trivial. 0 not checked. [2022-04-05 07:42:30,741 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:42:31,343 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-05 07:42:47,156 INFO L134 CoverageAnalysis]: Checked inductivity of 615 backedges. 69 proven. 90 refuted. 0 times theorem prover too weak. 456 trivial. 0 not checked. [2022-04-05 07:42:47,157 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:42:47,157 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2140465878] [2022-04-05 07:42:47,157 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:42:47,157 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2000694558] [2022-04-05 07:42:47,157 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2000694558] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 07:42:47,157 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 07:42:47,157 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 29 [2022-04-05 07:42:47,157 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2093376425] [2022-04-05 07:42:47,158 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 07:42:47,158 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2022-04-05 07:42:47,158 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:42:47,158 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2022-04-05 07:42:47,158 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=135, Invalid=675, Unknown=2, NotChecked=0, Total=812 [2022-04-05 07:42:47,159 INFO L87 Difference]: Start difference. First operand 193 states and 247 transitions. Second operand has 29 states, 27 states have (on average 1.9259259259259258) internal successors, (52), 26 states have internal predecessors, (52), 16 states have call successors, (44), 2 states have call predecessors, (44), 2 states have return successors, (41), 12 states have call predecessors, (41), 14 states have call successors, (41) [2022-04-05 07:42:54,496 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-04-05 07:43:00,459 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-04-05 07:43:07,204 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-04-05 07:43:09,206 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-04-05 07:43:14,065 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:43:16,067 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-04-05 07:43:18,070 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-04-05 07:43:20,073 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-04-05 07:43:21,784 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.71s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:43:23,786 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-04-05 07:43:25,789 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-04-05 07:43:27,791 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-04-05 07:43:29,794 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-04-05 07:43:31,799 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-04-05 07:43:33,834 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-04-05 07:43:35,846 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-04-05 07:43:50,422 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-04-05 07:43:52,577 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-04-05 07:43:54,693 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-04-05 07:43:56,717 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-04-05 07:44:07,164 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-04-05 07:44:09,168 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-04-05 07:45:40,736 WARN L232 SmtUtils]: Spent 1.35m on a formula simplification. DAG size of input: 126 DAG size of output: 124 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 07:45:47,050 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-04-05 07:45:49,053 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-04-05 07:45:51,055 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-04-05 07:45:53,059 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-04-05 07:46:12,034 WARN L232 SmtUtils]: Spent 10.37s on a formula simplification. DAG size of input: 95 DAG size of output: 93 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 07:46:14,585 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-04-05 07:46:16,587 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-04-05 07:46:19,715 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-04-05 07:46:21,719 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-04-05 07:46:23,890 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-04-05 07:47:14,647 WARN L232 SmtUtils]: Spent 42.12s on a formula simplification that was a NOOP. DAG size: 85 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 07:47:16,651 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-04-05 07:47:18,654 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-04-05 07:49:24,049 WARN L232 SmtUtils]: Spent 1.81m on a formula simplification. DAG size of input: 130 DAG size of output: 128 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 07:49:27,515 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-04-05 07:49:49,457 WARN L232 SmtUtils]: Spent 18.96s on a formula simplification. DAG size of input: 96 DAG size of output: 94 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 07:50:34,564 WARN L232 SmtUtils]: Spent 44.11s on a formula simplification that was a NOOP. DAG size: 105 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 07:50:36,572 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-04-05 07:50:45,342 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse5 (* c_main_~b~0 2)) (.cse6 (* (- 1) c_main_~c~0)) (.cse2 (+ (* c_main_~q~0 c_main_~x~0) (* c_main_~s~0 c_main_~y~0)))) (and (let ((.cse1 (* 2 c_main_~a~0))) (or (= (let ((.cse0 (div .cse1 c_main_~a~0))) (+ (* c_main_~p~0 .cse0 c_main_~x~0) (* c_main_~r~0 .cse0 c_main_~y~0))) .cse2) (not (= c_main_~b~0 .cse2)) (<= (* 3 c_main_~a~0) c_main_~b~0) (not (= c_main_~b~0 .cse1)))) (let ((.cse4 (+ .cse5 .cse6 c_main_~a~0))) (let ((.cse3 (div .cse4 c_main_~b~0))) (or (not (= (+ c_main_~c~0 (* (- 2) c_main_~b~0)) 0)) (= (+ (* (+ (* (- 1) (* .cse3 c_main_~s~0)) c_main_~r~0) c_main_~y~0) (* (+ (* (- 1) .cse3 c_main_~q~0) c_main_~p~0) c_main_~x~0)) 0) (< .cse3 (+ 2 c_main_~k~0)) (not (= (mod .cse4 c_main_~b~0) 0)) (<= (* c_main_~b~0 3) c_main_~c~0)))) (or (not (= c_main_~c~0 0)) (= (+ (* (+ c_main_~r~0 (* (- 1) (* c_main_~s~0 c_main_~k~0))) c_main_~y~0) (* (+ c_main_~p~0 (* (- 1) c_main_~q~0 c_main_~k~0)) c_main_~x~0)) 0)) (let ((.cse7 (+ c_main_~b~0 .cse6 c_main_~a~0))) (let ((.cse8 (div .cse7 c_main_~b~0))) (or (not (= (+ (* (- 1) c_main_~b~0) c_main_~c~0) 0)) (not (= (mod .cse7 c_main_~b~0) 0)) (not (<= (+ c_main_~k~0 1) .cse8)) (<= .cse5 c_main_~c~0) (= (+ (* (+ (* (- 1) (* .cse8 c_main_~s~0)) c_main_~r~0) c_main_~y~0) (* (+ c_main_~p~0 (* (- 1) .cse8 c_main_~q~0)) c_main_~x~0)) 0)))) (or (= .cse2 0) (not (= c_main_~b~0 0))))) is different from true [2022-04-05 07:50:47,506 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-04-05 07:50:54,019 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-04-05 07:51:00,459 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-04-05 07:51:02,812 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-04-05 07:51:04,814 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-04-05 07:51:52,480 WARN L232 SmtUtils]: Spent 43.57s on a formula simplification that was a NOOP. DAG size: 117 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 07:51:52,521 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:51:52,521 INFO L93 Difference]: Finished difference Result 270 states and 358 transitions. [2022-04-05 07:51:52,522 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2022-04-05 07:51:52,522 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 27 states have (on average 1.9259259259259258) internal successors, (52), 26 states have internal predecessors, (52), 16 states have call successors, (44), 2 states have call predecessors, (44), 2 states have return successors, (41), 12 states have call predecessors, (41), 14 states have call successors, (41) Word has length 138 [2022-04-05 07:51:52,522 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:51:52,523 INFO L225 Difference]: With dead ends: 270 [2022-04-05 07:51:52,523 INFO L226 Difference]: Without dead ends: 264 [2022-04-05 07:51:52,524 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 309 GetRequests, 246 SyntacticMatches, 2 SemanticMatches, 61 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 941 ImplicationChecksByTransitivity, 461.1s TimeCoverageRelationStatistics Valid=756, Invalid=2989, Unknown=41, NotChecked=120, Total=3906 [2022-04-05 07:51:52,525 INFO L913 BasicCegarLoop]: 57 mSDtfsCounter, 141 mSDsluCounter, 341 mSDsCounter, 0 mSdLazyCounter, 1226 mSolverCounterSat, 343 mSolverCounterUnsat, 39 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 95.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 146 SdHoareTripleChecker+Valid, 398 SdHoareTripleChecker+Invalid, 1609 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 343 IncrementalHoareTripleChecker+Valid, 1226 IncrementalHoareTripleChecker+Invalid, 39 IncrementalHoareTripleChecker+Unknown, 1 IncrementalHoareTripleChecker+Unchecked, 96.1s IncrementalHoareTripleChecker+Time [2022-04-05 07:51:52,525 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [146 Valid, 398 Invalid, 1609 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [343 Valid, 1226 Invalid, 39 Unknown, 1 Unchecked, 96.1s Time] [2022-04-05 07:51:52,525 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 264 states. [2022-04-05 07:51:52,605 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 264 to 229. [2022-04-05 07:51:52,606 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 229 states, 126 states have (on average 1.1111111111111112) internal successors, (140), 127 states have internal predecessors, (140), 80 states have call successors, (80), 24 states have call predecessors, (80), 22 states have return successors, (78), 77 states have call predecessors, (78), 78 states have call successors, (78) [2022-04-05 07:51:52,607 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 229 states to 229 states and 298 transitions. [2022-04-05 07:51:52,607 INFO L78 Accepts]: Start accepts. Automaton has 229 states and 298 transitions. Word has length 138 [2022-04-05 07:51:52,607 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:51:52,607 INFO L478 AbstractCegarLoop]: Abstraction has 229 states and 298 transitions. [2022-04-05 07:51:52,607 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 27 states have (on average 1.9259259259259258) internal successors, (52), 26 states have internal predecessors, (52), 16 states have call successors, (44), 2 states have call predecessors, (44), 2 states have return successors, (41), 12 states have call predecessors, (41), 14 states have call successors, (41) [2022-04-05 07:51:52,607 INFO L276 IsEmpty]: Start isEmpty. Operand 229 states and 298 transitions. [2022-04-05 07:51:52,608 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 183 [2022-04-05 07:51:52,608 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:51:52,608 INFO L499 BasicCegarLoop]: trace histogram [25, 24, 24, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 4, 3, 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-04-05 07:51:52,624 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-04-05 07:51:52,816 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-04-05 07:51:52,817 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:51:52,817 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:51:52,817 INFO L85 PathProgramCache]: Analyzing trace with hash 980979816, now seen corresponding path program 3 times [2022-04-05 07:51:52,817 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:51:52,817 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2119924052] [2022-04-05 07:51:52,817 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:51:52,817 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:51:52,824 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:51:52,824 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1513725764] [2022-04-05 07:51:52,824 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 07:51:52,824 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:51:52,825 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:51:52,825 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 07:51:52,826 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-04-05 07:51:53,165 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-04-05 07:51:53,166 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 07:51:53,167 INFO L263 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 57 conjunts are in the unsatisfiable core [2022-04-05 07:51:53,170 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:51:54,297 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-05 07:51:56,627 INFO L134 CoverageAnalysis]: Checked inductivity of 1309 backedges. 113 proven. 83 refuted. 0 times theorem prover too weak. 1113 trivial. 0 not checked. [2022-04-05 07:51:56,627 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 07:51:59,521 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful