/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/cohencu-ll_unwindbound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.1-dev-c225d54 [2021-05-02 19:31:37,419 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-05-02 19:31:37,420 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-05-02 19:31:37,442 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-05-02 19:31:37,442 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-05-02 19:31:37,443 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-05-02 19:31:37,444 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-05-02 19:31:37,460 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-05-02 19:31:37,462 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-05-02 19:31:37,466 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-05-02 19:31:37,466 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-05-02 19:31:37,467 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-05-02 19:31:37,467 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-05-02 19:31:37,469 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-05-02 19:31:37,470 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-05-02 19:31:37,471 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-05-02 19:31:37,472 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-05-02 19:31:37,472 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-05-02 19:31:37,475 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-05-02 19:31:37,479 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-05-02 19:31:37,480 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-05-02 19:31:37,481 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-05-02 19:31:37,482 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-05-02 19:31:37,483 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-05-02 19:31:37,485 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-05-02 19:31:37,485 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-05-02 19:31:37,485 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-05-02 19:31:37,489 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-05-02 19:31:37,491 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-05-02 19:31:37,491 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-05-02 19:31:37,492 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-05-02 19:31:37,492 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-05-02 19:31:37,493 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-05-02 19:31:37,494 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-05-02 19:31:37,494 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-05-02 19:31:37,494 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-05-02 19:31:37,495 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-05-02 19:31:37,495 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-05-02 19:31:37,495 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-05-02 19:31:37,495 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-05-02 19:31:37,496 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-05-02 19:31:37,497 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2021-05-02 19:31:37,510 INFO L113 SettingsManager]: Loading preferences was successful [2021-05-02 19:31:37,510 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-05-02 19:31:37,511 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-05-02 19:31:37,511 INFO L138 SettingsManager]: * sizeof long=4 [2021-05-02 19:31:37,511 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-05-02 19:31:37,511 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-05-02 19:31:37,511 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-05-02 19:31:37,511 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-05-02 19:31:37,511 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-05-02 19:31:37,511 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-05-02 19:31:37,512 INFO L138 SettingsManager]: * sizeof long double=12 [2021-05-02 19:31:37,512 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-05-02 19:31:37,512 INFO L138 SettingsManager]: * Use constant arrays=true [2021-05-02 19:31:37,512 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-05-02 19:31:37,512 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-05-02 19:31:37,512 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-05-02 19:31:37,512 INFO L138 SettingsManager]: * To the following directory=./dump/ [2021-05-02 19:31:37,512 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-05-02 19:31:37,512 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-05-02 19:31:37,512 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-05-02 19:31:37,512 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-05-02 19:31:37,513 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2021-05-02 19:31:37,513 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-02 19:31:37,795 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-05-02 19:31:37,819 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-05-02 19:31:37,821 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-05-02 19:31:37,822 INFO L271 PluginConnector]: Initializing CDTParser... [2021-05-02 19:31:37,822 INFO L275 PluginConnector]: CDTParser initialized [2021-05-02 19:31:37,823 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound5.c [2021-05-02 19:31:37,879 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/977a49dd3/cd98c74be5464bcba457ac96a781da67/FLAG8a1b095fd [2021-05-02 19:31:38,258 INFO L306 CDTParser]: Found 1 translation units. [2021-05-02 19:31:38,259 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound5.c [2021-05-02 19:31:38,265 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/977a49dd3/cd98c74be5464bcba457ac96a781da67/FLAG8a1b095fd [2021-05-02 19:31:38,681 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/977a49dd3/cd98c74be5464bcba457ac96a781da67 [2021-05-02 19:31:38,686 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-05-02 19:31:38,688 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2021-05-02 19:31:38,690 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-05-02 19:31:38,691 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-05-02 19:31:38,693 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-05-02 19:31:38,694 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.05 07:31:38" (1/1) ... [2021-05-02 19:31:38,694 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@649c2133 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 07:31:38, skipping insertion in model container [2021-05-02 19:31:38,695 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.05 07:31:38" (1/1) ... [2021-05-02 19:31:38,700 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-05-02 19:31:38,712 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-05-02 19:31:38,812 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/cohencu-ll_unwindbound5.c[596,609] [2021-05-02 19:31:38,825 INFO L206 PostProcessor]: Analyzing one entry point: main [2021-05-02 19:31:38,835 INFO L203 MainTranslator]: Completed pre-run [2021-05-02 19:31:38,846 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/cohencu-ll_unwindbound5.c[596,609] [2021-05-02 19:31:38,874 INFO L206 PostProcessor]: Analyzing one entry point: main [2021-05-02 19:31:38,883 INFO L208 MainTranslator]: Completed translation [2021-05-02 19:31:38,884 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 07:31:38 WrapperNode [2021-05-02 19:31:38,884 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-05-02 19:31:38,884 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-05-02 19:31:38,884 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-05-02 19:31:38,885 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-05-02 19:31:38,923 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 07:31:38" (1/1) ... [2021-05-02 19:31:38,923 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 07:31:38" (1/1) ... [2021-05-02 19:31:38,927 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 07:31:38" (1/1) ... [2021-05-02 19:31:38,927 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 07:31:38" (1/1) ... [2021-05-02 19:31:38,931 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 07:31:38" (1/1) ... [2021-05-02 19:31:38,934 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 07:31:38" (1/1) ... [2021-05-02 19:31:38,938 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 07:31:38" (1/1) ... [2021-05-02 19:31:38,939 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-05-02 19:31:38,940 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-05-02 19:31:38,940 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-05-02 19:31:38,940 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-05-02 19:31:38,940 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 07:31:38" (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-02 19:31:39,011 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2021-05-02 19:31:39,011 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-05-02 19:31:39,011 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2021-05-02 19:31:39,012 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2021-05-02 19:31:39,012 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-05-02 19:31:39,012 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2021-05-02 19:31:39,012 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2021-05-02 19:31:39,012 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2021-05-02 19:31:39,012 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2021-05-02 19:31:39,012 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-05-02 19:31:39,013 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_unsigned_short [2021-05-02 19:31:39,013 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2021-05-02 19:31:39,013 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-05-02 19:31:39,013 INFO L130 BoogieDeclarations]: Found specification of procedure main [2021-05-02 19:31:39,013 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2021-05-02 19:31:39,014 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-05-02 19:31:39,014 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-05-02 19:31:39,014 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2021-05-02 19:31:39,014 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2021-05-02 19:31:39,014 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-05-02 19:31:39,262 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-05-02 19:31:39,262 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2021-05-02 19:31:39,263 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.05 07:31:39 BoogieIcfgContainer [2021-05-02 19:31:39,263 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-05-02 19:31:39,264 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2021-05-02 19:31:39,264 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2021-05-02 19:31:39,265 INFO L275 PluginConnector]: IcfgTransformer initialized [2021-05-02 19:31:39,266 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.05 07:31:39" (1/1) ... [2021-05-02 19:31:39,280 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 02.05 07:31:39 BasicIcfg [2021-05-02 19:31:39,283 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2021-05-02 19:31:39,284 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-05-02 19:31:39,284 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-05-02 19:31:39,286 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-05-02 19:31:39,286 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.05 07:31:38" (1/4) ... [2021-05-02 19:31:39,287 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@65c43b6b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.05 07:31:39, skipping insertion in model container [2021-05-02 19:31:39,287 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 07:31:38" (2/4) ... [2021-05-02 19:31:39,287 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@65c43b6b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.05 07:31:39, skipping insertion in model container [2021-05-02 19:31:39,287 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.05 07:31:39" (3/4) ... [2021-05-02 19:31:39,287 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@65c43b6b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 02.05 07:31:39, skipping insertion in model container [2021-05-02 19:31:39,287 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 02.05 07:31:39" (4/4) ... [2021-05-02 19:31:39,288 INFO L111 eAbstractionObserver]: Analyzing ICFG cohencu-ll_unwindbound5.cJordan [2021-05-02 19:31:39,292 INFO L149 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2021-05-02 19:31:39,295 INFO L161 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2021-05-02 19:31:39,307 INFO L253 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-05-02 19:31:39,319 INFO L376 AbstractCegarLoop]: Interprodecural is true [2021-05-02 19:31:39,319 INFO L377 AbstractCegarLoop]: Hoare is false [2021-05-02 19:31:39,319 INFO L378 AbstractCegarLoop]: Compute interpolants for ForwardPredicates [2021-05-02 19:31:39,319 INFO L379 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2021-05-02 19:31:39,320 INFO L380 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2021-05-02 19:31:39,320 INFO L381 AbstractCegarLoop]: Difference is false [2021-05-02 19:31:39,320 INFO L382 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2021-05-02 19:31:39,320 INFO L386 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2021-05-02 19:31:39,328 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2021-05-02 19:31:39,333 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2021-05-02 19:31:39,333 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:39,334 INFO L523 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 19:31:39,334 INFO L428 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:39,337 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:39,337 INFO L82 PathProgramCache]: Analyzing trace with hash 1427487266, now seen corresponding path program 1 times [2021-05-02 19:31:39,343 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:39,343 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1475311851] [2021-05-02 19:31:39,344 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:39,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 19:31:39,512 INFO L375 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2021-05-02 19:31:39,524 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 19:31:39,543 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-05-02 19:31:39,543 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 19:31:39,543 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1475311851] [2021-05-02 19:31:39,544 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1475311851] provided 1 perfect and 0 imperfect interpolant sequences [2021-05-02 19:31:39,544 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-05-02 19:31:39,544 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-05-02 19:31:39,544 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2003964880] [2021-05-02 19:31:39,547 INFO L460 AbstractCegarLoop]: Interpolant automaton has 3 states [2021-05-02 19:31:39,548 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 19:31:39,556 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-05-02 19:31:39,556 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-05-02 19:31:39,558 INFO L87 Difference]: Start difference. First operand has 31 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-05-02 19:31:39,665 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 19:31:39,665 INFO L93 Difference]: Finished difference Result 32 states and 43 transitions. [2021-05-02 19:31:39,665 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-05-02 19:31:39,666 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2021-05-02 19:31:39,667 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 19:31:39,671 INFO L225 Difference]: With dead ends: 32 [2021-05-02 19:31:39,671 INFO L226 Difference]: Without dead ends: 27 [2021-05-02 19:31:39,672 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 62.7ms TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-05-02 19:31:39,682 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2021-05-02 19:31:39,693 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2021-05-02 19:31:39,694 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2021-05-02 19:31:39,695 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 37 transitions. [2021-05-02 19:31:39,695 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 37 transitions. Word has length 11 [2021-05-02 19:31:39,696 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 19:31:39,696 INFO L480 AbstractCegarLoop]: Abstraction has 26 states and 37 transitions. [2021-05-02 19:31:39,696 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-05-02 19:31:39,696 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 37 transitions. [2021-05-02 19:31:39,696 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2021-05-02 19:31:39,696 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:39,696 INFO L523 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 19:31:39,697 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-05-02 19:31:39,697 INFO L428 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:39,697 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:39,697 INFO L82 PathProgramCache]: Analyzing trace with hash 1331862890, now seen corresponding path program 1 times [2021-05-02 19:31:39,697 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:39,698 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1685785072] [2021-05-02 19:31:39,698 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:39,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 19:31:39,769 INFO L375 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2021-05-02 19:31:39,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 19:31:39,795 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-05-02 19:31:39,796 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 19:31:39,796 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1685785072] [2021-05-02 19:31:39,796 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1685785072] provided 1 perfect and 0 imperfect interpolant sequences [2021-05-02 19:31:39,797 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-05-02 19:31:39,797 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-05-02 19:31:39,797 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [894179066] [2021-05-02 19:31:39,798 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2021-05-02 19:31:39,798 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 19:31:39,800 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-05-02 19:31:39,800 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-05-02 19:31:39,801 INFO L87 Difference]: Start difference. First operand 26 states and 37 transitions. Second operand has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-05-02 19:31:39,962 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 19:31:39,962 INFO L93 Difference]: Finished difference Result 28 states and 39 transitions. [2021-05-02 19:31:39,963 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-05-02 19:31:39,963 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2021-05-02 19:31:39,963 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 19:31:39,964 INFO L225 Difference]: With dead ends: 28 [2021-05-02 19:31:39,964 INFO L226 Difference]: Without dead ends: 28 [2021-05-02 19:31:39,965 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 53.8ms TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2021-05-02 19:31:39,965 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2021-05-02 19:31:39,974 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2021-05-02 19:31:39,974 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2021-05-02 19:31:39,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 39 transitions. [2021-05-02 19:31:39,977 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 39 transitions. Word has length 12 [2021-05-02 19:31:39,977 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 19:31:39,978 INFO L480 AbstractCegarLoop]: Abstraction has 28 states and 39 transitions. [2021-05-02 19:31:39,978 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-05-02 19:31:39,978 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 39 transitions. [2021-05-02 19:31:39,979 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2021-05-02 19:31:39,979 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:39,979 INFO L523 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 19:31:39,980 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2021-05-02 19:31:39,980 INFO L428 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:39,981 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:39,981 INFO L82 PathProgramCache]: Analyzing trace with hash 1332935366, now seen corresponding path program 1 times [2021-05-02 19:31:39,983 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:39,984 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [775082204] [2021-05-02 19:31:39,985 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:40,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 19:31:40,079 INFO L375 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2021-05-02 19:31:40,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 19:31:40,085 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-05-02 19:31:40,085 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 19:31:40,085 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [775082204] [2021-05-02 19:31:40,085 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [775082204] provided 1 perfect and 0 imperfect interpolant sequences [2021-05-02 19:31:40,086 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-05-02 19:31:40,086 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2021-05-02 19:31:40,086 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [458132811] [2021-05-02 19:31:40,086 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2021-05-02 19:31:40,086 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 19:31:40,086 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-05-02 19:31:40,086 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2021-05-02 19:31:40,087 INFO L87 Difference]: Start difference. First operand 28 states and 39 transitions. Second operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-05-02 19:31:40,264 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 19:31:40,264 INFO L93 Difference]: Finished difference Result 32 states and 42 transitions. [2021-05-02 19:31:40,265 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-05-02 19:31:40,265 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2021-05-02 19:31:40,265 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 19:31:40,265 INFO L225 Difference]: With dead ends: 32 [2021-05-02 19:31:40,266 INFO L226 Difference]: Without dead ends: 32 [2021-05-02 19:31:40,266 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 131.3ms TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2021-05-02 19:31:40,266 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2021-05-02 19:31:40,269 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2021-05-02 19:31:40,269 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2021-05-02 19:31:40,270 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 42 transitions. [2021-05-02 19:31:40,270 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 42 transitions. Word has length 12 [2021-05-02 19:31:40,270 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 19:31:40,270 INFO L480 AbstractCegarLoop]: Abstraction has 32 states and 42 transitions. [2021-05-02 19:31:40,270 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-05-02 19:31:40,271 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2021-05-02 19:31:40,271 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2021-05-02 19:31:40,271 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:40,271 INFO L523 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 19:31:40,271 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2021-05-02 19:31:40,271 INFO L428 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:40,271 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:40,272 INFO L82 PathProgramCache]: Analyzing trace with hash -1273314772, now seen corresponding path program 1 times [2021-05-02 19:31:40,272 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:40,272 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1966553597] [2021-05-02 19:31:40,272 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:40,279 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 19:31:40,279 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [932068641] [2021-05-02 19:31:40,280 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-02 19:31:40,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 19:31:40,333 INFO L263 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 17 conjunts are in the unsatisfiable core [2021-05-02 19:31:40,336 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 19:31:40,433 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-05-02 19:31:40,434 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 19:31:40,434 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1966553597] [2021-05-02 19:31:40,434 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 19:31:40,434 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [932068641] [2021-05-02 19:31:40,434 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [932068641] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 19:31:40,434 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 19:31:40,434 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2021-05-02 19:31:40,434 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [338939771] [2021-05-02 19:31:40,435 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2021-05-02 19:31:40,435 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 19:31:40,435 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-05-02 19:31:40,435 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2021-05-02 19:31:40,435 INFO L87 Difference]: Start difference. First operand 32 states and 42 transitions. Second operand has 8 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-05-02 19:31:40,666 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 19:31:40,667 INFO L93 Difference]: Finished difference Result 52 states and 71 transitions. [2021-05-02 19:31:40,667 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-05-02 19:31:40,667 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2021-05-02 19:31:40,667 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 19:31:40,668 INFO L225 Difference]: With dead ends: 52 [2021-05-02 19:31:40,668 INFO L226 Difference]: Without dead ends: 52 [2021-05-02 19:31:40,668 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 41.6ms TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2021-05-02 19:31:40,668 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2021-05-02 19:31:40,672 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 51. [2021-05-02 19:31:40,672 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 23 states have call successors, (23), 6 states have call predecessors, (23), 5 states have return successors, (21), 20 states have call predecessors, (21), 21 states have call successors, (21) [2021-05-02 19:31:40,673 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 70 transitions. [2021-05-02 19:31:40,673 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 70 transitions. Word has length 17 [2021-05-02 19:31:40,673 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 19:31:40,673 INFO L480 AbstractCegarLoop]: Abstraction has 51 states and 70 transitions. [2021-05-02 19:31:40,673 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 8 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-05-02 19:31:40,674 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 70 transitions. [2021-05-02 19:31:40,674 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2021-05-02 19:31:40,674 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:40,674 INFO L523 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 19:31:40,884 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 19:31:40,885 INFO L428 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:40,885 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:40,886 INFO L82 PathProgramCache]: Analyzing trace with hash 1649805282, now seen corresponding path program 1 times [2021-05-02 19:31:40,886 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:40,886 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1962719563] [2021-05-02 19:31:40,886 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:40,892 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 19:31:40,893 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [204514060] [2021-05-02 19:31:40,893 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-02 19:31:40,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 19:31:40,933 INFO L263 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 17 conjunts are in the unsatisfiable core [2021-05-02 19:31:40,935 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 19:31:41,002 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-05-02 19:31:41,002 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 19:31:41,002 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1962719563] [2021-05-02 19:31:41,002 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 19:31:41,002 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [204514060] [2021-05-02 19:31:41,003 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [204514060] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 19:31:41,003 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 19:31:41,003 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2021-05-02 19:31:41,003 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1638845663] [2021-05-02 19:31:41,003 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2021-05-02 19:31:41,003 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 19:31:41,003 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-05-02 19:31:41,004 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2021-05-02 19:31:41,004 INFO L87 Difference]: Start difference. First operand 51 states and 70 transitions. Second operand has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2021-05-02 19:31:41,241 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 19:31:41,241 INFO L93 Difference]: Finished difference Result 56 states and 74 transitions. [2021-05-02 19:31:41,242 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-05-02 19:31:41,243 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Word has length 22 [2021-05-02 19:31:41,243 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 19:31:41,245 INFO L225 Difference]: With dead ends: 56 [2021-05-02 19:31:41,245 INFO L226 Difference]: Without dead ends: 56 [2021-05-02 19:31:41,245 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 39.1ms TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2021-05-02 19:31:41,246 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2021-05-02 19:31:41,255 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2021-05-02 19:31:41,256 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 25 states have (on average 1.16) internal successors, (29), 27 states have internal predecessors, (29), 23 states have call successors, (23), 7 states have call predecessors, (23), 6 states have return successors, (21), 20 states have call predecessors, (21), 21 states have call successors, (21) [2021-05-02 19:31:41,257 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 73 transitions. [2021-05-02 19:31:41,257 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 73 transitions. Word has length 22 [2021-05-02 19:31:41,257 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 19:31:41,257 INFO L480 AbstractCegarLoop]: Abstraction has 55 states and 73 transitions. [2021-05-02 19:31:41,257 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2021-05-02 19:31:41,258 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 73 transitions. [2021-05-02 19:31:41,258 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2021-05-02 19:31:41,259 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:41,259 INFO L523 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 19:31:41,460 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 19:31:41,461 INFO L428 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:41,461 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:41,461 INFO L82 PathProgramCache]: Analyzing trace with hash 1442767915, now seen corresponding path program 1 times [2021-05-02 19:31:41,461 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:41,462 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [328442569] [2021-05-02 19:31:41,462 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:41,467 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 19:31:41,468 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1689479924] [2021-05-02 19:31:41,468 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-02 19:31:41,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 19:31:41,512 INFO L263 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 19 conjunts are in the unsatisfiable core [2021-05-02 19:31:41,513 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 19:31:41,607 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2021-05-02 19:31:41,608 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 19:31:41,608 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [328442569] [2021-05-02 19:31:41,608 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 19:31:41,608 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1689479924] [2021-05-02 19:31:41,608 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1689479924] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 19:31:41,608 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 19:31:41,608 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2021-05-02 19:31:41,608 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1873526273] [2021-05-02 19:31:41,608 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2021-05-02 19:31:41,608 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 19:31:41,609 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-05-02 19:31:41,609 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2021-05-02 19:31:41,609 INFO L87 Difference]: Start difference. First operand 55 states and 73 transitions. Second operand has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2021-05-02 19:31:41,783 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 19:31:41,784 INFO L93 Difference]: Finished difference Result 60 states and 77 transitions. [2021-05-02 19:31:41,784 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-05-02 19:31:41,784 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Word has length 27 [2021-05-02 19:31:41,784 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 19:31:41,785 INFO L225 Difference]: With dead ends: 60 [2021-05-02 19:31:41,785 INFO L226 Difference]: Without dead ends: 54 [2021-05-02 19:31:41,786 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 41.4ms TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2021-05-02 19:31:41,786 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2021-05-02 19:31:41,789 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2021-05-02 19:31:41,789 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 28 states have (on average 1.1071428571428572) internal successors, (31), 29 states have internal predecessors, (31), 18 states have call successors, (18), 8 states have call predecessors, (18), 7 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2021-05-02 19:31:41,790 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 65 transitions. [2021-05-02 19:31:41,790 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 65 transitions. Word has length 27 [2021-05-02 19:31:41,790 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 19:31:41,790 INFO L480 AbstractCegarLoop]: Abstraction has 54 states and 65 transitions. [2021-05-02 19:31:41,790 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2021-05-02 19:31:41,790 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 65 transitions. [2021-05-02 19:31:41,791 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2021-05-02 19:31:41,791 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:41,791 INFO L523 BasicCegarLoop]: trace histogram [7, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 19:31:41,991 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 19:31:41,992 INFO L428 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:41,992 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:41,992 INFO L82 PathProgramCache]: Analyzing trace with hash -1251454759, now seen corresponding path program 1 times [2021-05-02 19:31:41,992 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:41,992 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [884882887] [2021-05-02 19:31:41,993 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:41,999 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 19:31:41,999 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1359141052] [2021-05-02 19:31:42,000 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-02 19:31:42,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 19:31:42,057 INFO L263 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 7 conjunts are in the unsatisfiable core [2021-05-02 19:31:42,065 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 19:31:42,080 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:42,083 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:42,085 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:42,096 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:42,098 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:42,099 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:42,149 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:42,152 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:42,169 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 30 proven. 2 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2021-05-02 19:31:42,169 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 19:31:42,169 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [884882887] [2021-05-02 19:31:42,169 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 19:31:42,169 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1359141052] [2021-05-02 19:31:42,169 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1359141052] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 19:31:42,169 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 19:31:42,169 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5] total 5 [2021-05-02 19:31:42,170 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1891537595] [2021-05-02 19:31:42,170 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2021-05-02 19:31:42,170 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 19:31:42,170 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-05-02 19:31:42,170 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2021-05-02 19:31:42,170 INFO L87 Difference]: Start difference. First operand 54 states and 65 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 4 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2021-05-02 19:31:42,203 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 19:31:42,203 INFO L93 Difference]: Finished difference Result 56 states and 67 transitions. [2021-05-02 19:31:42,204 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-05-02 19:31:42,204 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 4 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 45 [2021-05-02 19:31:42,204 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 19:31:42,205 INFO L225 Difference]: With dead ends: 56 [2021-05-02 19:31:42,205 INFO L226 Difference]: Without dead ends: 56 [2021-05-02 19:31:42,205 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 12.7ms TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2021-05-02 19:31:42,205 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2021-05-02 19:31:42,207 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2021-05-02 19:31:42,208 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 30 states have (on average 1.1) internal successors, (33), 31 states have internal predecessors, (33), 18 states have call successors, (18), 8 states have call predecessors, (18), 7 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2021-05-02 19:31:42,208 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 67 transitions. [2021-05-02 19:31:42,208 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 67 transitions. Word has length 45 [2021-05-02 19:31:42,209 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 19:31:42,209 INFO L480 AbstractCegarLoop]: Abstraction has 56 states and 67 transitions. [2021-05-02 19:31:42,209 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 4 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2021-05-02 19:31:42,209 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 67 transitions. [2021-05-02 19:31:42,209 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2021-05-02 19:31:42,210 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:42,210 INFO L523 BasicCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 19:31:42,424 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 19:31:42,425 INFO L428 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:42,425 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:42,425 INFO L82 PathProgramCache]: Analyzing trace with hash -1899744846, now seen corresponding path program 1 times [2021-05-02 19:31:42,425 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:42,425 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [907497739] [2021-05-02 19:31:42,426 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:42,431 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 19:31:42,432 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2027105063] [2021-05-02 19:31:42,432 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-02 19:31:42,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 19:31:42,472 INFO L263 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 23 conjunts are in the unsatisfiable core [2021-05-02 19:31:42,474 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 19:31:42,613 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 26 proven. 5 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2021-05-02 19:31:42,613 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 19:31:42,614 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [907497739] [2021-05-02 19:31:42,614 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 19:31:42,614 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2027105063] [2021-05-02 19:31:42,614 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2027105063] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 19:31:42,614 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 19:31:42,614 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2021-05-02 19:31:42,614 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1176114026] [2021-05-02 19:31:42,616 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2021-05-02 19:31:42,616 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 19:31:42,616 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-05-02 19:31:42,616 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2021-05-02 19:31:42,617 INFO L87 Difference]: Start difference. First operand 56 states and 67 transitions. Second operand has 9 states, 8 states have (on average 2.125) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2021-05-02 19:31:42,811 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 19:31:42,811 INFO L93 Difference]: Finished difference Result 76 states and 96 transitions. [2021-05-02 19:31:42,812 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-05-02 19:31:42,812 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 45 [2021-05-02 19:31:42,812 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 19:31:42,813 INFO L225 Difference]: With dead ends: 76 [2021-05-02 19:31:42,813 INFO L226 Difference]: Without dead ends: 76 [2021-05-02 19:31:42,813 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 64.8ms TimeCoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2021-05-02 19:31:42,814 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2021-05-02 19:31:42,817 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 75. [2021-05-02 19:31:42,817 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 37 states have (on average 1.1081081081081081) internal successors, (41), 39 states have internal predecessors, (41), 28 states have call successors, (28), 10 states have call predecessors, (28), 9 states have return successors, (26), 25 states have call predecessors, (26), 26 states have call successors, (26) [2021-05-02 19:31:42,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 95 transitions. [2021-05-02 19:31:42,818 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 95 transitions. Word has length 45 [2021-05-02 19:31:42,818 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 19:31:42,818 INFO L480 AbstractCegarLoop]: Abstraction has 75 states and 95 transitions. [2021-05-02 19:31:42,818 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2021-05-02 19:31:42,818 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 95 transitions. [2021-05-02 19:31:42,819 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2021-05-02 19:31:42,819 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:42,819 INFO L523 BasicCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 19:31:43,025 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 19:31:43,025 INFO L428 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:43,025 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:43,025 INFO L82 PathProgramCache]: Analyzing trace with hash 400776220, now seen corresponding path program 2 times [2021-05-02 19:31:43,025 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:43,026 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1123784425] [2021-05-02 19:31:43,026 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:43,031 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 19:31:43,031 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1376156648] [2021-05-02 19:31:43,031 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 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-02 19:31:43,076 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-02 19:31:43,076 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-02 19:31:43,077 INFO L263 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 25 conjunts are in the unsatisfiable core [2021-05-02 19:31:43,079 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 19:31:43,192 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 28 proven. 9 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2021-05-02 19:31:43,192 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 19:31:43,193 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1123784425] [2021-05-02 19:31:43,193 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 19:31:43,193 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1376156648] [2021-05-02 19:31:43,193 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1376156648] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 19:31:43,193 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 19:31:43,193 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2021-05-02 19:31:43,193 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2128070079] [2021-05-02 19:31:43,193 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2021-05-02 19:31:43,193 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 19:31:43,194 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-05-02 19:31:43,194 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2021-05-02 19:31:43,194 INFO L87 Difference]: Start difference. First operand 75 states and 95 transitions. Second operand has 9 states, 8 states have (on average 2.125) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2021-05-02 19:31:43,374 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 19:31:43,374 INFO L93 Difference]: Finished difference Result 80 states and 99 transitions. [2021-05-02 19:31:43,378 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-05-02 19:31:43,378 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 50 [2021-05-02 19:31:43,378 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 19:31:43,379 INFO L225 Difference]: With dead ends: 80 [2021-05-02 19:31:43,379 INFO L226 Difference]: Without dead ends: 78 [2021-05-02 19:31:43,379 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 44.8ms TimeCoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2021-05-02 19:31:43,379 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2021-05-02 19:31:43,383 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 78. [2021-05-02 19:31:43,383 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 40 states have (on average 1.1) internal successors, (44), 42 states have internal predecessors, (44), 27 states have call successors, (27), 11 states have call predecessors, (27), 10 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2021-05-02 19:31:43,384 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 95 transitions. [2021-05-02 19:31:43,384 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 95 transitions. Word has length 50 [2021-05-02 19:31:43,384 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 19:31:43,384 INFO L480 AbstractCegarLoop]: Abstraction has 78 states and 95 transitions. [2021-05-02 19:31:43,384 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 9 states, 8 states have (on average 2.125) internal successors, (17), 7 states have internal predecessors, (17), 4 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2021-05-02 19:31:43,384 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 95 transitions. [2021-05-02 19:31:43,385 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2021-05-02 19:31:43,386 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:43,386 INFO L523 BasicCegarLoop]: trace histogram [12, 11, 11, 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] [2021-05-02 19:31:43,600 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 19:31:43,601 INFO L428 AbstractCegarLoop]: === Iteration 10 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:43,601 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:43,601 INFO L82 PathProgramCache]: Analyzing trace with hash 999510626, now seen corresponding path program 1 times [2021-05-02 19:31:43,602 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:43,602 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [687570316] [2021-05-02 19:31:43,602 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:43,607 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 19:31:43,607 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1566149597] [2021-05-02 19:31:43,607 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-02 19:31:43,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 19:31:43,659 INFO L263 TraceCheckSpWp]: Trace formula consists of 219 conjuncts, 31 conjunts are in the unsatisfiable core [2021-05-02 19:31:43,666 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 19:31:43,681 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,683 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,771 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,778 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,781 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,787 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,807 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,816 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,821 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,822 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,843 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,846 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,852 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,854 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,875 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,877 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,882 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,884 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,903 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,905 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,910 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,911 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,974 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,976 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,989 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:43,991 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,003 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,004 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,016 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,018 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,028 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,030 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,057 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,058 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,087 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,088 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,096 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,116 INFO L134 CoverageAnalysis]: Checked inductivity of 250 backedges. 51 proven. 9 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2021-05-02 19:31:44,117 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 19:31:44,117 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [687570316] [2021-05-02 19:31:44,117 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 19:31:44,117 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1566149597] [2021-05-02 19:31:44,117 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1566149597] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 19:31:44,117 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 19:31:44,117 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2021-05-02 19:31:44,117 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [612456809] [2021-05-02 19:31:44,118 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states [2021-05-02 19:31:44,118 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 19:31:44,119 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-05-02 19:31:44,119 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2021-05-02 19:31:44,119 INFO L87 Difference]: Start difference. First operand 78 states and 95 transitions. Second operand has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2021-05-02 19:31:44,311 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 19:31:44,312 INFO L93 Difference]: Finished difference Result 82 states and 98 transitions. [2021-05-02 19:31:44,312 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-05-02 19:31:44,312 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 71 [2021-05-02 19:31:44,312 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 19:31:44,313 INFO L225 Difference]: With dead ends: 82 [2021-05-02 19:31:44,313 INFO L226 Difference]: Without dead ends: 82 [2021-05-02 19:31:44,313 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 62 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 144.8ms TimeCoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2021-05-02 19:31:44,313 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2021-05-02 19:31:44,317 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 82. [2021-05-02 19:31:44,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 43 states have (on average 1.0930232558139534) internal successors, (47), 45 states have internal predecessors, (47), 27 states have call successors, (27), 12 states have call predecessors, (27), 11 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2021-05-02 19:31:44,317 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 98 transitions. [2021-05-02 19:31:44,318 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 98 transitions. Word has length 71 [2021-05-02 19:31:44,318 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 19:31:44,318 INFO L480 AbstractCegarLoop]: Abstraction has 82 states and 98 transitions. [2021-05-02 19:31:44,318 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2021-05-02 19:31:44,318 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 98 transitions. [2021-05-02 19:31:44,319 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2021-05-02 19:31:44,319 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:44,319 INFO L523 BasicCegarLoop]: trace histogram [12, 11, 11, 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] [2021-05-02 19:31:44,536 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2021-05-02 19:31:44,537 INFO L428 AbstractCegarLoop]: === Iteration 11 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:44,537 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:44,537 INFO L82 PathProgramCache]: Analyzing trace with hash -1401496737, now seen corresponding path program 2 times [2021-05-02 19:31:44,537 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:44,537 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1959243155] [2021-05-02 19:31:44,538 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:44,544 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 19:31:44,545 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [183931984] [2021-05-02 19:31:44,545 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 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-02 19:31:44,591 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-02 19:31:44,591 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-02 19:31:44,592 INFO L263 TraceCheckSpWp]: Trace formula consists of 232 conjuncts, 9 conjunts are in the unsatisfiable core [2021-05-02 19:31:44,593 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 19:31:44,600 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,602 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,602 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,606 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,607 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,607 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,639 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,640 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,641 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,675 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,676 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:44,689 INFO L134 CoverageAnalysis]: Checked inductivity of 254 backedges. 60 proven. 112 refuted. 0 times theorem prover too weak. 82 trivial. 0 not checked. [2021-05-02 19:31:44,689 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 19:31:44,689 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1959243155] [2021-05-02 19:31:44,689 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 19:31:44,689 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [183931984] [2021-05-02 19:31:44,689 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [183931984] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 19:31:44,689 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 19:31:44,689 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2021-05-02 19:31:44,689 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [69104717] [2021-05-02 19:31:44,690 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2021-05-02 19:31:44,690 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 19:31:44,690 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-05-02 19:31:44,690 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2021-05-02 19:31:44,690 INFO L87 Difference]: Start difference. First operand 82 states and 98 transitions. Second operand has 6 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 5 states have internal predecessors, (22), 5 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2021-05-02 19:31:44,745 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 19:31:44,745 INFO L93 Difference]: Finished difference Result 90 states and 105 transitions. [2021-05-02 19:31:44,746 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-05-02 19:31:44,746 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), 5 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 73 [2021-05-02 19:31:44,746 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 19:31:44,749 INFO L225 Difference]: With dead ends: 90 [2021-05-02 19:31:44,749 INFO L226 Difference]: Without dead ends: 90 [2021-05-02 19:31:44,749 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 68 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 17.7ms TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2021-05-02 19:31:44,750 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2021-05-02 19:31:44,757 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 88. [2021-05-02 19:31:44,758 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 48 states have (on average 1.1041666666666667) internal successors, (53), 50 states have internal predecessors, (53), 27 states have call successors, (27), 13 states have call predecessors, (27), 12 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2021-05-02 19:31:44,760 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 104 transitions. [2021-05-02 19:31:44,760 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 104 transitions. Word has length 73 [2021-05-02 19:31:44,760 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 19:31:44,760 INFO L480 AbstractCegarLoop]: Abstraction has 88 states and 104 transitions. [2021-05-02 19:31:44,761 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), 5 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2021-05-02 19:31:44,761 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 104 transitions. [2021-05-02 19:31:44,763 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2021-05-02 19:31:44,763 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:44,763 INFO L523 BasicCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 19:31:44,976 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2021-05-02 19:31:44,977 INFO L428 AbstractCegarLoop]: === Iteration 12 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:44,977 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:44,977 INFO L82 PathProgramCache]: Analyzing trace with hash -2049786824, now seen corresponding path program 3 times [2021-05-02 19:31:44,977 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:44,978 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [412607848] [2021-05-02 19:31:44,978 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:44,983 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 19:31:44,983 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [466692939] [2021-05-02 19:31:44,983 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 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-02 19:31:45,053 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2021-05-02 19:31:45,053 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-02 19:31:45,054 INFO L263 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 29 conjunts are in the unsatisfiable core [2021-05-02 19:31:45,055 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 19:31:45,215 INFO L134 CoverageAnalysis]: Checked inductivity of 258 backedges. 51 proven. 17 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2021-05-02 19:31:45,215 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 19:31:45,215 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [412607848] [2021-05-02 19:31:45,215 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 19:31:45,215 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [466692939] [2021-05-02 19:31:45,215 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [466692939] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 19:31:45,215 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 19:31:45,215 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2021-05-02 19:31:45,215 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1317320795] [2021-05-02 19:31:45,216 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states [2021-05-02 19:31:45,216 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 19:31:45,216 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-05-02 19:31:45,216 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2021-05-02 19:31:45,216 INFO L87 Difference]: Start difference. First operand 88 states and 104 transitions. Second operand has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2021-05-02 19:31:45,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 19:31:45,468 INFO L93 Difference]: Finished difference Result 108 states and 133 transitions. [2021-05-02 19:31:45,469 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-05-02 19:31:45,469 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 73 [2021-05-02 19:31:45,469 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 19:31:45,470 INFO L225 Difference]: With dead ends: 108 [2021-05-02 19:31:45,470 INFO L226 Difference]: Without dead ends: 108 [2021-05-02 19:31:45,470 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 70.0ms TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2021-05-02 19:31:45,470 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2021-05-02 19:31:45,484 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 107. [2021-05-02 19:31:45,485 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 55 states have (on average 1.1090909090909091) internal successors, (61), 58 states have internal predecessors, (61), 37 states have call successors, (37), 15 states have call predecessors, (37), 14 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2021-05-02 19:31:45,486 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 132 transitions. [2021-05-02 19:31:45,486 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 132 transitions. Word has length 73 [2021-05-02 19:31:45,487 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 19:31:45,487 INFO L480 AbstractCegarLoop]: Abstraction has 107 states and 132 transitions. [2021-05-02 19:31:45,487 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 10 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2021-05-02 19:31:45,487 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 132 transitions. [2021-05-02 19:31:45,488 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2021-05-02 19:31:45,488 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:45,489 INFO L523 BasicCegarLoop]: trace histogram [13, 12, 12, 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] [2021-05-02 19:31:45,706 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,10 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 19:31:45,709 INFO L428 AbstractCegarLoop]: === Iteration 13 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:45,709 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:45,709 INFO L82 PathProgramCache]: Analyzing trace with hash -601883655, now seen corresponding path program 1 times [2021-05-02 19:31:45,709 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:45,709 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [296382874] [2021-05-02 19:31:45,709 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:45,714 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 19:31:45,715 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1532874990] [2021-05-02 19:31:45,715 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-02 19:31:45,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 19:31:45,767 INFO L263 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 27 conjunts are in the unsatisfiable core [2021-05-02 19:31:45,768 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 19:31:45,824 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,825 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,832 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,833 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,841 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,841 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,848 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,849 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,856 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,856 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,873 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,876 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,902 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,905 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,912 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,913 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,917 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 19:31:45,941 INFO L134 CoverageAnalysis]: Checked inductivity of 296 backedges. 53 proven. 12 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2021-05-02 19:31:45,941 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 19:31:45,941 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [296382874] [2021-05-02 19:31:45,942 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 19:31:45,942 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1532874990] [2021-05-02 19:31:45,942 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1532874990] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 19:31:45,942 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 19:31:45,942 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2021-05-02 19:31:45,942 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1996531815] [2021-05-02 19:31:45,943 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states [2021-05-02 19:31:45,943 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 19:31:45,944 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-05-02 19:31:45,944 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2021-05-02 19:31:45,944 INFO L87 Difference]: Start difference. First operand 107 states and 132 transitions. Second operand has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 4 states have call predecessors, (13), 5 states have call successors, (13) [2021-05-02 19:31:46,151 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 19:31:46,151 INFO L93 Difference]: Finished difference Result 111 states and 135 transitions. [2021-05-02 19:31:46,152 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-05-02 19:31:46,152 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 4 states have call predecessors, (13), 5 states have call successors, (13) Word has length 76 [2021-05-02 19:31:46,152 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 19:31:46,154 INFO L225 Difference]: With dead ends: 111 [2021-05-02 19:31:46,154 INFO L226 Difference]: Without dead ends: 109 [2021-05-02 19:31:46,154 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 59.0ms TimeCoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2021-05-02 19:31:46,154 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2021-05-02 19:31:46,157 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 109. [2021-05-02 19:31:46,157 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 57 states have (on average 1.087719298245614) internal successors, (62), 59 states have internal predecessors, (62), 37 states have call successors, (37), 16 states have call predecessors, (37), 14 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2021-05-02 19:31:46,158 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 133 transitions. [2021-05-02 19:31:46,158 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 133 transitions. Word has length 76 [2021-05-02 19:31:46,158 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 19:31:46,158 INFO L480 AbstractCegarLoop]: Abstraction has 109 states and 133 transitions. [2021-05-02 19:31:46,158 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 4 states have call predecessors, (13), 5 states have call successors, (13) [2021-05-02 19:31:46,158 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 133 transitions. [2021-05-02 19:31:46,159 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2021-05-02 19:31:46,159 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 19:31:46,159 INFO L523 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 19:31:46,370 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,11 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 19:31:46,371 INFO L428 AbstractCegarLoop]: === Iteration 14 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 19:31:46,371 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 19:31:46,371 INFO L82 PathProgramCache]: Analyzing trace with hash -1157335722, now seen corresponding path program 4 times [2021-05-02 19:31:46,371 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 19:31:46,371 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1674409661] [2021-05-02 19:31:46,371 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 19:31:46,377 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 19:31:46,377 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1806094776] [2021-05-02 19:31:46,377 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST 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