/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/automizer/LoopAccelerationJordanC.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_unwindbound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.1-dev-6253b08 [2021-05-06 08:15:46,088 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-05-06 08:15:46,089 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-05-06 08:15:46,119 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-05-06 08:15:46,119 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-05-06 08:15:46,121 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-05-06 08:15:46,125 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-05-06 08:15:46,129 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-05-06 08:15:46,130 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-05-06 08:15:46,133 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-05-06 08:15:46,134 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-05-06 08:15:46,135 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-05-06 08:15:46,135 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-05-06 08:15:46,136 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-05-06 08:15:46,138 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-05-06 08:15:46,139 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-05-06 08:15:46,140 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-05-06 08:15:46,141 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-05-06 08:15:46,143 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-05-06 08:15:46,147 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-05-06 08:15:46,150 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-05-06 08:15:46,151 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-05-06 08:15:46,152 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-05-06 08:15:46,153 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-05-06 08:15:46,156 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-05-06 08:15:46,156 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-05-06 08:15:46,156 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-05-06 08:15:46,157 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-05-06 08:15:46,157 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-05-06 08:15:46,158 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-05-06 08:15:46,158 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-05-06 08:15:46,158 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-05-06 08:15:46,159 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-05-06 08:15:46,159 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-05-06 08:15:46,160 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-05-06 08:15:46,160 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-05-06 08:15:46,160 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-05-06 08:15:46,160 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-05-06 08:15:46,161 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-05-06 08:15:46,161 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-05-06 08:15:46,162 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-05-06 08:15:46,165 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2021-05-06 08:15:46,179 INFO L113 SettingsManager]: Loading preferences was successful [2021-05-06 08:15:46,179 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-05-06 08:15:46,181 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-05-06 08:15:46,181 INFO L138 SettingsManager]: * sizeof long=4 [2021-05-06 08:15:46,181 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-05-06 08:15:46,182 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-05-06 08:15:46,182 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-05-06 08:15:46,182 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-05-06 08:15:46,182 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-05-06 08:15:46,182 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-05-06 08:15:46,183 INFO L138 SettingsManager]: * sizeof long double=12 [2021-05-06 08:15:46,183 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-05-06 08:15:46,183 INFO L138 SettingsManager]: * Use constant arrays=true [2021-05-06 08:15:46,183 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-05-06 08:15:46,184 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-05-06 08:15:46,184 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-05-06 08:15:46,184 INFO L138 SettingsManager]: * To the following directory=./dump/ [2021-05-06 08:15:46,184 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-05-06 08:15:46,184 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-05-06 08:15:46,184 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-05-06 08:15:46,184 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-05-06 08:15:46,185 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2021-05-06 08:15:46,185 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_JORDAN 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; [2021-05-06 08:15:46,415 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-05-06 08:15:46,436 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-05-06 08:15:46,438 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-05-06 08:15:46,438 INFO L271 PluginConnector]: Initializing CDTParser... [2021-05-06 08:15:46,439 INFO L275 PluginConnector]: CDTParser initialized [2021-05-06 08:15:46,439 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2021-05-06 08:15:46,490 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/dca26733d/ba2076896442464ca61352ba19270b69/FLAG887a1ba91 [2021-05-06 08:15:46,855 INFO L306 CDTParser]: Found 1 translation units. [2021-05-06 08:15:46,855 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2021-05-06 08:15:46,861 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/dca26733d/ba2076896442464ca61352ba19270b69/FLAG887a1ba91 [2021-05-06 08:15:47,249 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/dca26733d/ba2076896442464ca61352ba19270b69 [2021-05-06 08:15:47,251 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-05-06 08:15:47,253 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2021-05-06 08:15:47,255 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-05-06 08:15:47,255 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-05-06 08:15:47,257 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-05-06 08:15:47,258 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.05 08:15:47" (1/1) ... [2021-05-06 08:15:47,259 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@59b6b81f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.05 08:15:47, skipping insertion in model container [2021-05-06 08:15:47,259 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.05 08:15:47" (1/1) ... [2021-05-06 08:15:47,264 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-05-06 08:15:47,276 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-05-06 08:15:47,364 WARN L224 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_unwindbound5.c[490,503] [2021-05-06 08:15:47,375 INFO L206 PostProcessor]: Analyzing one entry point: main [2021-05-06 08:15:47,380 INFO L203 MainTranslator]: Completed pre-run [2021-05-06 08:15:47,406 WARN L224 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_unwindbound5.c[490,503] [2021-05-06 08:15:47,423 INFO L206 PostProcessor]: Analyzing one entry point: main [2021-05-06 08:15:47,459 INFO L208 MainTranslator]: Completed translation [2021-05-06 08:15:47,459 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.05 08:15:47 WrapperNode [2021-05-06 08:15:47,460 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-05-06 08:15:47,460 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-05-06 08:15:47,460 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-05-06 08:15:47,460 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-05-06 08:15:47,468 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.05 08:15:47" (1/1) ... [2021-05-06 08:15:47,468 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.05 08:15:47" (1/1) ... [2021-05-06 08:15:47,480 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.05 08:15:47" (1/1) ... [2021-05-06 08:15:47,481 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.05 08:15:47" (1/1) ... [2021-05-06 08:15:47,488 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.05 08:15:47" (1/1) ... [2021-05-06 08:15:47,491 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.05 08:15:47" (1/1) ... [2021-05-06 08:15:47,492 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.05 08:15:47" (1/1) ... [2021-05-06 08:15:47,493 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-05-06 08:15:47,494 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-05-06 08:15:47,494 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-05-06 08:15:47,494 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-05-06 08:15:47,494 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.05 08:15:47" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-05-06 08:15:47,559 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2021-05-06 08:15:47,559 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-05-06 08:15:47,559 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2021-05-06 08:15:47,559 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2021-05-06 08:15:47,559 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-05-06 08:15:47,559 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2021-05-06 08:15:47,560 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2021-05-06 08:15:47,560 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2021-05-06 08:15:47,560 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2021-05-06 08:15:47,560 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-05-06 08:15:47,560 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2021-05-06 08:15:47,561 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2021-05-06 08:15:47,561 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-05-06 08:15:47,561 INFO L130 BoogieDeclarations]: Found specification of procedure main [2021-05-06 08:15:47,561 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2021-05-06 08:15:47,561 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-05-06 08:15:47,561 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-05-06 08:15:47,561 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2021-05-06 08:15:47,562 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2021-05-06 08:15:47,562 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-05-06 08:15:47,868 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-05-06 08:15:47,869 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2021-05-06 08:15:47,870 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.05 08:15:47 BoogieIcfgContainer [2021-05-06 08:15:47,870 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-05-06 08:15:47,870 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2021-05-06 08:15:47,870 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2021-05-06 08:15:47,871 INFO L275 PluginConnector]: IcfgTransformer initialized [2021-05-06 08:15:47,876 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.05 08:15:47" (1/1) ... [2021-05-06 08:15:47,891 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.05 08:15:47 BasicIcfg [2021-05-06 08:15:47,891 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2021-05-06 08:15:47,892 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-05-06 08:15:47,893 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-05-06 08:15:47,895 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-05-06 08:15:47,895 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.05 08:15:47" (1/4) ... [2021-05-06 08:15:47,895 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@125faf40 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.05 08:15:47, skipping insertion in model container [2021-05-06 08:15:47,896 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.05 08:15:47" (2/4) ... [2021-05-06 08:15:47,896 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@125faf40 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.05 08:15:47, skipping insertion in model container [2021-05-06 08:15:47,896 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.05 08:15:47" (3/4) ... [2021-05-06 08:15:47,898 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@125faf40 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.05 08:15:47, skipping insertion in model container [2021-05-06 08:15:47,898 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.05 08:15:47" (4/4) ... [2021-05-06 08:15:47,899 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound5.cJordan [2021-05-06 08:15:47,903 INFO L149 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2021-05-06 08:15:47,906 INFO L161 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2021-05-06 08:15:47,917 INFO L253 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-05-06 08:15:47,938 INFO L376 AbstractCegarLoop]: Interprodecural is true [2021-05-06 08:15:47,938 INFO L377 AbstractCegarLoop]: Hoare is false [2021-05-06 08:15:47,938 INFO L378 AbstractCegarLoop]: Compute interpolants for ForwardPredicates [2021-05-06 08:15:47,938 INFO L379 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2021-05-06 08:15:47,938 INFO L380 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2021-05-06 08:15:47,938 INFO L381 AbstractCegarLoop]: Difference is false [2021-05-06 08:15:47,938 INFO L382 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2021-05-06 08:15:47,938 INFO L386 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2021-05-06 08:15:47,949 INFO L276 IsEmpty]: Start isEmpty. Operand has 39 states, 21 states have (on average 1.4285714285714286) internal successors, (30), 23 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2021-05-06 08:15:47,959 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2021-05-06 08:15:47,960 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:47,960 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:47,961 INFO L428 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:47,965 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:47,966 INFO L82 PathProgramCache]: Analyzing trace with hash -282167495, now seen corresponding path program 1 times [2021-05-06 08:15:47,972 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:47,972 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [863626010] [2021-05-06 08:15:47,972 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:48,056 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:48,057 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1794877565] [2021-05-06 08:15:48,057 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:48,167 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:48,172 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 1 conjunts are in the unsatisfiable core [2021-05-06 08:15:48,178 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:48,263 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-05-06 08:15:48,263 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:48,264 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [863626010] [2021-05-06 08:15:48,264 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:48,264 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1794877565] [2021-05-06 08:15:48,264 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1794877565] provided 1 perfect and 0 imperfect interpolant sequences [2021-05-06 08:15:48,264 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-05-06 08:15:48,264 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-05-06 08:15:48,265 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [564312655] [2021-05-06 08:15:48,268 INFO L460 AbstractCegarLoop]: Interpolant automaton has 2 states [2021-05-06 08:15:48,268 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:48,275 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2021-05-06 08:15:48,276 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-05-06 08:15:48,277 INFO L87 Difference]: Start difference. First operand has 39 states, 21 states have (on average 1.4285714285714286) internal successors, (30), 23 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2021-05-06 08:15:48,287 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:48,287 INFO L93 Difference]: Finished difference Result 39 states and 50 transitions. [2021-05-06 08:15:48,287 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-05-06 08:15:48,288 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 32 [2021-05-06 08:15:48,288 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:48,292 INFO L225 Difference]: With dead ends: 39 [2021-05-06 08:15:48,292 INFO L226 Difference]: Without dead ends: 34 [2021-05-06 08:15:48,293 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0ms TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-05-06 08:15:48,319 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2021-05-06 08:15:48,330 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2021-05-06 08:15:48,330 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 18 states have (on average 1.2777777777777777) internal successors, (23), 20 states have internal predecessors, (23), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2021-05-06 08:15:48,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 45 transitions. [2021-05-06 08:15:48,332 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 45 transitions. Word has length 32 [2021-05-06 08:15:48,333 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:48,333 INFO L480 AbstractCegarLoop]: Abstraction has 34 states and 45 transitions. [2021-05-06 08:15:48,333 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2021-05-06 08:15:48,333 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 45 transitions. [2021-05-06 08:15:48,334 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2021-05-06 08:15:48,334 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:48,334 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:48,535 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2021-05-06 08:15:48,536 INFO L428 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:48,536 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:48,536 INFO L82 PathProgramCache]: Analyzing trace with hash -127828113, now seen corresponding path program 1 times [2021-05-06 08:15:48,536 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:48,537 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1687221337] [2021-05-06 08:15:48,537 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:48,553 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:48,553 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1307606831] [2021-05-06 08:15:48,553 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:48,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:48,630 INFO L263 TraceCheckSpWp]: Trace formula consists of 159 conjuncts, 5 conjunts are in the unsatisfiable core [2021-05-06 08:15:48,632 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:48,657 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:48,661 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:48,662 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:48,707 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:48,719 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:48,743 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-05-06 08:15:48,744 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:48,744 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1687221337] [2021-05-06 08:15:48,744 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:48,744 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1307606831] [2021-05-06 08:15:48,744 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1307606831] provided 1 perfect and 0 imperfect interpolant sequences [2021-05-06 08:15:48,744 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-05-06 08:15:48,744 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-05-06 08:15:48,744 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [457898576] [2021-05-06 08:15:48,745 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2021-05-06 08:15:48,745 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:48,746 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-05-06 08:15:48,746 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-05-06 08:15:48,746 INFO L87 Difference]: Start difference. First operand 34 states and 45 transitions. Second operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) [2021-05-06 08:15:48,765 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:48,766 INFO L93 Difference]: Finished difference Result 36 states and 47 transitions. [2021-05-06 08:15:48,766 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-05-06 08:15:48,769 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2021-05-06 08:15:48,769 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:48,771 INFO L225 Difference]: With dead ends: 36 [2021-05-06 08:15:48,771 INFO L226 Difference]: Without dead ends: 36 [2021-05-06 08:15:48,771 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 9.0ms TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-05-06 08:15:48,772 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2021-05-06 08:15:48,777 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2021-05-06 08:15:48,778 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 20 states have (on average 1.25) internal successors, (25), 21 states have internal predecessors, (25), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2021-05-06 08:15:48,778 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 47 transitions. [2021-05-06 08:15:48,779 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 47 transitions. Word has length 33 [2021-05-06 08:15:48,779 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:48,779 INFO L480 AbstractCegarLoop]: Abstraction has 36 states and 47 transitions. [2021-05-06 08:15:48,779 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) [2021-05-06 08:15:48,779 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 47 transitions. [2021-05-06 08:15:48,780 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2021-05-06 08:15:48,780 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:48,780 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:48,989 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,3 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:48,989 INFO L428 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:48,989 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:48,990 INFO L82 PathProgramCache]: Analyzing trace with hash 365419517, now seen corresponding path program 1 times [2021-05-06 08:15:48,990 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:48,990 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [507455546] [2021-05-06 08:15:48,990 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:49,001 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:49,001 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1655267357] [2021-05-06 08:15:49,001 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:49,053 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:49,054 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 7 conjunts are in the unsatisfiable core [2021-05-06 08:15:49,055 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:49,149 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:49,158 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:49,159 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:49,171 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:49,172 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:49,186 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-05-06 08:15:49,186 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:49,186 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [507455546] [2021-05-06 08:15:49,186 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:49,186 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1655267357] [2021-05-06 08:15:49,187 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1655267357] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:49,187 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:49,187 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2021-05-06 08:15:49,187 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1810112785] [2021-05-06 08:15:49,187 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2021-05-06 08:15:49,187 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:49,188 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-05-06 08:15:49,188 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2021-05-06 08:15:49,188 INFO L87 Difference]: Start difference. First operand 36 states and 47 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2021-05-06 08:15:49,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:49,259 INFO L93 Difference]: Finished difference Result 45 states and 62 transitions. [2021-05-06 08:15:49,259 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-05-06 08:15:49,259 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2021-05-06 08:15:49,260 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:49,260 INFO L225 Difference]: With dead ends: 45 [2021-05-06 08:15:49,260 INFO L226 Difference]: Without dead ends: 45 [2021-05-06 08:15:49,260 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 28.4ms TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2021-05-06 08:15:49,261 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2021-05-06 08:15:49,266 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 37. [2021-05-06 08:15:49,266 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 22 states have internal predecessors, (26), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2021-05-06 08:15:49,268 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 48 transitions. [2021-05-06 08:15:49,268 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 48 transitions. Word has length 34 [2021-05-06 08:15:49,268 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:49,268 INFO L480 AbstractCegarLoop]: Abstraction has 37 states and 48 transitions. [2021-05-06 08:15:49,268 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2021-05-06 08:15:49,268 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 48 transitions. [2021-05-06 08:15:49,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2021-05-06 08:15:49,270 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:49,270 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:49,473 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:49,473 INFO L428 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:49,474 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:49,474 INFO L82 PathProgramCache]: Analyzing trace with hash 196514290, now seen corresponding path program 1 times [2021-05-06 08:15:49,474 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:49,474 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [351921686] [2021-05-06 08:15:49,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:49,490 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:49,490 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1313065534] [2021-05-06 08:15:49,491 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:49,550 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:49,551 INFO L263 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 14 conjunts are in the unsatisfiable core [2021-05-06 08:15:49,552 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:49,596 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:49,607 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:49,609 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:49,621 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:49,624 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:49,658 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:49,659 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:49,668 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:49,677 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-05-06 08:15:49,677 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:49,677 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [351921686] [2021-05-06 08:15:49,678 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:49,678 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1313065534] [2021-05-06 08:15:49,678 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1313065534] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:49,678 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:49,678 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2021-05-06 08:15:49,678 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1918955874] [2021-05-06 08:15:49,678 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2021-05-06 08:15:49,678 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:49,679 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-05-06 08:15:49,679 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2021-05-06 08:15:49,679 INFO L87 Difference]: Start difference. First operand 37 states and 48 transitions. Second operand has 9 states, 9 states have (on average 2.0) internal successors, (18), 7 states have internal predecessors, (18), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2021-05-06 08:15:49,812 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:49,812 INFO L93 Difference]: Finished difference Result 57 states and 79 transitions. [2021-05-06 08:15:49,812 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-05-06 08:15:49,813 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.0) internal successors, (18), 7 states have internal predecessors, (18), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2021-05-06 08:15:49,813 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:49,814 INFO L225 Difference]: With dead ends: 57 [2021-05-06 08:15:49,814 INFO L226 Difference]: Without dead ends: 57 [2021-05-06 08:15:49,814 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 56.0ms TimeCoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2021-05-06 08:15:49,814 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2021-05-06 08:15:49,817 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 44. [2021-05-06 08:15:49,818 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 26 states have (on average 1.2307692307692308) internal successors, (32), 28 states have internal predecessors, (32), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2021-05-06 08:15:49,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 56 transitions. [2021-05-06 08:15:49,818 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 56 transitions. Word has length 36 [2021-05-06 08:15:49,819 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:49,819 INFO L480 AbstractCegarLoop]: Abstraction has 44 states and 56 transitions. [2021-05-06 08:15:49,819 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 9 states, 9 states have (on average 2.0) internal successors, (18), 7 states have internal predecessors, (18), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2021-05-06 08:15:49,819 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 56 transitions. [2021-05-06 08:15:49,819 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2021-05-06 08:15:49,819 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:49,819 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:50,024 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:50,025 INFO L428 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:50,026 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:50,026 INFO L82 PathProgramCache]: Analyzing trace with hash 56558454, now seen corresponding path program 1 times [2021-05-06 08:15:50,026 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:50,026 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1810445101] [2021-05-06 08:15:50,026 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:50,037 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:50,037 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1301728250] [2021-05-06 08:15:50,037 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:50,094 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:50,095 INFO L263 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 7 conjunts are in the unsatisfiable core [2021-05-06 08:15:50,097 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:50,120 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,123 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,129 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,166 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,171 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,174 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,185 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,187 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,203 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-05-06 08:15:50,203 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:50,203 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1810445101] [2021-05-06 08:15:50,203 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:50,203 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1301728250] [2021-05-06 08:15:50,203 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1301728250] provided 1 perfect and 0 imperfect interpolant sequences [2021-05-06 08:15:50,203 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-05-06 08:15:50,203 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-05-06 08:15:50,203 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1344763868] [2021-05-06 08:15:50,204 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2021-05-06 08:15:50,204 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:50,204 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-05-06 08:15:50,204 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2021-05-06 08:15:50,204 INFO L87 Difference]: Start difference. First operand 44 states and 56 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) [2021-05-06 08:15:50,234 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:50,235 INFO L93 Difference]: Finished difference Result 44 states and 55 transitions. [2021-05-06 08:15:50,235 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-05-06 08:15:50,235 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) Word has length 39 [2021-05-06 08:15:50,237 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:50,239 INFO L225 Difference]: With dead ends: 44 [2021-05-06 08:15:50,239 INFO L226 Difference]: Without dead ends: 44 [2021-05-06 08:15:50,239 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 9.9ms TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2021-05-06 08:15:50,239 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2021-05-06 08:15:50,241 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 44. [2021-05-06 08:15:50,242 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 26 states have (on average 1.1923076923076923) internal successors, (31), 28 states have internal predecessors, (31), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2021-05-06 08:15:50,242 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 55 transitions. [2021-05-06 08:15:50,242 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 55 transitions. Word has length 39 [2021-05-06 08:15:50,242 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:50,242 INFO L480 AbstractCegarLoop]: Abstraction has 44 states and 55 transitions. [2021-05-06 08:15:50,242 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) [2021-05-06 08:15:50,242 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 55 transitions. [2021-05-06 08:15:50,243 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-05-06 08:15:50,243 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:50,243 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:50,448 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:50,449 INFO L428 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:50,449 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:50,449 INFO L82 PathProgramCache]: Analyzing trace with hash 578094295, now seen corresponding path program 1 times [2021-05-06 08:15:50,449 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:50,449 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1083576415] [2021-05-06 08:15:50,449 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:50,458 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:50,458 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [325155056] [2021-05-06 08:15:50,458 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:50,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:50,512 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 14 conjunts are in the unsatisfiable core [2021-05-06 08:15:50,514 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:50,545 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,546 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,566 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,567 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,579 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,580 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,602 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,604 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,613 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,615 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,628 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:50,641 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-05-06 08:15:50,642 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:50,642 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1083576415] [2021-05-06 08:15:50,642 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:50,642 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [325155056] [2021-05-06 08:15:50,642 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [325155056] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:50,642 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:50,642 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2021-05-06 08:15:50,642 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1552162611] [2021-05-06 08:15:50,642 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2021-05-06 08:15:50,642 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:50,643 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-05-06 08:15:50,643 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2021-05-06 08:15:50,643 INFO L87 Difference]: Start difference. First operand 44 states and 55 transitions. Second operand has 8 states, 8 states have (on average 2.625) internal successors, (21), 6 states have internal predecessors, (21), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2021-05-06 08:15:50,728 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:50,728 INFO L93 Difference]: Finished difference Result 56 states and 72 transitions. [2021-05-06 08:15:50,728 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-05-06 08:15:50,728 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 6 states have internal predecessors, (21), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 41 [2021-05-06 08:15:50,728 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:50,729 INFO L225 Difference]: With dead ends: 56 [2021-05-06 08:15:50,729 INFO L226 Difference]: Without dead ends: 56 [2021-05-06 08:15:50,729 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 36.6ms TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2021-05-06 08:15:50,729 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2021-05-06 08:15:50,732 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2021-05-06 08:15:50,732 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 32 states have (on average 1.21875) internal successors, (39), 34 states have internal predecessors, (39), 17 states have call successors, (17), 6 states have call predecessors, (17), 5 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2021-05-06 08:15:50,733 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 71 transitions. [2021-05-06 08:15:50,733 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 71 transitions. Word has length 41 [2021-05-06 08:15:50,733 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:50,733 INFO L480 AbstractCegarLoop]: Abstraction has 55 states and 71 transitions. [2021-05-06 08:15:50,733 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 6 states have internal predecessors, (21), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2021-05-06 08:15:50,733 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 71 transitions. [2021-05-06 08:15:50,734 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2021-05-06 08:15:50,734 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:50,734 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:50,940 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:50,941 INFO L428 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:50,941 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:50,941 INFO L82 PathProgramCache]: Analyzing trace with hash -1581112078, now seen corresponding path program 1 times [2021-05-06 08:15:50,941 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:50,941 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [432895793] [2021-05-06 08:15:50,941 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:50,950 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:50,950 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2056914594] [2021-05-06 08:15:50,950 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:50,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:50,999 INFO L263 TraceCheckSpWp]: Trace formula consists of 187 conjuncts, 19 conjunts are in the unsatisfiable core [2021-05-06 08:15:51,000 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:51,034 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,035 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,084 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,085 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,087 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,089 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,100 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,101 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,102 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,103 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,121 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,122 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,124 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,125 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,137 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,138 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,140 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,141 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,153 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,154 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,155 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,155 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,162 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,178 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 12 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2021-05-06 08:15:51,179 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:51,179 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [432895793] [2021-05-06 08:15:51,179 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:51,181 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2056914594] [2021-05-06 08:15:51,181 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2056914594] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:51,181 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:51,181 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2021-05-06 08:15:51,181 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1091227549] [2021-05-06 08:15:51,182 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2021-05-06 08:15:51,182 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:51,182 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-05-06 08:15:51,182 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2021-05-06 08:15:51,182 INFO L87 Difference]: Start difference. First operand 55 states and 71 transitions. Second operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 6 states have internal predecessors, (21), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2021-05-06 08:15:51,264 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:51,265 INFO L93 Difference]: Finished difference Result 60 states and 75 transitions. [2021-05-06 08:15:51,265 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-05-06 08:15:51,265 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 6 states have internal predecessors, (21), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) Word has length 46 [2021-05-06 08:15:51,265 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:51,266 INFO L225 Difference]: With dead ends: 60 [2021-05-06 08:15:51,266 INFO L226 Difference]: Without dead ends: 60 [2021-05-06 08:15:51,266 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 51.0ms TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2021-05-06 08:15:51,266 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2021-05-06 08:15:51,269 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2021-05-06 08:15:51,269 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 35 states have (on average 1.2) internal successors, (42), 37 states have internal predecessors, (42), 17 states have call successors, (17), 7 states have call predecessors, (17), 6 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2021-05-06 08:15:51,270 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 74 transitions. [2021-05-06 08:15:51,270 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 74 transitions. Word has length 46 [2021-05-06 08:15:51,270 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:51,270 INFO L480 AbstractCegarLoop]: Abstraction has 59 states and 74 transitions. [2021-05-06 08:15:51,270 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 6 states have internal predecessors, (21), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2021-05-06 08:15:51,270 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 74 transitions. [2021-05-06 08:15:51,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2021-05-06 08:15:51,270 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:51,271 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:51,484 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:51,485 INFO L428 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:51,485 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:51,485 INFO L82 PathProgramCache]: Analyzing trace with hash 1942645143, now seen corresponding path program 1 times [2021-05-06 08:15:51,485 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:51,485 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2056657133] [2021-05-06 08:15:51,486 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:51,493 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:51,493 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [407401902] [2021-05-06 08:15:51,493 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:51,552 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:51,553 INFO L263 TraceCheckSpWp]: Trace formula consists of 196 conjuncts, 23 conjunts are in the unsatisfiable core [2021-05-06 08:15:51,555 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:51,599 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,600 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,610 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,611 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,633 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,633 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,641 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,642 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,649 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,650 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,673 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,674 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,682 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:51,691 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 14 proven. 7 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2021-05-06 08:15:51,691 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:51,691 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2056657133] [2021-05-06 08:15:51,691 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:51,691 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [407401902] [2021-05-06 08:15:51,691 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [407401902] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:51,691 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:51,691 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2021-05-06 08:15:51,691 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [509466574] [2021-05-06 08:15:51,691 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states [2021-05-06 08:15:51,691 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:51,692 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-05-06 08:15:51,692 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2021-05-06 08:15:51,692 INFO L87 Difference]: Start difference. First operand 59 states and 74 transitions. Second operand has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 2 states have call successors, (8) [2021-05-06 08:15:51,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:51,839 INFO L93 Difference]: Finished difference Result 64 states and 78 transitions. [2021-05-06 08:15:51,839 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2021-05-06 08:15:51,839 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 2 states have call successors, (8) Word has length 51 [2021-05-06 08:15:51,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:51,840 INFO L225 Difference]: With dead ends: 64 [2021-05-06 08:15:51,840 INFO L226 Difference]: Without dead ends: 64 [2021-05-06 08:15:51,840 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 41 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 59.2ms TimeCoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2021-05-06 08:15:51,840 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2021-05-06 08:15:51,843 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 63. [2021-05-06 08:15:51,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 17 states have call successors, (17), 8 states have call predecessors, (17), 7 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2021-05-06 08:15:51,843 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 77 transitions. [2021-05-06 08:15:51,843 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 77 transitions. Word has length 51 [2021-05-06 08:15:51,844 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:51,844 INFO L480 AbstractCegarLoop]: Abstraction has 63 states and 77 transitions. [2021-05-06 08:15:51,844 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 2 states have call successors, (8) [2021-05-06 08:15:51,844 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 77 transitions. [2021-05-06 08:15:51,844 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2021-05-06 08:15:51,844 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:51,844 INFO L523 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 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] [2021-05-06 08:15:52,052 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2021-05-06 08:15:52,053 INFO L428 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:52,053 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:52,053 INFO L82 PathProgramCache]: Analyzing trace with hash -1782154901, now seen corresponding path program 1 times [2021-05-06 08:15:52,053 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:52,053 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1560424051] [2021-05-06 08:15:52,053 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:52,060 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:52,060 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [418814602] [2021-05-06 08:15:52,060 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:52,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:52,113 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 11 conjunts are in the unsatisfiable core [2021-05-06 08:15:52,114 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:52,190 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,196 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2021-05-06 08:15:52,196 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:52,196 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1560424051] [2021-05-06 08:15:52,196 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:52,196 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [418814602] [2021-05-06 08:15:52,196 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [418814602] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:52,197 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:52,197 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2021-05-06 08:15:52,197 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [63644867] [2021-05-06 08:15:52,197 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2021-05-06 08:15:52,197 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:52,197 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-05-06 08:15:52,197 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2021-05-06 08:15:52,198 INFO L87 Difference]: Start difference. First operand 63 states and 77 transitions. Second operand has 6 states, 6 states have (on average 3.5) internal successors, (21), 5 states have internal predecessors, (21), 3 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) [2021-05-06 08:15:52,253 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:52,253 INFO L93 Difference]: Finished difference Result 94 states and 129 transitions. [2021-05-06 08:15:52,253 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-05-06 08:15:52,253 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.5) internal successors, (21), 5 states have internal predecessors, (21), 3 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 59 [2021-05-06 08:15:52,254 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:52,255 INFO L225 Difference]: With dead ends: 94 [2021-05-06 08:15:52,255 INFO L226 Difference]: Without dead ends: 94 [2021-05-06 08:15:52,255 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 17.7ms TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2021-05-06 08:15:52,255 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2021-05-06 08:15:52,259 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 84. [2021-05-06 08:15:52,260 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 49 states have (on average 1.2448979591836735) internal successors, (61), 52 states have internal predecessors, (61), 26 states have call successors, (26), 9 states have call predecessors, (26), 8 states have return successors, (24), 22 states have call predecessors, (24), 24 states have call successors, (24) [2021-05-06 08:15:52,260 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 111 transitions. [2021-05-06 08:15:52,260 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 111 transitions. Word has length 59 [2021-05-06 08:15:52,260 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:52,260 INFO L480 AbstractCegarLoop]: Abstraction has 84 states and 111 transitions. [2021-05-06 08:15:52,261 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 6 states, 6 states have (on average 3.5) internal successors, (21), 5 states have internal predecessors, (21), 3 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) [2021-05-06 08:15:52,261 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 111 transitions. [2021-05-06 08:15:52,261 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2021-05-06 08:15:52,261 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:52,261 INFO L523 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:52,467 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:52,467 INFO L428 AbstractCegarLoop]: === Iteration 10 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:52,467 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:52,468 INFO L82 PathProgramCache]: Analyzing trace with hash -1573186588, now seen corresponding path program 1 times [2021-05-06 08:15:52,468 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:52,468 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [920889431] [2021-05-06 08:15:52,468 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:52,474 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:52,474 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [907759168] [2021-05-06 08:15:52,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:52,530 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:52,531 INFO L263 TraceCheckSpWp]: Trace formula consists of 225 conjuncts, 9 conjunts are in the unsatisfiable core [2021-05-06 08:15:52,532 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:52,543 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,544 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,544 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,572 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,573 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,574 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,581 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,582 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,582 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,615 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,616 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,624 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2021-05-06 08:15:52,624 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:52,624 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [920889431] [2021-05-06 08:15:52,624 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:52,624 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [907759168] [2021-05-06 08:15:52,624 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [907759168] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:52,624 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:52,624 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2021-05-06 08:15:52,624 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1075061610] [2021-05-06 08:15:52,624 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2021-05-06 08:15:52,624 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:52,625 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-05-06 08:15:52,625 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2021-05-06 08:15:52,625 INFO L87 Difference]: Start difference. First operand 84 states and 111 transitions. Second operand has 6 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 5 states have internal predecessors, (22), 4 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2021-05-06 08:15:52,670 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:52,670 INFO L93 Difference]: Finished difference Result 99 states and 123 transitions. [2021-05-06 08:15:52,670 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-05-06 08:15:52,670 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 5 states have internal predecessors, (22), 4 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) Word has length 60 [2021-05-06 08:15:52,671 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:52,671 INFO L225 Difference]: With dead ends: 99 [2021-05-06 08:15:52,671 INFO L226 Difference]: Without dead ends: 99 [2021-05-06 08:15:52,672 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 55 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 13.4ms TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2021-05-06 08:15:52,672 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2021-05-06 08:15:52,675 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 99. [2021-05-06 08:15:52,676 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 61 states have (on average 1.1967213114754098) internal successors, (73), 64 states have internal predecessors, (73), 26 states have call successors, (26), 12 states have call predecessors, (26), 11 states have return successors, (24), 22 states have call predecessors, (24), 24 states have call successors, (24) [2021-05-06 08:15:52,676 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 123 transitions. [2021-05-06 08:15:52,676 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 123 transitions. Word has length 60 [2021-05-06 08:15:52,677 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:52,677 INFO L480 AbstractCegarLoop]: Abstraction has 99 states and 123 transitions. [2021-05-06 08:15:52,677 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 6 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 5 states have internal predecessors, (22), 4 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2021-05-06 08:15:52,677 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 123 transitions. [2021-05-06 08:15:52,677 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2021-05-06 08:15:52,677 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:52,677 INFO L523 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:52,884 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,11 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:52,885 INFO L428 AbstractCegarLoop]: === Iteration 11 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:52,885 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:52,885 INFO L82 PathProgramCache]: Analyzing trace with hash -1491020248, now seen corresponding path program 1 times [2021-05-06 08:15:52,885 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:52,886 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [694890899] [2021-05-06 08:15:52,886 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:52,892 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:52,892 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1304656709] [2021-05-06 08:15:52,892 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:52,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:52,950 INFO L263 TraceCheckSpWp]: Trace formula consists of 227 conjuncts, 9 conjunts are in the unsatisfiable core [2021-05-06 08:15:52,951 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:52,974 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,975 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,982 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,987 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,988 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,994 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:52,994 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,002 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,011 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,012 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,027 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,028 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,034 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,035 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,042 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,043 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,051 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,071 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2021-05-06 08:15:53,071 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:53,072 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [694890899] [2021-05-06 08:15:53,072 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:53,072 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1304656709] [2021-05-06 08:15:53,072 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1304656709] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:53,072 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:53,072 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2021-05-06 08:15:53,072 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [397845811] [2021-05-06 08:15:53,072 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2021-05-06 08:15:53,072 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:53,073 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-05-06 08:15:53,073 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2021-05-06 08:15:53,073 INFO L87 Difference]: Start difference. First operand 99 states and 123 transitions. Second operand has 8 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2021-05-06 08:15:53,214 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:53,214 INFO L93 Difference]: Finished difference Result 170 states and 243 transitions. [2021-05-06 08:15:53,215 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-05-06 08:15:53,215 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 61 [2021-05-06 08:15:53,215 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:53,216 INFO L225 Difference]: With dead ends: 170 [2021-05-06 08:15:53,216 INFO L226 Difference]: Without dead ends: 170 [2021-05-06 08:15:53,217 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 66.3ms TimeCoverageRelationStatistics Valid=55, Invalid=155, Unknown=0, NotChecked=0, Total=210 [2021-05-06 08:15:53,217 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 170 states. [2021-05-06 08:15:53,228 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 170 to 142. [2021-05-06 08:15:53,229 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 87 states have (on average 1.2873563218390804) internal successors, (112), 91 states have internal predecessors, (112), 43 states have call successors, (43), 12 states have call predecessors, (43), 11 states have return successors, (41), 38 states have call predecessors, (41), 41 states have call successors, (41) [2021-05-06 08:15:53,229 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 196 transitions. [2021-05-06 08:15:53,229 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 196 transitions. Word has length 61 [2021-05-06 08:15:53,230 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:53,230 INFO L480 AbstractCegarLoop]: Abstraction has 142 states and 196 transitions. [2021-05-06 08:15:53,230 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 8 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2021-05-06 08:15:53,230 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 196 transitions. [2021-05-06 08:15:53,230 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2021-05-06 08:15:53,230 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:53,230 INFO L523 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:53,447 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2021-05-06 08:15:53,447 INFO L428 AbstractCegarLoop]: === Iteration 12 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:53,448 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:53,448 INFO L82 PathProgramCache]: Analyzing trace with hash 1948826973, now seen corresponding path program 1 times [2021-05-06 08:15:53,448 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:53,448 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1797514330] [2021-05-06 08:15:53,448 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:53,454 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:53,454 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1603422760] [2021-05-06 08:15:53,454 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:53,503 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:53,504 INFO L263 TraceCheckSpWp]: Trace formula consists of 234 conjuncts, 9 conjunts are in the unsatisfiable core [2021-05-06 08:15:53,505 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:53,512 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,513 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,514 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,538 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,539 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,540 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,547 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,552 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,553 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,580 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,581 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,592 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2021-05-06 08:15:53,592 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:53,592 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1797514330] [2021-05-06 08:15:53,592 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:53,592 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1603422760] [2021-05-06 08:15:53,592 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1603422760] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:53,593 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:53,593 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2021-05-06 08:15:53,593 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [48846254] [2021-05-06 08:15:53,593 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2021-05-06 08:15:53,593 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:53,593 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-05-06 08:15:53,593 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2021-05-06 08:15:53,593 INFO L87 Difference]: Start difference. First operand 142 states and 196 transitions. Second operand has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 4 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2021-05-06 08:15:53,652 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:53,652 INFO L93 Difference]: Finished difference Result 142 states and 195 transitions. [2021-05-06 08:15:53,652 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-05-06 08:15:53,653 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 4 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) Word has length 62 [2021-05-06 08:15:53,653 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:53,656 INFO L225 Difference]: With dead ends: 142 [2021-05-06 08:15:53,656 INFO L226 Difference]: Without dead ends: 142 [2021-05-06 08:15:53,656 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 57 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 13.7ms TimeCoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2021-05-06 08:15:53,656 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2021-05-06 08:15:53,668 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 142. [2021-05-06 08:15:53,668 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 87 states have (on average 1.2758620689655173) internal successors, (111), 91 states have internal predecessors, (111), 43 states have call successors, (43), 12 states have call predecessors, (43), 11 states have return successors, (41), 38 states have call predecessors, (41), 41 states have call successors, (41) [2021-05-06 08:15:53,670 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 195 transitions. [2021-05-06 08:15:53,670 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 195 transitions. Word has length 62 [2021-05-06 08:15:53,670 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:53,670 INFO L480 AbstractCegarLoop]: Abstraction has 142 states and 195 transitions. [2021-05-06 08:15:53,670 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 4 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2021-05-06 08:15:53,670 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 195 transitions. [2021-05-06 08:15:53,671 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2021-05-06 08:15:53,671 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:53,671 INFO L523 BasicCegarLoop]: trace histogram [5, 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, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:53,884 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,13 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:53,885 INFO L428 AbstractCegarLoop]: === Iteration 13 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:53,885 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:53,885 INFO L82 PathProgramCache]: Analyzing trace with hash 1844620331, now seen corresponding path program 1 times [2021-05-06 08:15:53,885 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:53,885 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1365856181] [2021-05-06 08:15:53,885 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:53,891 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:53,891 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1876583672] [2021-05-06 08:15:53,891 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:53,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:53,934 INFO L263 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 11 conjunts are in the unsatisfiable core [2021-05-06 08:15:53,935 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:53,942 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,943 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,943 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,966 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,967 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,968 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,974 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,975 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:53,976 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,004 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,005 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,006 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,016 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,022 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,032 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 13 proven. 5 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2021-05-06 08:15:54,033 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:54,033 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1365856181] [2021-05-06 08:15:54,033 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:54,033 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1876583672] [2021-05-06 08:15:54,033 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1876583672] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:54,033 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:54,033 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2021-05-06 08:15:54,033 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1343194700] [2021-05-06 08:15:54,033 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2021-05-06 08:15:54,033 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:54,034 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-05-06 08:15:54,034 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2021-05-06 08:15:54,034 INFO L87 Difference]: Start difference. First operand 142 states and 195 transitions. Second operand has 7 states, 7 states have (on average 4.0) internal successors, (28), 6 states have internal predecessors, (28), 4 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2021-05-06 08:15:54,092 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:54,093 INFO L93 Difference]: Finished difference Result 169 states and 222 transitions. [2021-05-06 08:15:54,094 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-05-06 08:15:54,094 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 4.0) internal successors, (28), 6 states have internal predecessors, (28), 4 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) Word has length 66 [2021-05-06 08:15:54,094 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:54,095 INFO L225 Difference]: With dead ends: 169 [2021-05-06 08:15:54,095 INFO L226 Difference]: Without dead ends: 169 [2021-05-06 08:15:54,095 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 60 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 21.5ms TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2021-05-06 08:15:54,095 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2021-05-06 08:15:54,099 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 167. [2021-05-06 08:15:54,099 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 167 states, 105 states have (on average 1.2380952380952381) internal successors, (130), 108 states have internal predecessors, (130), 46 states have call successors, (46), 16 states have call predecessors, (46), 15 states have return successors, (44), 42 states have call predecessors, (44), 44 states have call successors, (44) [2021-05-06 08:15:54,100 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 167 states to 167 states and 220 transitions. [2021-05-06 08:15:54,100 INFO L78 Accepts]: Start accepts. Automaton has 167 states and 220 transitions. Word has length 66 [2021-05-06 08:15:54,100 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:54,100 INFO L480 AbstractCegarLoop]: Abstraction has 167 states and 220 transitions. [2021-05-06 08:15:54,101 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 7 states, 7 states have (on average 4.0) internal successors, (28), 6 states have internal predecessors, (28), 4 states have call successors, (11), 4 states have call predecessors, (11), 2 states have return successors, (9), 2 states have call predecessors, (9), 3 states have call successors, (9) [2021-05-06 08:15:54,101 INFO L276 IsEmpty]: Start isEmpty. Operand 167 states and 220 transitions. [2021-05-06 08:15:54,101 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2021-05-06 08:15:54,101 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:54,101 INFO L523 BasicCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 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] [2021-05-06 08:15:54,321 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2021-05-06 08:15:54,321 INFO L428 AbstractCegarLoop]: === Iteration 14 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:54,321 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:54,321 INFO L82 PathProgramCache]: Analyzing trace with hash 918639692, now seen corresponding path program 1 times [2021-05-06 08:15:54,321 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:54,321 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1442737426] [2021-05-06 08:15:54,321 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:54,327 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:54,327 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [957449377] [2021-05-06 08:15:54,327 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:54,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:54,385 INFO L263 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 22 conjunts are in the unsatisfiable core [2021-05-06 08:15:54,387 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:54,509 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,516 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 15 proven. 14 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2021-05-06 08:15:54,516 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:54,517 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1442737426] [2021-05-06 08:15:54,517 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:54,517 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [957449377] [2021-05-06 08:15:54,517 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [957449377] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:54,517 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:54,517 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2021-05-06 08:15:54,517 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1925837688] [2021-05-06 08:15:54,517 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2021-05-06 08:15:54,517 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:54,518 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-05-06 08:15:54,518 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2021-05-06 08:15:54,518 INFO L87 Difference]: Start difference. First operand 167 states and 220 transitions. Second operand has 8 states, 8 states have (on average 3.5) internal successors, (28), 7 states have internal predecessors, (28), 3 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2021-05-06 08:15:54,631 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:54,631 INFO L93 Difference]: Finished difference Result 212 states and 294 transitions. [2021-05-06 08:15:54,631 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-05-06 08:15:54,631 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.5) internal successors, (28), 7 states have internal predecessors, (28), 3 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 68 [2021-05-06 08:15:54,631 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:54,632 INFO L225 Difference]: With dead ends: 212 [2021-05-06 08:15:54,632 INFO L226 Difference]: Without dead ends: 211 [2021-05-06 08:15:54,633 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 60 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 59.3ms TimeCoverageRelationStatistics Valid=25, Invalid=65, Unknown=0, NotChecked=0, Total=90 [2021-05-06 08:15:54,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 211 states. [2021-05-06 08:15:54,640 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 211 to 208. [2021-05-06 08:15:54,640 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 208 states, 126 states have (on average 1.2857142857142858) internal successors, (162), 132 states have internal predecessors, (162), 65 states have call successors, (65), 17 states have call predecessors, (65), 16 states have return successors, (62), 58 states have call predecessors, (62), 62 states have call successors, (62) [2021-05-06 08:15:54,641 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 208 states to 208 states and 289 transitions. [2021-05-06 08:15:54,641 INFO L78 Accepts]: Start accepts. Automaton has 208 states and 289 transitions. Word has length 68 [2021-05-06 08:15:54,642 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:54,642 INFO L480 AbstractCegarLoop]: Abstraction has 208 states and 289 transitions. [2021-05-06 08:15:54,643 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 8 states, 8 states have (on average 3.5) internal successors, (28), 7 states have internal predecessors, (28), 3 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2021-05-06 08:15:54,643 INFO L276 IsEmpty]: Start isEmpty. Operand 208 states and 289 transitions. [2021-05-06 08:15:54,643 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2021-05-06 08:15:54,643 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:54,643 INFO L523 BasicCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 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] [2021-05-06 08:15:54,859 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,15 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:54,859 INFO L428 AbstractCegarLoop]: === Iteration 15 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:54,859 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:54,860 INFO L82 PathProgramCache]: Analyzing trace with hash -210356579, now seen corresponding path program 2 times [2021-05-06 08:15:54,860 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:54,860 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1533976323] [2021-05-06 08:15:54,860 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:54,865 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:54,865 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [92769384] [2021-05-06 08:15:54,865 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:54,927 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-06 08:15:54,927 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-06 08:15:54,928 INFO L263 TraceCheckSpWp]: Trace formula consists of 253 conjuncts, 34 conjunts are in the unsatisfiable core [2021-05-06 08:15:54,930 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:54,949 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,950 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,968 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,969 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,970 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,970 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,977 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,978 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,979 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:54,979 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,010 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,010 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,011 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,012 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,020 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,021 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,021 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,022 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,029 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,029 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,030 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,031 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,038 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,039 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,040 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,041 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,048 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,089 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,090 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,097 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,098 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,109 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,110 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,118 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,127 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 17 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2021-05-06 08:15:55,127 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:55,127 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1533976323] [2021-05-06 08:15:55,128 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:55,128 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [92769384] [2021-05-06 08:15:55,128 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [92769384] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:55,128 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:55,128 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2021-05-06 08:15:55,128 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [959415757] [2021-05-06 08:15:55,128 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2021-05-06 08:15:55,128 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:55,128 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-05-06 08:15:55,128 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2021-05-06 08:15:55,129 INFO L87 Difference]: Start difference. First operand 208 states and 289 transitions. Second operand has 11 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 9 states have internal predecessors, (28), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) [2021-05-06 08:15:55,339 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:55,339 INFO L93 Difference]: Finished difference Result 214 states and 294 transitions. [2021-05-06 08:15:55,340 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-05-06 08:15:55,340 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 9 states have internal predecessors, (28), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) Word has length 73 [2021-05-06 08:15:55,340 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:55,341 INFO L225 Difference]: With dead ends: 214 [2021-05-06 08:15:55,341 INFO L226 Difference]: Without dead ends: 214 [2021-05-06 08:15:55,341 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 63 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 114.5ms TimeCoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2021-05-06 08:15:55,341 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 214 states. [2021-05-06 08:15:55,345 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 214 to 212. [2021-05-06 08:15:55,346 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 212 states, 129 states have (on average 1.2790697674418605) internal successors, (165), 135 states have internal predecessors, (165), 65 states have call successors, (65), 18 states have call predecessors, (65), 17 states have return successors, (62), 58 states have call predecessors, (62), 62 states have call successors, (62) [2021-05-06 08:15:55,346 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 212 states to 212 states and 292 transitions. [2021-05-06 08:15:55,347 INFO L78 Accepts]: Start accepts. Automaton has 212 states and 292 transitions. Word has length 73 [2021-05-06 08:15:55,347 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:55,347 INFO L480 AbstractCegarLoop]: Abstraction has 212 states and 292 transitions. [2021-05-06 08:15:55,347 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 11 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 9 states have internal predecessors, (28), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 5 states have call predecessors, (11), 5 states have call successors, (11) [2021-05-06 08:15:55,347 INFO L276 IsEmpty]: Start isEmpty. Operand 212 states and 292 transitions. [2021-05-06 08:15:55,347 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2021-05-06 08:15:55,347 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:55,348 INFO L523 BasicCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:55,567 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2021-05-06 08:15:55,567 INFO L428 AbstractCegarLoop]: === Iteration 16 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:55,567 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:55,567 INFO L82 PathProgramCache]: Analyzing trace with hash 952478412, now seen corresponding path program 3 times [2021-05-06 08:15:55,567 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:55,568 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1766107930] [2021-05-06 08:15:55,568 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:55,573 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:55,573 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1900899566] [2021-05-06 08:15:55,573 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:55,630 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2021-05-06 08:15:55,630 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-06 08:15:55,631 INFO L263 TraceCheckSpWp]: Trace formula consists of 226 conjuncts, 46 conjunts are in the unsatisfiable core [2021-05-06 08:15:55,633 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:55,655 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,656 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,679 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,679 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,686 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,687 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,719 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,720 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,729 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,731 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,738 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,739 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,747 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,748 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,815 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,817 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,823 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,824 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,831 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,839 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,887 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,889 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,894 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,897 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,906 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,908 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,911 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,913 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,914 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,916 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,918 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,920 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,922 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,924 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,925 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,926 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,928 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,930 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,948 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,950 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,951 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,954 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,955 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,957 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,970 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:55,980 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 31 proven. 19 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2021-05-06 08:15:55,980 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:55,980 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1766107930] [2021-05-06 08:15:55,981 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:55,981 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1900899566] [2021-05-06 08:15:55,981 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1900899566] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:55,981 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:55,981 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2021-05-06 08:15:55,981 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [435377745] [2021-05-06 08:15:55,981 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states [2021-05-06 08:15:55,981 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:55,982 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2021-05-06 08:15:55,982 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=173, Unknown=0, NotChecked=0, Total=210 [2021-05-06 08:15:55,982 INFO L87 Difference]: Start difference. First operand 212 states and 292 transitions. Second operand has 15 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 12 states have internal predecessors, (31), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (12), 6 states have call predecessors, (12), 5 states have call successors, (12) [2021-05-06 08:15:56,571 WARN L205 SmtUtils]: Spent 187.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2021-05-06 08:15:56,777 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:56,777 INFO L93 Difference]: Finished difference Result 222 states and 300 transitions. [2021-05-06 08:15:56,777 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2021-05-06 08:15:56,777 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 12 states have internal predecessors, (31), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (12), 6 states have call predecessors, (12), 5 states have call successors, (12) Word has length 78 [2021-05-06 08:15:56,778 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:56,778 INFO L225 Difference]: With dead ends: 222 [2021-05-06 08:15:56,778 INFO L226 Difference]: Without dead ends: 222 [2021-05-06 08:15:56,779 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 521.7ms TimeCoverageRelationStatistics Valid=70, Invalid=350, Unknown=0, NotChecked=0, Total=420 [2021-05-06 08:15:56,779 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 222 states. [2021-05-06 08:15:56,783 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 222 to 220. [2021-05-06 08:15:56,784 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 220 states, 135 states have (on average 1.2666666666666666) internal successors, (171), 141 states have internal predecessors, (171), 65 states have call successors, (65), 20 states have call predecessors, (65), 19 states have return successors, (62), 58 states have call predecessors, (62), 62 states have call successors, (62) [2021-05-06 08:15:56,784 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 220 states to 220 states and 298 transitions. [2021-05-06 08:15:56,784 INFO L78 Accepts]: Start accepts. Automaton has 220 states and 298 transitions. Word has length 78 [2021-05-06 08:15:56,785 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:56,785 INFO L480 AbstractCegarLoop]: Abstraction has 220 states and 298 transitions. [2021-05-06 08:15:56,785 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 15 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 12 states have internal predecessors, (31), 6 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (12), 6 states have call predecessors, (12), 5 states have call successors, (12) [2021-05-06 08:15:56,785 INFO L276 IsEmpty]: Start isEmpty. Operand 220 states and 298 transitions. [2021-05-06 08:15:56,785 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2021-05-06 08:15:56,785 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:56,785 INFO L523 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:57,000 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2021-05-06 08:15:57,001 INFO L428 AbstractCegarLoop]: === Iteration 17 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:57,001 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:57,001 INFO L82 PathProgramCache]: Analyzing trace with hash -1350616622, now seen corresponding path program 2 times [2021-05-06 08:15:57,001 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:57,001 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1051374476] [2021-05-06 08:15:57,001 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:57,007 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:57,007 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1692494449] [2021-05-06 08:15:57,008 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:57,065 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-06 08:15:57,065 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-06 08:15:57,066 INFO L263 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 22 conjunts are in the unsatisfiable core [2021-05-06 08:15:57,068 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:57,147 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,148 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,155 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,156 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,163 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,164 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,188 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,190 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,200 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,220 INFO L134 CoverageAnalysis]: Checked inductivity of 165 backedges. 27 proven. 23 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2021-05-06 08:15:57,220 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:57,220 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1051374476] [2021-05-06 08:15:57,220 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:57,220 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1692494449] [2021-05-06 08:15:57,220 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1692494449] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:57,220 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:57,221 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2021-05-06 08:15:57,221 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [224712177] [2021-05-06 08:15:57,221 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states [2021-05-06 08:15:57,221 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:57,223 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-05-06 08:15:57,223 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2021-05-06 08:15:57,223 INFO L87 Difference]: Start difference. First operand 220 states and 298 transitions. Second operand has 10 states, 10 states have (on average 2.7) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 3 states have call predecessors, (13), 4 states have call successors, (13) [2021-05-06 08:15:57,504 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:57,505 INFO L93 Difference]: Finished difference Result 283 states and 405 transitions. [2021-05-06 08:15:57,505 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2021-05-06 08:15:57,505 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.7) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 3 states have call predecessors, (13), 4 states have call successors, (13) Word has length 82 [2021-05-06 08:15:57,505 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:57,506 INFO L225 Difference]: With dead ends: 283 [2021-05-06 08:15:57,506 INFO L226 Difference]: Without dead ends: 283 [2021-05-06 08:15:57,506 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 73 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 62.6ms TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2021-05-06 08:15:57,507 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 283 states. [2021-05-06 08:15:57,512 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 283 to 253. [2021-05-06 08:15:57,512 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 253 states, 150 states have (on average 1.2933333333333332) internal successors, (194), 157 states have internal predecessors, (194), 82 states have call successors, (82), 21 states have call predecessors, (82), 20 states have return successors, (79), 74 states have call predecessors, (79), 79 states have call successors, (79) [2021-05-06 08:15:57,513 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 253 states to 253 states and 355 transitions. [2021-05-06 08:15:57,513 INFO L78 Accepts]: Start accepts. Automaton has 253 states and 355 transitions. Word has length 82 [2021-05-06 08:15:57,513 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:57,513 INFO L480 AbstractCegarLoop]: Abstraction has 253 states and 355 transitions. [2021-05-06 08:15:57,514 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 10 states, 10 states have (on average 2.7) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 3 states have call predecessors, (13), 4 states have call successors, (13) [2021-05-06 08:15:57,514 INFO L276 IsEmpty]: Start isEmpty. Operand 253 states and 355 transitions. [2021-05-06 08:15:57,514 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2021-05-06 08:15:57,514 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:57,514 INFO L523 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:57,717 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable23 [2021-05-06 08:15:57,717 INFO L428 AbstractCegarLoop]: === Iteration 18 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:57,717 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:57,717 INFO L82 PathProgramCache]: Analyzing trace with hash -1080401827, now seen corresponding path program 1 times [2021-05-06 08:15:57,717 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:57,717 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [194523238] [2021-05-06 08:15:57,717 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:57,722 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:57,722 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [396861975] [2021-05-06 08:15:57,722 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:57,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:57,775 INFO L263 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 11 conjunts are in the unsatisfiable core [2021-05-06 08:15:57,776 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:57,794 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,795 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,795 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,817 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,818 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,819 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,824 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,825 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,826 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,854 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,855 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,855 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,881 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,882 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:57,891 INFO L134 CoverageAnalysis]: Checked inductivity of 161 backedges. 16 proven. 73 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2021-05-06 08:15:57,891 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:57,891 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [194523238] [2021-05-06 08:15:57,891 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:57,891 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [396861975] [2021-05-06 08:15:57,891 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [396861975] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:57,891 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:57,891 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2021-05-06 08:15:57,891 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1718665683] [2021-05-06 08:15:57,891 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2021-05-06 08:15:57,891 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:57,892 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-05-06 08:15:57,892 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2021-05-06 08:15:57,892 INFO L87 Difference]: Start difference. First operand 253 states and 355 transitions. Second operand has 7 states, 7 states have (on average 4.0) internal successors, (28), 6 states have internal predecessors, (28), 5 states have call successors, (15), 5 states have call predecessors, (15), 3 states have return successors, (13), 3 states have call predecessors, (13), 4 states have call successors, (13) [2021-05-06 08:15:57,954 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:57,954 INFO L93 Difference]: Finished difference Result 256 states and 358 transitions. [2021-05-06 08:15:57,954 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-05-06 08:15:57,954 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 4.0) internal successors, (28), 6 states have internal predecessors, (28), 5 states have call successors, (15), 5 states have call predecessors, (15), 3 states have return successors, (13), 3 states have call predecessors, (13), 4 states have call successors, (13) Word has length 83 [2021-05-06 08:15:57,954 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:57,955 INFO L225 Difference]: With dead ends: 256 [2021-05-06 08:15:57,955 INFO L226 Difference]: Without dead ends: 256 [2021-05-06 08:15:57,956 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 77 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 20.5ms TimeCoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2021-05-06 08:15:57,956 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 256 states. [2021-05-06 08:15:57,960 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 256 to 256. [2021-05-06 08:15:57,960 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 256 states, 153 states have (on average 1.2875816993464053) internal successors, (197), 160 states have internal predecessors, (197), 82 states have call successors, (82), 21 states have call predecessors, (82), 20 states have return successors, (79), 74 states have call predecessors, (79), 79 states have call successors, (79) [2021-05-06 08:15:57,961 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 256 states to 256 states and 358 transitions. [2021-05-06 08:15:57,961 INFO L78 Accepts]: Start accepts. Automaton has 256 states and 358 transitions. Word has length 83 [2021-05-06 08:15:57,961 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:57,961 INFO L480 AbstractCegarLoop]: Abstraction has 256 states and 358 transitions. [2021-05-06 08:15:57,962 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 7 states, 7 states have (on average 4.0) internal successors, (28), 6 states have internal predecessors, (28), 5 states have call successors, (15), 5 states have call predecessors, (15), 3 states have return successors, (13), 3 states have call predecessors, (13), 4 states have call successors, (13) [2021-05-06 08:15:57,962 INFO L276 IsEmpty]: Start isEmpty. Operand 256 states and 358 transitions. [2021-05-06 08:15:57,962 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2021-05-06 08:15:57,962 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:57,962 INFO L523 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:58,172 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable24 [2021-05-06 08:15:58,173 INFO L428 AbstractCegarLoop]: === Iteration 19 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:58,173 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:58,173 INFO L82 PathProgramCache]: Analyzing trace with hash 900405455, now seen corresponding path program 1 times [2021-05-06 08:15:58,173 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:58,173 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2111740535] [2021-05-06 08:15:58,173 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:58,182 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:58,182 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [393850107] [2021-05-06 08:15:58,182 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:58,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:58,249 INFO L263 TraceCheckSpWp]: Trace formula consists of 273 conjuncts, 37 conjunts are in the unsatisfiable core [2021-05-06 08:15:58,250 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:58,397 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:58,406 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2021-05-06 08:15:58,406 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:58,406 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2111740535] [2021-05-06 08:15:58,406 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:58,406 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [393850107] [2021-05-06 08:15:58,406 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [393850107] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:58,406 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:58,406 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2021-05-06 08:15:58,407 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1374192405] [2021-05-06 08:15:58,408 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2021-05-06 08:15:58,408 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:58,408 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-05-06 08:15:58,408 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2021-05-06 08:15:58,409 INFO L87 Difference]: Start difference. First operand 256 states and 358 transitions. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2021-05-06 08:15:58,621 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:58,621 INFO L93 Difference]: Finished difference Result 287 states and 409 transitions. [2021-05-06 08:15:58,621 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-05-06 08:15:58,622 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 3.25) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) Word has length 84 [2021-05-06 08:15:58,622 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:58,623 INFO L225 Difference]: With dead ends: 287 [2021-05-06 08:15:58,623 INFO L226 Difference]: Without dead ends: 286 [2021-05-06 08:15:58,623 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 76 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 85.1ms TimeCoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2021-05-06 08:15:58,624 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 286 states. [2021-05-06 08:15:58,630 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 286 to 285. [2021-05-06 08:15:58,630 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 285 states, 168 states have (on average 1.3035714285714286) internal successors, (219), 176 states have internal predecessors, (219), 95 states have call successors, (95), 22 states have call predecessors, (95), 21 states have return successors, (92), 86 states have call predecessors, (92), 92 states have call successors, (92) [2021-05-06 08:15:58,631 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 285 states to 285 states and 406 transitions. [2021-05-06 08:15:58,631 INFO L78 Accepts]: Start accepts. Automaton has 285 states and 406 transitions. Word has length 84 [2021-05-06 08:15:58,633 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:58,633 INFO L480 AbstractCegarLoop]: Abstraction has 285 states and 406 transitions. [2021-05-06 08:15:58,633 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 9 states, 8 states have (on average 3.25) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2021-05-06 08:15:58,633 INFO L276 IsEmpty]: Start isEmpty. Operand 285 states and 406 transitions. [2021-05-06 08:15:58,634 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2021-05-06 08:15:58,634 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:58,634 INFO L523 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:58,850 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 20 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable25 [2021-05-06 08:15:58,850 INFO L428 AbstractCegarLoop]: === Iteration 20 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:58,850 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:58,850 INFO L82 PathProgramCache]: Analyzing trace with hash -2138218929, now seen corresponding path program 2 times [2021-05-06 08:15:58,850 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:58,850 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [924320791] [2021-05-06 08:15:58,850 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:58,855 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:58,855 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [350489625] [2021-05-06 08:15:58,855 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:58,909 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-06 08:15:58,909 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-06 08:15:58,910 INFO L263 TraceCheckSpWp]: Trace formula consists of 291 conjuncts, 13 conjunts are in the unsatisfiable core [2021-05-06 08:15:58,911 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:58,918 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:58,921 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:58,921 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:58,949 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:58,950 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:58,950 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:58,959 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:58,961 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:58,961 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:58,992 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:58,993 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:58,996 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,005 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,006 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,007 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,036 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,037 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,058 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 16 proven. 79 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2021-05-06 08:15:59,058 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:59,058 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [924320791] [2021-05-06 08:15:59,059 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:59,059 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [350489625] [2021-05-06 08:15:59,059 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [350489625] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:59,059 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:59,059 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2021-05-06 08:15:59,059 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [784804853] [2021-05-06 08:15:59,059 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2021-05-06 08:15:59,059 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:59,059 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-05-06 08:15:59,059 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2021-05-06 08:15:59,059 INFO L87 Difference]: Start difference. First operand 285 states and 406 transitions. Second operand has 8 states, 8 states have (on average 4.0) internal successors, (32), 7 states have internal predecessors, (32), 5 states have call successors, (15), 5 states have call predecessors, (15), 3 states have return successors, (13), 3 states have call predecessors, (13), 4 states have call successors, (13) [2021-05-06 08:15:59,132 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:59,132 INFO L93 Difference]: Finished difference Result 324 states and 442 transitions. [2021-05-06 08:15:59,132 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-05-06 08:15:59,133 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.0) internal successors, (32), 7 states have internal predecessors, (32), 5 states have call successors, (15), 5 states have call predecessors, (15), 3 states have return successors, (13), 3 states have call predecessors, (13), 4 states have call successors, (13) Word has length 87 [2021-05-06 08:15:59,133 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:59,134 INFO L225 Difference]: With dead ends: 324 [2021-05-06 08:15:59,134 INFO L226 Difference]: Without dead ends: 324 [2021-05-06 08:15:59,134 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 46.1ms TimeCoverageRelationStatistics Valid=42, Invalid=68, Unknown=0, NotChecked=0, Total=110 [2021-05-06 08:15:59,135 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 324 states. [2021-05-06 08:15:59,140 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 324 to 323. [2021-05-06 08:15:59,141 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 323 states, 196 states have (on average 1.2653061224489797) internal successors, (248), 203 states have internal predecessors, (248), 98 states have call successors, (98), 29 states have call predecessors, (98), 28 states have return successors, (95), 90 states have call predecessors, (95), 95 states have call successors, (95) [2021-05-06 08:15:59,142 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 323 states to 323 states and 441 transitions. [2021-05-06 08:15:59,142 INFO L78 Accepts]: Start accepts. Automaton has 323 states and 441 transitions. Word has length 87 [2021-05-06 08:15:59,142 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:59,142 INFO L480 AbstractCegarLoop]: Abstraction has 323 states and 441 transitions. [2021-05-06 08:15:59,142 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 8 states, 8 states have (on average 4.0) internal successors, (32), 7 states have internal predecessors, (32), 5 states have call successors, (15), 5 states have call predecessors, (15), 3 states have return successors, (13), 3 states have call predecessors, (13), 4 states have call successors, (13) [2021-05-06 08:15:59,142 INFO L276 IsEmpty]: Start isEmpty. Operand 323 states and 441 transitions. [2021-05-06 08:15:59,144 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2021-05-06 08:15:59,144 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:59,144 INFO L523 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:15:59,357 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable26 [2021-05-06 08:15:59,357 INFO L428 AbstractCegarLoop]: === Iteration 21 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:59,357 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:59,357 INFO L82 PathProgramCache]: Analyzing trace with hash 118626568, now seen corresponding path program 1 times [2021-05-06 08:15:59,357 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:59,357 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1091463565] [2021-05-06 08:15:59,357 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:59,364 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:59,364 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1544277662] [2021-05-06 08:15:59,364 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:59,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:15:59,423 INFO L263 TraceCheckSpWp]: Trace formula consists of 300 conjuncts, 13 conjunts are in the unsatisfiable core [2021-05-06 08:15:59,424 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:59,431 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,432 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,433 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,456 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,457 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,457 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,463 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,464 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,466 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,493 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,495 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,495 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,502 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,503 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,503 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,531 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,532 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,543 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 21 proven. 78 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2021-05-06 08:15:59,543 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:15:59,543 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1091463565] [2021-05-06 08:15:59,543 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:15:59,543 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1544277662] [2021-05-06 08:15:59,543 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1544277662] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:15:59,543 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:15:59,544 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2021-05-06 08:15:59,544 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1907004459] [2021-05-06 08:15:59,544 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2021-05-06 08:15:59,544 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:15:59,544 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-05-06 08:15:59,544 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2021-05-06 08:15:59,544 INFO L87 Difference]: Start difference. First operand 323 states and 441 transitions. Second operand has 8 states, 8 states have (on average 4.25) internal successors, (34), 7 states have internal predecessors, (34), 5 states have call successors, (15), 5 states have call predecessors, (15), 3 states have return successors, (13), 3 states have call predecessors, (13), 4 states have call successors, (13) [2021-05-06 08:15:59,619 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:15:59,619 INFO L93 Difference]: Finished difference Result 325 states and 441 transitions. [2021-05-06 08:15:59,619 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-05-06 08:15:59,619 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.25) internal successors, (34), 7 states have internal predecessors, (34), 5 states have call successors, (15), 5 states have call predecessors, (15), 3 states have return successors, (13), 3 states have call predecessors, (13), 4 states have call successors, (13) Word has length 89 [2021-05-06 08:15:59,619 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:15:59,621 INFO L225 Difference]: With dead ends: 325 [2021-05-06 08:15:59,621 INFO L226 Difference]: Without dead ends: 325 [2021-05-06 08:15:59,621 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 82 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 30.0ms TimeCoverageRelationStatistics Valid=41, Invalid=69, Unknown=0, NotChecked=0, Total=110 [2021-05-06 08:15:59,621 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 325 states. [2021-05-06 08:15:59,627 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 325 to 325. [2021-05-06 08:15:59,628 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 325 states, 198 states have (on average 1.2525252525252526) internal successors, (248), 205 states have internal predecessors, (248), 98 states have call successors, (98), 29 states have call predecessors, (98), 28 states have return successors, (95), 90 states have call predecessors, (95), 95 states have call successors, (95) [2021-05-06 08:15:59,629 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 325 states to 325 states and 441 transitions. [2021-05-06 08:15:59,629 INFO L78 Accepts]: Start accepts. Automaton has 325 states and 441 transitions. Word has length 89 [2021-05-06 08:15:59,629 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:15:59,629 INFO L480 AbstractCegarLoop]: Abstraction has 325 states and 441 transitions. [2021-05-06 08:15:59,629 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 8 states, 8 states have (on average 4.25) internal successors, (34), 7 states have internal predecessors, (34), 5 states have call successors, (15), 5 states have call predecessors, (15), 3 states have return successors, (13), 3 states have call predecessors, (13), 4 states have call successors, (13) [2021-05-06 08:15:59,629 INFO L276 IsEmpty]: Start isEmpty. Operand 325 states and 441 transitions. [2021-05-06 08:15:59,630 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2021-05-06 08:15:59,630 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:15:59,630 INFO L523 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 4, 3, 3, 3, 3, 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] [2021-05-06 08:15:59,833 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable27 [2021-05-06 08:15:59,834 INFO L428 AbstractCegarLoop]: === Iteration 22 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:15:59,834 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:15:59,834 INFO L82 PathProgramCache]: Analyzing trace with hash 1881160278, now seen corresponding path program 2 times [2021-05-06 08:15:59,834 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:15:59,834 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1672550980] [2021-05-06 08:15:59,834 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:15:59,840 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:15:59,840 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1832709876] [2021-05-06 08:15:59,840 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:15:59,896 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-06 08:15:59,896 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-06 08:15:59,897 INFO L263 TraceCheckSpWp]: Trace formula consists of 320 conjuncts, 5 conjunts are in the unsatisfiable core [2021-05-06 08:15:59,898 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:15:59,961 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,962 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,962 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,970 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,977 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,978 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,984 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,985 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,990 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,990 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,995 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:15:59,996 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,011 INFO L134 CoverageAnalysis]: Checked inductivity of 181 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 139 trivial. 0 not checked. [2021-05-06 08:16:00,011 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:16:00,011 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1672550980] [2021-05-06 08:16:00,011 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:16:00,011 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1832709876] [2021-05-06 08:16:00,011 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1832709876] provided 1 perfect and 0 imperfect interpolant sequences [2021-05-06 08:16:00,011 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-05-06 08:16:00,011 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-05-06 08:16:00,011 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [579169877] [2021-05-06 08:16:00,011 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2021-05-06 08:16:00,011 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:16:00,012 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-05-06 08:16:00,012 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-05-06 08:16:00,012 INFO L87 Difference]: Start difference. First operand 325 states and 441 transitions. Second operand has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) [2021-05-06 08:16:00,058 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:16:00,059 INFO L93 Difference]: Finished difference Result 427 states and 611 transitions. [2021-05-06 08:16:00,060 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-05-06 08:16:00,060 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) Word has length 93 [2021-05-06 08:16:00,060 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:16:00,062 INFO L225 Difference]: With dead ends: 427 [2021-05-06 08:16:00,062 INFO L226 Difference]: Without dead ends: 427 [2021-05-06 08:16:00,063 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 90 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 26.9ms TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2021-05-06 08:16:00,063 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 427 states. [2021-05-06 08:16:00,070 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 427 to 361. [2021-05-06 08:16:00,071 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 361 states, 222 states have (on average 1.2657657657657657) internal successors, (281), 229 states have internal predecessors, (281), 110 states have call successors, (110), 29 states have call predecessors, (110), 28 states have return successors, (107), 102 states have call predecessors, (107), 107 states have call successors, (107) [2021-05-06 08:16:00,072 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 361 states to 361 states and 498 transitions. [2021-05-06 08:16:00,072 INFO L78 Accepts]: Start accepts. Automaton has 361 states and 498 transitions. Word has length 93 [2021-05-06 08:16:00,073 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:16:00,073 INFO L480 AbstractCegarLoop]: Abstraction has 361 states and 498 transitions. [2021-05-06 08:16:00,073 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) [2021-05-06 08:16:00,073 INFO L276 IsEmpty]: Start isEmpty. Operand 361 states and 498 transitions. [2021-05-06 08:16:00,073 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2021-05-06 08:16:00,073 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:16:00,073 INFO L523 BasicCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:16:00,290 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable28,23 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:16:00,290 INFO L428 AbstractCegarLoop]: === Iteration 23 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:16:00,291 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:16:00,291 INFO L82 PathProgramCache]: Analyzing trace with hash 653404933, now seen corresponding path program 1 times [2021-05-06 08:16:00,291 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:16:00,291 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [267495933] [2021-05-06 08:16:00,291 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:16:00,306 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:16:00,306 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1895497266] [2021-05-06 08:16:00,306 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:16:00,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-06 08:16:00,460 INFO L263 TraceCheckSpWp]: Trace formula consists of 308 conjuncts, 65 conjunts are in the unsatisfiable core [2021-05-06 08:16:00,462 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:16:00,601 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,604 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,611 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,612 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,660 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,661 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,675 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,676 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,790 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,791 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,799 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,801 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,809 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,810 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,829 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,830 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,841 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:00,852 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 84 proven. 44 refuted. 0 times theorem prover too weak. 160 trivial. 0 not checked. [2021-05-06 08:16:00,852 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:16:00,852 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [267495933] [2021-05-06 08:16:00,852 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:16:00,852 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1895497266] [2021-05-06 08:16:00,852 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1895497266] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:16:00,852 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:16:00,852 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2021-05-06 08:16:00,853 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [667335473] [2021-05-06 08:16:00,853 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2021-05-06 08:16:00,853 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:16:00,853 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-05-06 08:16:00,853 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2021-05-06 08:16:00,853 INFO L87 Difference]: Start difference. First operand 361 states and 498 transitions. Second operand has 13 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 11 states have internal predecessors, (31), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2021-05-06 08:16:01,278 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:16:01,278 INFO L93 Difference]: Finished difference Result 367 states and 503 transitions. [2021-05-06 08:16:01,278 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-05-06 08:16:01,278 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 11 states have internal predecessors, (31), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 101 [2021-05-06 08:16:01,279 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:16:01,280 INFO L225 Difference]: With dead ends: 367 [2021-05-06 08:16:01,280 INFO L226 Difference]: Without dead ends: 367 [2021-05-06 08:16:01,280 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 86 SyntacticMatches, 3 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 269.8ms TimeCoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2021-05-06 08:16:01,280 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 367 states. [2021-05-06 08:16:01,286 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 367 to 365. [2021-05-06 08:16:01,286 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 365 states, 225 states have (on average 1.2622222222222221) internal successors, (284), 232 states have internal predecessors, (284), 110 states have call successors, (110), 30 states have call predecessors, (110), 29 states have return successors, (107), 102 states have call predecessors, (107), 107 states have call successors, (107) [2021-05-06 08:16:01,287 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 365 states to 365 states and 501 transitions. [2021-05-06 08:16:01,287 INFO L78 Accepts]: Start accepts. Automaton has 365 states and 501 transitions. Word has length 101 [2021-05-06 08:16:01,287 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:16:01,287 INFO L480 AbstractCegarLoop]: Abstraction has 365 states and 501 transitions. [2021-05-06 08:16:01,288 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 13 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 11 states have internal predecessors, (31), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2021-05-06 08:16:01,288 INFO L276 IsEmpty]: Start isEmpty. Operand 365 states and 501 transitions. [2021-05-06 08:16:01,288 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2021-05-06 08:16:01,288 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:16:01,288 INFO L523 BasicCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:16:01,505 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable29,24 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:16:01,505 INFO L428 AbstractCegarLoop]: === Iteration 24 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:16:01,505 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:16:01,505 INFO L82 PathProgramCache]: Analyzing trace with hash -1232145013, now seen corresponding path program 3 times [2021-05-06 08:16:01,505 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:16:01,505 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [992688310] [2021-05-06 08:16:01,505 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:16:01,515 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:16:01,515 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1475304864] [2021-05-06 08:16:01,515 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:16:01,572 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2021-05-06 08:16:01,572 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-06 08:16:01,573 INFO L263 TraceCheckSpWp]: Trace formula consists of 253 conjuncts, 12 conjunts are in the unsatisfiable core [2021-05-06 08:16:01,574 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:16:01,689 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:01,690 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:01,696 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:01,704 INFO L134 CoverageAnalysis]: Checked inductivity of 342 backedges. 64 proven. 10 refuted. 0 times theorem prover too weak. 268 trivial. 0 not checked. [2021-05-06 08:16:01,704 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:16:01,704 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [992688310] [2021-05-06 08:16:01,704 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:16:01,704 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1475304864] [2021-05-06 08:16:01,704 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1475304864] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:16:01,704 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:16:01,704 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2021-05-06 08:16:01,704 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [804546720] [2021-05-06 08:16:01,704 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2021-05-06 08:16:01,705 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:16:01,705 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-05-06 08:16:01,705 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2021-05-06 08:16:01,705 INFO L87 Difference]: Start difference. First operand 365 states and 501 transitions. Second operand has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) [2021-05-06 08:16:01,760 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:16:01,760 INFO L93 Difference]: Finished difference Result 369 states and 504 transitions. [2021-05-06 08:16:01,760 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-05-06 08:16:01,760 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) Word has length 105 [2021-05-06 08:16:01,761 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:16:01,762 INFO L225 Difference]: With dead ends: 369 [2021-05-06 08:16:01,762 INFO L226 Difference]: Without dead ends: 369 [2021-05-06 08:16:01,762 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 99 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 28.3ms TimeCoverageRelationStatistics Valid=23, Invalid=49, Unknown=0, NotChecked=0, Total=72 [2021-05-06 08:16:01,762 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 369 states. [2021-05-06 08:16:01,768 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 369 to 369. [2021-05-06 08:16:01,770 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 369 states, 228 states have (on average 1.2587719298245614) internal successors, (287), 235 states have internal predecessors, (287), 110 states have call successors, (110), 31 states have call predecessors, (110), 30 states have return successors, (107), 102 states have call predecessors, (107), 107 states have call successors, (107) [2021-05-06 08:16:01,771 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 369 states to 369 states and 504 transitions. [2021-05-06 08:16:01,771 INFO L78 Accepts]: Start accepts. Automaton has 369 states and 504 transitions. Word has length 105 [2021-05-06 08:16:01,772 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:16:01,772 INFO L480 AbstractCegarLoop]: Abstraction has 369 states and 504 transitions. [2021-05-06 08:16:01,772 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 7 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 6 states have internal predecessors, (25), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) [2021-05-06 08:16:01,772 INFO L276 IsEmpty]: Start isEmpty. Operand 369 states and 504 transitions. [2021-05-06 08:16:01,773 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2021-05-06 08:16:01,773 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:16:01,773 INFO L523 BasicCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 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] [2021-05-06 08:16:01,980 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable30,25 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:16:01,981 INFO L428 AbstractCegarLoop]: === Iteration 25 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:16:01,981 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:16:01,981 INFO L82 PathProgramCache]: Analyzing trace with hash -1212495288, now seen corresponding path program 2 times [2021-05-06 08:16:01,981 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:16:01,981 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1764143505] [2021-05-06 08:16:01,981 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:16:01,985 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:16:01,986 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1966005737] [2021-05-06 08:16:01,986 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:16:02,047 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-06 08:16:02,047 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-06 08:16:02,048 INFO L263 TraceCheckSpWp]: Trace formula consists of 319 conjuncts, 42 conjunts are in the unsatisfiable core [2021-05-06 08:16:02,050 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-06 08:16:02,231 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:02,232 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:02,239 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:02,240 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:02,247 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:02,248 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:02,300 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:02,301 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:02,312 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-06 08:16:02,323 INFO L134 CoverageAnalysis]: Checked inductivity of 336 backedges. 47 proven. 34 refuted. 0 times theorem prover too weak. 255 trivial. 0 not checked. [2021-05-06 08:16:02,323 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-06 08:16:02,323 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1764143505] [2021-05-06 08:16:02,323 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-06 08:16:02,323 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1966005737] [2021-05-06 08:16:02,323 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1966005737] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-06 08:16:02,323 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-06 08:16:02,323 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2021-05-06 08:16:02,323 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1654364550] [2021-05-06 08:16:02,323 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2021-05-06 08:16:02,323 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-06 08:16:02,323 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-05-06 08:16:02,324 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2021-05-06 08:16:02,324 INFO L87 Difference]: Start difference. First operand 369 states and 504 transitions. Second operand has 13 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 12 states have internal predecessors, (32), 7 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 5 states have call predecessors, (17), 6 states have call successors, (17) [2021-05-06 08:16:02,752 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-06 08:16:02,752 INFO L93 Difference]: Finished difference Result 401 states and 555 transitions. [2021-05-06 08:16:02,753 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-05-06 08:16:02,753 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 12 states have internal predecessors, (32), 7 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 5 states have call predecessors, (17), 6 states have call successors, (17) Word has length 107 [2021-05-06 08:16:02,753 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-06 08:16:02,754 INFO L225 Difference]: With dead ends: 401 [2021-05-06 08:16:02,754 INFO L226 Difference]: Without dead ends: 400 [2021-05-06 08:16:02,754 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 95 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38 ImplicationChecksByTransitivity, 166.5ms TimeCoverageRelationStatistics Valid=47, Invalid=225, Unknown=0, NotChecked=0, Total=272 [2021-05-06 08:16:02,755 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 400 states. [2021-05-06 08:16:02,760 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 400 to 398. [2021-05-06 08:16:02,761 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 398 states, 243 states have (on average 1.2674897119341564) internal successors, (308), 251 states have internal predecessors, (308), 123 states have call successors, (123), 32 states have call predecessors, (123), 31 states have return successors, (120), 114 states have call predecessors, (120), 120 states have call successors, (120) [2021-05-06 08:16:02,762 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 398 states to 398 states and 551 transitions. [2021-05-06 08:16:02,762 INFO L78 Accepts]: Start accepts. Automaton has 398 states and 551 transitions. Word has length 107 [2021-05-06 08:16:02,762 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-06 08:16:02,762 INFO L480 AbstractCegarLoop]: Abstraction has 398 states and 551 transitions. [2021-05-06 08:16:02,763 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 13 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 12 states have internal predecessors, (32), 7 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 5 states have call predecessors, (17), 6 states have call successors, (17) [2021-05-06 08:16:02,763 INFO L276 IsEmpty]: Start isEmpty. Operand 398 states and 551 transitions. [2021-05-06 08:16:02,763 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2021-05-06 08:16:02,763 INFO L515 BasicCegarLoop]: Found error trace [2021-05-06 08:16:02,763 INFO L523 BasicCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-06 08:16:02,964 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 26 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable31 [2021-05-06 08:16:02,964 INFO L428 AbstractCegarLoop]: === Iteration 26 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-06 08:16:02,964 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-06 08:16:02,964 INFO L82 PathProgramCache]: Analyzing trace with hash -1392800366, now seen corresponding path program 2 times [2021-05-06 08:16:02,964 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-06 08:16:02,965 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1976128251] [2021-05-06 08:16:02,965 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-06 08:16:02,973 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-06 08:16:02,973 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1784858009] [2021-05-06 08:16:02,973 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:16:03,044 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-06 08:16:03,045 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2021-05-06 08:16:03,045 INFO L223 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-05-06 08:16:03,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-05-06 08:16:03,078 INFO L223 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-05-06 08:16:03,157 INFO L173 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-05-06 08:16:03,158 INFO L624 BasicCegarLoop]: Counterexample might be feasible [2021-05-06 08:16:03,376 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable32,27 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-06 08:16:03,432 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.05 08:16:03 BasicIcfg [2021-05-06 08:16:03,432 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2021-05-06 08:16:03,433 INFO L168 Benchmark]: Toolchain (without parser) took 16180.58 ms. Allocated memory was 172.0 MB in the beginning and 249.6 MB in the end (delta: 77.6 MB). Free memory was 136.3 MB in the beginning and 119.8 MB in the end (delta: 16.6 MB). Peak memory consumption was 94.6 MB. Max. memory is 8.0 GB. [2021-05-06 08:16:03,433 INFO L168 Benchmark]: CDTParser took 0.09 ms. Allocated memory is still 172.0 MB. Free memory is still 152.9 MB. There was no memory consumed. Max. memory is 8.0 GB. [2021-05-06 08:16:03,433 INFO L168 Benchmark]: CACSL2BoogieTranslator took 205.04 ms. Allocated memory is still 172.0 MB. Free memory was 136.2 MB in the beginning and 155.0 MB in the end (delta: -18.9 MB). Peak memory consumption was 15.3 MB. Max. memory is 8.0 GB. [2021-05-06 08:16:03,433 INFO L168 Benchmark]: Boogie Preprocessor took 32.72 ms. Allocated memory is still 172.0 MB. Free memory was 155.0 MB in the beginning and 153.5 MB in the end (delta: 1.6 MB). Peak memory consumption was 1.0 MB. Max. memory is 8.0 GB. [2021-05-06 08:16:03,433 INFO L168 Benchmark]: RCFGBuilder took 376.17 ms. Allocated memory is still 172.0 MB. Free memory was 153.0 MB in the beginning and 136.3 MB in the end (delta: 16.8 MB). Peak memory consumption was 16.8 MB. Max. memory is 8.0 GB. [2021-05-06 08:16:03,433 INFO L168 Benchmark]: IcfgTransformer took 20.74 ms. Allocated memory is still 172.0 MB. Free memory was 136.3 MB in the beginning and 135.0 MB in the end (delta: 1.2 MB). Peak memory consumption was 1.0 MB. Max. memory is 8.0 GB. [2021-05-06 08:16:03,433 INFO L168 Benchmark]: TraceAbstraction took 15539.73 ms. Allocated memory was 172.0 MB in the beginning and 249.6 MB in the end (delta: 77.6 MB). Free memory was 134.6 MB in the beginning and 119.8 MB in the end (delta: 14.8 MB). Peak memory consumption was 92.9 MB. Max. memory is 8.0 GB. [2021-05-06 08:16:03,433 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.09 ms. Allocated memory is still 172.0 MB. Free memory is still 152.9 MB. There was no memory consumed. Max. memory is 8.0 GB. * CACSL2BoogieTranslator took 205.04 ms. Allocated memory is still 172.0 MB. Free memory was 136.2 MB in the beginning and 155.0 MB in the end (delta: -18.9 MB). Peak memory consumption was 15.3 MB. Max. memory is 8.0 GB. * Boogie Preprocessor took 32.72 ms. Allocated memory is still 172.0 MB. Free memory was 155.0 MB in the beginning and 153.5 MB in the end (delta: 1.6 MB). Peak memory consumption was 1.0 MB. Max. memory is 8.0 GB. * RCFGBuilder took 376.17 ms. Allocated memory is still 172.0 MB. Free memory was 153.0 MB in the beginning and 136.3 MB in the end (delta: 16.8 MB). Peak memory consumption was 16.8 MB. Max. memory is 8.0 GB. * IcfgTransformer took 20.74 ms. Allocated memory is still 172.0 MB. Free memory was 136.3 MB in the beginning and 135.0 MB in the end (delta: 1.2 MB). Peak memory consumption was 1.0 MB. Max. memory is 8.0 GB. * TraceAbstraction took 15539.73 ms. Allocated memory was 172.0 MB in the beginning and 249.6 MB in the end (delta: 77.6 MB). Free memory was 134.6 MB in the beginning and 119.8 MB in the end (delta: 14.8 MB). Peak memory consumption was 92.9 MB. Max. memory is 8.0 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - CounterExampleResult [Line: 13]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L18] int counter = 0; VAL [\old(counter)=13, counter=0] [L20] int x, y; [L21] long long a, b, p, q, r, s, c, k, xy, yy; [L22] x = __VERIFIER_nondet_int() [L23] y = __VERIFIER_nondet_int() [L24] CALL assume_abort_if_not(x >= 1) VAL [\old(cond)=1, \old(counter)=0, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=0] [L24] RET assume_abort_if_not(x >= 1) VAL [\old(counter)=0, counter=0, x=3, y=4] [L25] CALL assume_abort_if_not(y >= 1) VAL [\old(cond)=1, \old(counter)=0, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=0] [L25] RET assume_abort_if_not(y >= 1) VAL [\old(counter)=0, counter=0, x=3, y=4] [L27] a = x [L28] b = y [L29] p = 1 [L30] q = 0 [L31] r = 0 [L32] s = 1 [L33] c = 0 [L34] k = 0 [L35] xy = (long long) x * y [L36] yy = (long long) y * y VAL [\old(counter)=0, a=3, b=4, c=0, counter=0, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L37] CALL assume_abort_if_not(xy < 2147483647) VAL [\old(cond)=1, \old(counter)=0, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=0] [L37] RET assume_abort_if_not(xy < 2147483647) VAL [\old(counter)=0, a=3, b=4, c=0, counter=0, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L38] CALL assume_abort_if_not(yy < 2147483647) VAL [\old(cond)=1, \old(counter)=0, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=0] [L38] RET assume_abort_if_not(yy < 2147483647) VAL [\old(counter)=0, a=3, b=4, c=0, counter=0, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L40] EXPR counter++ VAL [\old(counter)=0, a=3, b=4, c=0, counter=1, counter++=0, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L40] COND TRUE counter++<5 [L41] COND FALSE !(!(b != 0)) [L43] c = a [L44] k = 0 VAL [\old(counter)=0, a=3, b=4, c=3, counter=1, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L46] EXPR counter++ VAL [\old(counter)=0, a=3, b=4, c=3, counter=2, counter++=1, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L46] COND TRUE counter++<5 [L47] CALL __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L47] RET __VERIFIER_assert(a == k * b + c) VAL [\old(counter)=0, a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L48] CALL __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L48] RET __VERIFIER_assert(a == y*r + x*p) VAL [\old(counter)=0, a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L49] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L49] RET __VERIFIER_assert(b == x * q + y * s) VAL [\old(counter)=0, a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L50] CALL __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L50] RET __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(counter)=0, a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L51] COND TRUE !(c >= b) VAL [\old(counter)=0, a=3, b=4, c=3, counter=2, k=0, p=1, q=0, r=0, s=1, x=3, xy=12, y=4, yy=16] [L57] a = b [L58] b = c [L60] long long temp; [L61] temp = p [L62] p = q [L63] q = temp - q * k [L64] temp = r [L65] r = s [L66] s = temp - s * k VAL [\old(counter)=0, a=4, b=3, c=3, counter=2, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L40] EXPR counter++ VAL [\old(counter)=0, a=4, b=3, c=3, counter=3, counter++=2, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L40] COND TRUE counter++<5 [L41] COND FALSE !(!(b != 0)) [L43] c = a [L44] k = 0 VAL [\old(counter)=0, a=4, b=3, c=4, counter=3, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L46] EXPR counter++ VAL [\old(counter)=0, a=4, b=3, c=4, counter=4, counter++=3, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L46] COND TRUE counter++<5 [L47] CALL __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L47] RET __VERIFIER_assert(a == k * b + c) VAL [\old(counter)=0, a=4, b=3, c=4, counter=4, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L48] CALL __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L48] RET __VERIFIER_assert(a == y*r + x*p) VAL [\old(counter)=0, a=4, b=3, c=4, counter=4, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L49] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L49] RET __VERIFIER_assert(b == x * q + y * s) VAL [\old(counter)=0, a=4, b=3, c=4, counter=4, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L50] CALL __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, \old(counter)=0, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=4] [L50] RET __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(counter)=0, a=4, b=3, c=4, counter=4, k=0, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L51] COND FALSE !(!(c >= b)) [L53] c = c - b [L54] k = k + 1 VAL [\old(counter)=0, a=4, b=3, c=1, counter=4, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L46] EXPR counter++ VAL [\old(counter)=0, a=4, b=3, c=1, counter=5, counter++=4, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L46] COND TRUE counter++<5 [L47] CALL __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, \old(counter)=0, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=5] [L47] RET __VERIFIER_assert(a == k * b + c) VAL [\old(counter)=0, a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L48] CALL __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, \old(counter)=0, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=5] [L48] RET __VERIFIER_assert(a == y*r + x*p) VAL [\old(counter)=0, a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L49] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, \old(counter)=0, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=5] [L49] RET __VERIFIER_assert(b == x * q + y * s) VAL [\old(counter)=0, a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L50] CALL __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, \old(counter)=0, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=5] [L50] RET __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(counter)=0, a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L51] COND TRUE !(c >= b) VAL [\old(counter)=0, a=4, b=3, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=3, xy=12, y=4, yy=16] [L57] a = b [L58] b = c [L60] long long temp; [L61] temp = p [L62] p = q [L63] q = temp - q * k [L64] temp = r [L65] r = s [L66] s = temp - s * k VAL [\old(counter)=0, a=3, b=1, c=1, counter=5, k=1, p=1, q=-1, r=0, s=1, temp=1, x=3, xy=12, y=4, yy=16] [L40] EXPR counter++ VAL [\old(counter)=0, a=3, b=1, c=1, counter=6, counter++=5, k=1, p=1, q=-1, r=0, s=1, temp=1, x=3, xy=12, y=4, yy=16] [L40] COND FALSE !(counter++<5) [L70] CALL __VERIFIER_assert(q*x + s*y == 0) VAL [\old(cond)=0, \old(counter)=0, counter=6] [L11] COND TRUE !(cond) VAL [\old(cond)=0, \old(counter)=0, cond=0, counter=6] [L13] reach_error() VAL [\old(cond)=0, \old(counter)=0, cond=0, counter=6] - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 39 locations, 1 error locations. Started 1 CEGAR loops. VerificationResult: UNSAFE, OverallTime: 15441.1ms, OverallIterations: 26, TraceHistogramMax: 13, EmptinessCheckTime: 30.3ms, AutomataDifference: 3798.2ms, DeadEndRemovalTime: 0.0ms, HoareAnnotationTime: 0.0ms, InitialAbstractionConstructionTime: 7.7ms, PartialOrderReductionTime: 0.0ms, HoareTripleCheckerStatistics: 1194 SDtfs, 664 SDslu, 4702 SDs, 0 SdLazy, 3308 SolverSat, 467 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 2257.5ms Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1708 GetRequests, 1491 SyntacticMatches, 5 SemanticMatches, 212 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 270 ImplicationChecksByTransitivity, 1815.1ms Time, 0.0ms BasicInterpolantAutomatonTime, BiggestAbstraction: size=398occurred in iteration=25, InterpolantAutomatonStates: 213, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0ms DumpTime, AutomataMinimizationStatistics: 176.1ms AutomataMinimizationTime, 25 MinimizatonAttempts, 173 StatesRemovedByMinimization, 17 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 216.6ms SsaConstructionTime, 718.5ms SatisfiabilityAnalysisTime, 3821.8ms InterpolantComputationTime, 1780 NumberOfCodeBlocks, 1730 NumberOfCodeBlocksAsserted, 37 NumberOfCheckSat, 1645 ConstructedInterpolants, 0 QuantifiedInterpolants, 6754 SizeOfPredicates, 98 NumberOfNonLiveVariables, 5867 ConjunctsInSsa, 461 ConjunctsInUnsatCore, 25 InterpolantComputations, 4 PerfectInterpolantSequences, 2348/2813 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! Received shutdown request...