/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/egcd3-ll_valuebound2.c -------------------------------------------------------------------------------- This is Ultimate 0.2.1-dev-c225d54 [2021-05-02 20:33:49,586 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-05-02 20:33:49,588 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-05-02 20:33:49,619 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-05-02 20:33:49,619 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-05-02 20:33:49,623 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-05-02 20:33:49,625 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-05-02 20:33:49,628 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-05-02 20:33:49,630 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-05-02 20:33:49,633 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-05-02 20:33:49,633 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-05-02 20:33:49,634 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-05-02 20:33:49,634 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-05-02 20:33:49,636 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-05-02 20:33:49,637 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-05-02 20:33:49,638 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-05-02 20:33:49,640 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-05-02 20:33:49,640 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-05-02 20:33:49,642 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-05-02 20:33:49,646 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-05-02 20:33:49,646 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-05-02 20:33:49,647 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-05-02 20:33:49,648 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-05-02 20:33:49,649 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-05-02 20:33:49,654 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-05-02 20:33:49,654 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-05-02 20:33:49,654 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-05-02 20:33:49,655 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-05-02 20:33:49,655 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-05-02 20:33:49,656 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-05-02 20:33:49,656 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-05-02 20:33:49,657 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-05-02 20:33:49,658 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-05-02 20:33:49,658 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-05-02 20:33:49,659 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-05-02 20:33:49,659 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-05-02 20:33:49,659 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-05-02 20:33:49,659 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-05-02 20:33:49,660 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-05-02 20:33:49,660 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-05-02 20:33:49,661 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-05-02 20:33:49,661 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2021-05-02 20:33:49,674 INFO L113 SettingsManager]: Loading preferences was successful [2021-05-02 20:33:49,674 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-05-02 20:33:49,676 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-05-02 20:33:49,676 INFO L138 SettingsManager]: * sizeof long=4 [2021-05-02 20:33:49,676 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-05-02 20:33:49,676 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-05-02 20:33:49,677 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-05-02 20:33:49,677 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-05-02 20:33:49,677 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-05-02 20:33:49,677 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-05-02 20:33:49,677 INFO L138 SettingsManager]: * sizeof long double=12 [2021-05-02 20:33:49,678 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-05-02 20:33:49,678 INFO L138 SettingsManager]: * Use constant arrays=true [2021-05-02 20:33:49,678 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-05-02 20:33:49,678 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-05-02 20:33:49,678 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-05-02 20:33:49,678 INFO L138 SettingsManager]: * To the following directory=./dump/ [2021-05-02 20:33:49,678 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-05-02 20:33:49,678 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-05-02 20:33:49,678 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-05-02 20:33:49,679 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-05-02 20:33:49,679 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2021-05-02 20:33:49,679 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 20:33:49,938 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-05-02 20:33:49,955 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-05-02 20:33:49,956 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-05-02 20:33:49,957 INFO L271 PluginConnector]: Initializing CDTParser... [2021-05-02 20:33:49,958 INFO L275 PluginConnector]: CDTParser initialized [2021-05-02 20:33:49,958 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd3-ll_valuebound2.c [2021-05-02 20:33:50,007 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/42d691cf8/de5711ce6ffc4df5a18892facb5dd73d/FLAG199611d4a [2021-05-02 20:33:50,385 INFO L306 CDTParser]: Found 1 translation units. [2021-05-02 20:33:50,385 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd3-ll_valuebound2.c [2021-05-02 20:33:50,390 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/42d691cf8/de5711ce6ffc4df5a18892facb5dd73d/FLAG199611d4a [2021-05-02 20:33:50,402 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/42d691cf8/de5711ce6ffc4df5a18892facb5dd73d [2021-05-02 20:33:50,404 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-05-02 20:33:50,406 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2021-05-02 20:33:50,410 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-05-02 20:33:50,410 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-05-02 20:33:50,412 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-05-02 20:33:50,412 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.05 08:33:50" (1/1) ... [2021-05-02 20:33:50,413 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@25c881de and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 08:33:50, skipping insertion in model container [2021-05-02 20:33:50,413 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.05 08:33:50" (1/1) ... [2021-05-02 20:33:50,417 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-05-02 20:33:50,430 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-05-02 20:33:50,550 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/egcd3-ll_valuebound2.c[490,503] [2021-05-02 20:33:50,572 INFO L206 PostProcessor]: Analyzing one entry point: main [2021-05-02 20:33:50,577 INFO L203 MainTranslator]: Completed pre-run [2021-05-02 20:33:50,618 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/egcd3-ll_valuebound2.c[490,503] [2021-05-02 20:33:50,623 INFO L206 PostProcessor]: Analyzing one entry point: main [2021-05-02 20:33:50,631 INFO L208 MainTranslator]: Completed translation [2021-05-02 20:33:50,631 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 08:33:50 WrapperNode [2021-05-02 20:33:50,631 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-05-02 20:33:50,632 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-05-02 20:33:50,632 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-05-02 20:33:50,632 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-05-02 20:33:50,638 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 08:33:50" (1/1) ... [2021-05-02 20:33:50,638 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 08:33:50" (1/1) ... [2021-05-02 20:33:50,642 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 08:33:50" (1/1) ... [2021-05-02 20:33:50,643 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 08:33:50" (1/1) ... [2021-05-02 20:33:50,646 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 08:33:50" (1/1) ... [2021-05-02 20:33:50,648 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 08:33:50" (1/1) ... [2021-05-02 20:33:50,649 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 08:33:50" (1/1) ... [2021-05-02 20:33:50,650 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-05-02 20:33:50,651 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-05-02 20:33:50,651 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-05-02 20:33:50,651 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-05-02 20:33:50,651 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 08:33:50" (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 20:33:50,718 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2021-05-02 20:33:50,718 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-05-02 20:33:50,718 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2021-05-02 20:33:50,718 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2021-05-02 20:33:50,718 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-05-02 20:33:50,718 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2021-05-02 20:33:50,719 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2021-05-02 20:33:50,719 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2021-05-02 20:33:50,719 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2021-05-02 20:33:50,719 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-05-02 20:33:50,719 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2021-05-02 20:33:50,719 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2021-05-02 20:33:50,719 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-05-02 20:33:50,720 INFO L130 BoogieDeclarations]: Found specification of procedure main [2021-05-02 20:33:50,720 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2021-05-02 20:33:50,720 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-05-02 20:33:50,720 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-05-02 20:33:50,720 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2021-05-02 20:33:50,720 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2021-05-02 20:33:50,720 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-05-02 20:33:50,956 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-05-02 20:33:50,957 INFO L299 CfgBuilder]: Removed 3 assume(true) statements. [2021-05-02 20:33:50,957 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.05 08:33:50 BoogieIcfgContainer [2021-05-02 20:33:50,958 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-05-02 20:33:50,958 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2021-05-02 20:33:50,958 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2021-05-02 20:33:50,959 INFO L275 PluginConnector]: IcfgTransformer initialized [2021-05-02 20:33:50,960 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.05 08:33:50" (1/1) ... [2021-05-02 20:33:50,971 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 02.05 08:33:50 BasicIcfg [2021-05-02 20:33:50,971 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2021-05-02 20:33:50,972 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-05-02 20:33:50,972 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-05-02 20:33:50,974 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-05-02 20:33:50,974 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.05 08:33:50" (1/4) ... [2021-05-02 20:33:50,974 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@252a84e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.05 08:33:50, skipping insertion in model container [2021-05-02 20:33:50,974 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.05 08:33:50" (2/4) ... [2021-05-02 20:33:50,974 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@252a84e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.05 08:33:50, skipping insertion in model container [2021-05-02 20:33:50,975 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.05 08:33:50" (3/4) ... [2021-05-02 20:33:50,975 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@252a84e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 02.05 08:33:50, skipping insertion in model container [2021-05-02 20:33:50,975 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 02.05 08:33:50" (4/4) ... [2021-05-02 20:33:50,975 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound2.cJordan [2021-05-02 20:33:50,979 INFO L149 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2021-05-02 20:33:50,981 INFO L161 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2021-05-02 20:33:50,991 INFO L253 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-05-02 20:33:51,003 INFO L376 AbstractCegarLoop]: Interprodecural is true [2021-05-02 20:33:51,003 INFO L377 AbstractCegarLoop]: Hoare is false [2021-05-02 20:33:51,003 INFO L378 AbstractCegarLoop]: Compute interpolants for ForwardPredicates [2021-05-02 20:33:51,003 INFO L379 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2021-05-02 20:33:51,003 INFO L380 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2021-05-02 20:33:51,003 INFO L381 AbstractCegarLoop]: Difference is false [2021-05-02 20:33:51,003 INFO L382 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2021-05-02 20:33:51,003 INFO L386 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2021-05-02 20:33:51,012 INFO L276 IsEmpty]: Start isEmpty. Operand has 40 states, 23 states have (on average 1.5217391304347827) internal successors, (35), 24 states have internal predecessors, (35), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2021-05-02 20:33:51,016 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2021-05-02 20:33:51,016 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:51,017 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:51,017 INFO L428 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:51,021 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:51,021 INFO L82 PathProgramCache]: Analyzing trace with hash 958536290, now seen corresponding path program 1 times [2021-05-02 20:33:51,026 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:51,027 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1520347326] [2021-05-02 20:33:51,027 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:51,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:51,217 INFO L375 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2021-05-02 20:33:51,221 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:51,241 INFO L375 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-05-02 20:33:51,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:51,248 INFO L375 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-05-02 20:33:51,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:51,253 INFO L375 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2021-05-02 20:33:51,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:51,262 INFO L375 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2021-05-02 20:33:51,264 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:51,267 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-05-02 20:33:51,268 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:51,268 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1520347326] [2021-05-02 20:33:51,268 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1520347326] provided 1 perfect and 0 imperfect interpolant sequences [2021-05-02 20:33:51,268 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-05-02 20:33:51,269 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-05-02 20:33:51,269 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1818953106] [2021-05-02 20:33:51,275 INFO L460 AbstractCegarLoop]: Interpolant automaton has 3 states [2021-05-02 20:33:51,275 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:51,282 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-05-02 20:33:51,282 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-05-02 20:33:51,284 INFO L87 Difference]: Start difference. First operand has 40 states, 23 states have (on average 1.5217391304347827) internal successors, (35), 24 states have internal predecessors, (35), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2021-05-02 20:33:51,427 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:51,428 INFO L93 Difference]: Finished difference Result 40 states and 49 transitions. [2021-05-02 20:33:51,428 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-05-02 20:33:51,429 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2021-05-02 20:33:51,430 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:51,434 INFO L225 Difference]: With dead ends: 40 [2021-05-02 20:33:51,434 INFO L226 Difference]: Without dead ends: 35 [2021-05-02 20:33:51,436 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 43.8ms TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-05-02 20:33:51,446 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2021-05-02 20:33:51,460 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2021-05-02 20:33:51,461 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2021-05-02 20:33:51,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 44 transitions. [2021-05-02 20:33:51,464 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 44 transitions. Word has length 33 [2021-05-02 20:33:51,464 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:51,464 INFO L480 AbstractCegarLoop]: Abstraction has 35 states and 44 transitions. [2021-05-02 20:33:51,464 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2021-05-02 20:33:51,465 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 44 transitions. [2021-05-02 20:33:51,467 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2021-05-02 20:33:51,467 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:51,467 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:51,467 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-05-02 20:33:51,467 INFO L428 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:51,468 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:51,469 INFO L82 PathProgramCache]: Analyzing trace with hash 641145651, now seen corresponding path program 1 times [2021-05-02 20:33:51,469 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:51,469 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [963907764] [2021-05-02 20:33:51,469 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:51,500 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:51,500 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [217098662] [2021-05-02 20:33:51,500 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 20:33:51,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:51,575 INFO L263 TraceCheckSpWp]: Trace formula consists of 141 conjuncts, 7 conjunts are in the unsatisfiable core [2021-05-02 20:33:51,578 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:51,703 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:51,733 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-05-02 20:33:51,733 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:51,733 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [963907764] [2021-05-02 20:33:51,733 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:51,733 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [217098662] [2021-05-02 20:33:51,733 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [217098662] provided 1 perfect and 0 imperfect interpolant sequences [2021-05-02 20:33:51,733 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-05-02 20:33:51,734 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2021-05-02 20:33:51,734 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1022583720] [2021-05-02 20:33:51,734 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2021-05-02 20:33:51,735 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:51,735 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-05-02 20:33:51,735 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2021-05-02 20:33:51,735 INFO L87 Difference]: Start difference. First operand 35 states and 44 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 1 states have call successors, (5) [2021-05-02 20:33:51,796 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:51,796 INFO L93 Difference]: Finished difference Result 47 states and 62 transitions. [2021-05-02 20:33:51,798 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-05-02 20:33:51,798 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 1 states have call successors, (5) Word has length 34 [2021-05-02 20:33:51,798 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:51,799 INFO L225 Difference]: With dead ends: 47 [2021-05-02 20:33:51,799 INFO L226 Difference]: Without dead ends: 47 [2021-05-02 20:33:51,799 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 30.7ms TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2021-05-02 20:33:51,800 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2021-05-02 20:33:51,804 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 37. [2021-05-02 20:33:51,804 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 23 states have internal predecessors, (26), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2021-05-02 20:33:51,805 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 46 transitions. [2021-05-02 20:33:51,805 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 46 transitions. Word has length 34 [2021-05-02 20:33:51,805 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:51,805 INFO L480 AbstractCegarLoop]: Abstraction has 37 states and 46 transitions. [2021-05-02 20:33:51,805 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 1 states have call successors, (5) [2021-05-02 20:33:51,805 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 46 transitions. [2021-05-02 20:33:51,806 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2021-05-02 20:33:51,806 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:51,806 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:52,007 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2021-05-02 20:33:52,007 INFO L428 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:52,007 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:52,008 INFO L82 PathProgramCache]: Analyzing trace with hash 283168444, now seen corresponding path program 1 times [2021-05-02 20:33:52,008 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:52,008 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [201866044] [2021-05-02 20:33:52,008 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:52,019 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:52,019 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [659705045] [2021-05-02 20:33:52,019 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 20:33:52,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:52,082 INFO L263 TraceCheckSpWp]: Trace formula consists of 151 conjuncts, 32 conjunts are in the unsatisfiable core [2021-05-02 20:33:52,086 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:52,148 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,159 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,191 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,192 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,201 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,202 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,226 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,227 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,228 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,229 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,300 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,302 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,303 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,304 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,324 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-05-02 20:33:52,324 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:52,324 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [201866044] [2021-05-02 20:33:52,324 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:52,325 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [659705045] [2021-05-02 20:33:52,325 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [659705045] provided 1 perfect and 0 imperfect interpolant sequences [2021-05-02 20:33:52,325 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-05-02 20:33:52,325 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2021-05-02 20:33:52,325 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [962255840] [2021-05-02 20:33:52,326 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2021-05-02 20:33:52,326 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:52,326 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-05-02 20:33:52,329 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2021-05-02 20:33:52,329 INFO L87 Difference]: Start difference. First operand 37 states and 46 transitions. Second operand has 11 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 5 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 5 states have call predecessors, (5), 4 states have call successors, (5) [2021-05-02 20:33:52,431 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:52,431 INFO L93 Difference]: Finished difference Result 51 states and 65 transitions. [2021-05-02 20:33:52,431 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-05-02 20:33:52,432 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 5 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 5 states have call predecessors, (5), 4 states have call successors, (5) Word has length 37 [2021-05-02 20:33:52,432 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:52,433 INFO L225 Difference]: With dead ends: 51 [2021-05-02 20:33:52,433 INFO L226 Difference]: Without dead ends: 51 [2021-05-02 20:33:52,433 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 82.5ms TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2021-05-02 20:33:52,433 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2021-05-02 20:33:52,437 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 50. [2021-05-02 20:33:52,437 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 30 states have (on average 1.2) internal successors, (36), 31 states have internal predecessors, (36), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2021-05-02 20:33:52,438 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 64 transitions. [2021-05-02 20:33:52,438 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 64 transitions. Word has length 37 [2021-05-02 20:33:52,438 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:52,438 INFO L480 AbstractCegarLoop]: Abstraction has 50 states and 64 transitions. [2021-05-02 20:33:52,438 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 11 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 5 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 5 states have call predecessors, (5), 4 states have call successors, (5) [2021-05-02 20:33:52,439 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2021-05-02 20:33:52,439 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2021-05-02 20:33:52,439 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:52,440 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:52,656 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:33:52,657 INFO L428 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:52,657 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:52,657 INFO L82 PathProgramCache]: Analyzing trace with hash 656144812, now seen corresponding path program 1 times [2021-05-02 20:33:52,658 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:52,658 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [644125450] [2021-05-02 20:33:52,658 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:52,672 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:52,672 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1997022704] [2021-05-02 20:33:52,672 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 20:33:52,725 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:52,726 INFO L263 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 9 conjunts are in the unsatisfiable core [2021-05-02 20:33:52,728 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:52,782 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,783 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,791 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,800 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,812 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:52,828 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-05-02 20:33:52,828 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:52,828 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [644125450] [2021-05-02 20:33:52,829 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:52,829 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1997022704] [2021-05-02 20:33:52,829 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1997022704] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:33:52,829 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:33:52,829 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2021-05-02 20:33:52,829 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [924392053] [2021-05-02 20:33:52,829 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2021-05-02 20:33:52,829 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:52,830 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-05-02 20:33:52,830 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2021-05-02 20:33:52,830 INFO L87 Difference]: Start difference. First operand 50 states and 64 transitions. Second operand has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2021-05-02 20:33:53,008 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:53,008 INFO L93 Difference]: Finished difference Result 96 states and 136 transitions. [2021-05-02 20:33:53,008 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-05-02 20:33:53,008 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 39 [2021-05-02 20:33:53,009 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:53,009 INFO L225 Difference]: With dead ends: 96 [2021-05-02 20:33:53,009 INFO L226 Difference]: Without dead ends: 96 [2021-05-02 20:33:53,010 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 66.8ms TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2021-05-02 20:33:53,010 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2021-05-02 20:33:53,015 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 71. [2021-05-02 20:33:53,015 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 47 states have (on average 1.2553191489361701) internal successors, (59), 48 states have internal predecessors, (59), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2021-05-02 20:33:53,016 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 95 transitions. [2021-05-02 20:33:53,016 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 95 transitions. Word has length 39 [2021-05-02 20:33:53,017 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:53,017 INFO L480 AbstractCegarLoop]: Abstraction has 71 states and 95 transitions. [2021-05-02 20:33:53,017 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2021-05-02 20:33:53,017 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 95 transitions. [2021-05-02 20:33:53,017 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2021-05-02 20:33:53,017 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:53,018 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:53,232 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:33:53,235 INFO L428 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:53,235 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:53,235 INFO L82 PathProgramCache]: Analyzing trace with hash -2079765955, now seen corresponding path program 1 times [2021-05-02 20:33:53,236 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:53,236 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2064055315] [2021-05-02 20:33:53,236 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:53,246 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:53,246 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1836237095] [2021-05-02 20:33:53,246 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 20:33:53,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:53,297 INFO L263 TraceCheckSpWp]: Trace formula consists of 160 conjuncts, 32 conjunts are in the unsatisfiable core [2021-05-02 20:33:53,301 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:53,331 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,333 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,355 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,357 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,360 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,361 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,384 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,386 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,389 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,389 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,445 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,448 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,450 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,450 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,460 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,473 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,475 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,476 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,496 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-05-02 20:33:53,496 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:53,496 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2064055315] [2021-05-02 20:33:53,497 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:53,497 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1836237095] [2021-05-02 20:33:53,497 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1836237095] provided 1 perfect and 0 imperfect interpolant sequences [2021-05-02 20:33:53,497 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-05-02 20:33:53,497 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2021-05-02 20:33:53,497 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [597868543] [2021-05-02 20:33:53,497 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2021-05-02 20:33:53,497 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:53,498 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-05-02 20:33:53,498 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2021-05-02 20:33:53,498 INFO L87 Difference]: Start difference. First operand 71 states and 95 transitions. Second operand has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2021-05-02 20:33:53,604 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:53,605 INFO L93 Difference]: Finished difference Result 77 states and 100 transitions. [2021-05-02 20:33:53,605 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-05-02 20:33:53,606 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) Word has length 42 [2021-05-02 20:33:53,608 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:53,610 INFO L225 Difference]: With dead ends: 77 [2021-05-02 20:33:53,610 INFO L226 Difference]: Without dead ends: 77 [2021-05-02 20:33:53,610 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 72.4ms TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2021-05-02 20:33:53,611 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2021-05-02 20:33:53,623 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 75. [2021-05-02 20:33:53,623 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 50 states have (on average 1.24) internal successors, (62), 51 states have internal predecessors, (62), 19 states have call successors, (19), 6 states have call predecessors, (19), 5 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2021-05-02 20:33:53,624 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 98 transitions. [2021-05-02 20:33:53,624 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 98 transitions. Word has length 42 [2021-05-02 20:33:53,624 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:53,624 INFO L480 AbstractCegarLoop]: Abstraction has 75 states and 98 transitions. [2021-05-02 20:33:53,624 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 11 states, 9 states have (on average 2.111111111111111) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2021-05-02 20:33:53,624 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 98 transitions. [2021-05-02 20:33:53,625 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2021-05-02 20:33:53,625 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:53,625 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:53,840 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:33:53,841 INFO L428 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:53,841 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:53,841 INFO L82 PathProgramCache]: Analyzing trace with hash 446575011, now seen corresponding path program 1 times [2021-05-02 20:33:53,841 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:53,841 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1016037089] [2021-05-02 20:33:53,842 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:53,856 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:53,856 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [406684667] [2021-05-02 20:33:53,856 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 20:33:53,901 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:53,902 INFO L263 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 35 conjunts are in the unsatisfiable core [2021-05-02 20:33:53,904 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:53,929 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,930 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,945 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,946 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,947 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,948 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,970 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,971 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,972 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:53,973 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,009 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,032 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,097 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,099 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,107 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,112 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,137 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,157 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-05-02 20:33:54,158 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:54,158 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1016037089] [2021-05-02 20:33:54,158 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:54,158 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [406684667] [2021-05-02 20:33:54,158 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [406684667] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:33:54,158 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:33:54,158 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2021-05-02 20:33:54,158 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [430075186] [2021-05-02 20:33:54,158 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2021-05-02 20:33:54,159 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:54,159 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-05-02 20:33:54,159 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2021-05-02 20:33:54,159 INFO L87 Difference]: Start difference. First operand 75 states and 98 transitions. Second operand has 13 states, 12 states have (on average 2.0) internal successors, (24), 10 states have internal predecessors, (24), 5 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2021-05-02 20:33:54,376 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:54,377 INFO L93 Difference]: Finished difference Result 103 states and 137 transitions. [2021-05-02 20:33:54,377 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-05-02 20:33:54,377 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.0) internal successors, (24), 10 states have internal predecessors, (24), 5 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 42 [2021-05-02 20:33:54,377 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:54,378 INFO L225 Difference]: With dead ends: 103 [2021-05-02 20:33:54,378 INFO L226 Difference]: Without dead ends: 103 [2021-05-02 20:33:54,379 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 159.8ms TimeCoverageRelationStatistics Valid=62, Invalid=210, Unknown=0, NotChecked=0, Total=272 [2021-05-02 20:33:54,379 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2021-05-02 20:33:54,392 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 93. [2021-05-02 20:33:54,393 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 63 states have (on average 1.2380952380952381) internal successors, (78), 64 states have internal predecessors, (78), 23 states have call successors, (23), 7 states have call predecessors, (23), 6 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2021-05-02 20:33:54,395 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 122 transitions. [2021-05-02 20:33:54,395 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 122 transitions. Word has length 42 [2021-05-02 20:33:54,396 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:54,396 INFO L480 AbstractCegarLoop]: Abstraction has 93 states and 122 transitions. [2021-05-02 20:33:54,396 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 13 states, 12 states have (on average 2.0) internal successors, (24), 10 states have internal predecessors, (24), 5 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2021-05-02 20:33:54,396 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 122 transitions. [2021-05-02 20:33:54,398 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2021-05-02 20:33:54,398 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:54,398 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:54,608 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2021-05-02 20:33:54,609 INFO L428 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:54,609 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:54,609 INFO L82 PathProgramCache]: Analyzing trace with hash -1977261252, now seen corresponding path program 1 times [2021-05-02 20:33:54,609 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:54,609 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1999245123] [2021-05-02 20:33:54,609 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:54,618 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:54,618 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1708886695] [2021-05-02 20:33:54,618 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:33:54,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:54,663 INFO L263 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 21 conjunts are in the unsatisfiable core [2021-05-02 20:33:54,665 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:54,682 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,706 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,738 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,739 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,749 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,750 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,757 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,758 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:54,772 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 10 proven. 6 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2021-05-02 20:33:54,773 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:54,773 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1999245123] [2021-05-02 20:33:54,773 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:54,773 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1708886695] [2021-05-02 20:33:54,773 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1708886695] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:33:54,773 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:33:54,773 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2021-05-02 20:33:54,773 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [105778508] [2021-05-02 20:33:54,774 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2021-05-02 20:33:54,774 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:54,774 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-05-02 20:33:54,774 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2021-05-02 20:33:54,774 INFO L87 Difference]: Start difference. First operand 93 states and 122 transitions. Second operand has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 7 states have internal predecessors, (22), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2021-05-02 20:33:54,887 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:54,887 INFO L93 Difference]: Finished difference Result 105 states and 138 transitions. [2021-05-02 20:33:54,887 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-05-02 20:33:54,888 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 7 states have internal predecessors, (22), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 47 [2021-05-02 20:33:54,889 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:54,890 INFO L225 Difference]: With dead ends: 105 [2021-05-02 20:33:54,890 INFO L226 Difference]: Without dead ends: 105 [2021-05-02 20:33:54,891 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 69.7ms TimeCoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2021-05-02 20:33:54,891 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states. [2021-05-02 20:33:54,901 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 103. [2021-05-02 20:33:54,901 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 68 states have (on average 1.2352941176470589) internal successors, (84), 69 states have internal predecessors, (84), 27 states have call successors, (27), 8 states have call predecessors, (27), 7 states have return successors, (25), 25 states have call predecessors, (25), 25 states have call successors, (25) [2021-05-02 20:33:54,903 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 136 transitions. [2021-05-02 20:33:54,903 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 136 transitions. Word has length 47 [2021-05-02 20:33:54,903 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:54,903 INFO L480 AbstractCegarLoop]: Abstraction has 103 states and 136 transitions. [2021-05-02 20:33:54,903 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 7 states have internal predecessors, (22), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2021-05-02 20:33:54,903 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 136 transitions. [2021-05-02 20:33:54,906 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2021-05-02 20:33:54,906 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:54,907 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:55,121 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:33:55,121 INFO L428 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:55,121 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:55,121 INFO L82 PathProgramCache]: Analyzing trace with hash -846684234, now seen corresponding path program 1 times [2021-05-02 20:33:55,122 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:55,122 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [256213409] [2021-05-02 20:33:55,122 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:55,145 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:55,145 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1899117747] [2021-05-02 20:33:55,145 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 20:33:55,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:55,192 INFO L263 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 47 conjunts are in the unsatisfiable core [2021-05-02 20:33:55,202 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:55,229 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,230 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,246 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,247 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,248 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,249 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,273 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,274 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,275 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,275 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,328 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,389 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,391 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,399 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,400 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,417 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 2 proven. 13 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-05-02 20:33:55,417 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:55,417 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [256213409] [2021-05-02 20:33:55,417 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:55,417 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1899117747] [2021-05-02 20:33:55,417 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1899117747] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:33:55,417 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:33:55,417 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2021-05-02 20:33:55,417 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1837332880] [2021-05-02 20:33:55,418 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2021-05-02 20:33:55,418 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:55,418 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-05-02 20:33:55,418 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2021-05-02 20:33:55,418 INFO L87 Difference]: Start difference. First operand 103 states and 136 transitions. Second operand has 13 states, 12 states have (on average 2.25) internal successors, (27), 10 states have internal predecessors, (27), 5 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2021-05-02 20:33:55,660 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:55,661 INFO L93 Difference]: Finished difference Result 111 states and 143 transitions. [2021-05-02 20:33:55,661 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-05-02 20:33:55,661 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.25) internal successors, (27), 10 states have internal predecessors, (27), 5 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 47 [2021-05-02 20:33:55,661 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:55,662 INFO L225 Difference]: With dead ends: 111 [2021-05-02 20:33:55,662 INFO L226 Difference]: Without dead ends: 111 [2021-05-02 20:33:55,662 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 172.1ms TimeCoverageRelationStatistics Valid=62, Invalid=210, Unknown=0, NotChecked=0, Total=272 [2021-05-02 20:33:55,662 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2021-05-02 20:33:55,665 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 107. [2021-05-02 20:33:55,665 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 71 states have (on average 1.2253521126760563) internal successors, (87), 72 states have internal predecessors, (87), 27 states have call successors, (27), 9 states have call predecessors, (27), 8 states have return successors, (25), 25 states have call predecessors, (25), 25 states have call successors, (25) [2021-05-02 20:33:55,666 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 139 transitions. [2021-05-02 20:33:55,666 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 139 transitions. Word has length 47 [2021-05-02 20:33:55,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:55,666 INFO L480 AbstractCegarLoop]: Abstraction has 107 states and 139 transitions. [2021-05-02 20:33:55,666 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 13 states, 12 states have (on average 2.25) internal successors, (27), 10 states have internal predecessors, (27), 5 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2021-05-02 20:33:55,666 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 139 transitions. [2021-05-02 20:33:55,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2021-05-02 20:33:55,667 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:55,667 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:55,880 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2021-05-02 20:33:55,881 INFO L428 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:55,881 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:55,881 INFO L82 PathProgramCache]: Analyzing trace with hash 1679656732, now seen corresponding path program 2 times [2021-05-02 20:33:55,881 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:55,882 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1572552877] [2021-05-02 20:33:55,882 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:55,888 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:55,888 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1733525382] [2021-05-02 20:33:55,888 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 20:33:55,943 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-02 20:33:55,943 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-02 20:33:55,944 INFO L263 TraceCheckSpWp]: Trace formula consists of 195 conjuncts, 5 conjunts are in the unsatisfiable core [2021-05-02 20:33:55,945 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:55,979 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,980 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,980 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:55,989 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,002 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-05-02 20:33:56,002 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:56,003 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1572552877] [2021-05-02 20:33:56,003 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:56,003 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1733525382] [2021-05-02 20:33:56,003 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1733525382] provided 1 perfect and 0 imperfect interpolant sequences [2021-05-02 20:33:56,003 INFO L226 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-05-02 20:33:56,003 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-05-02 20:33:56,003 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [101782720] [2021-05-02 20:33:56,003 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2021-05-02 20:33:56,003 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:56,004 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-05-02 20:33:56,004 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-05-02 20:33:56,004 INFO L87 Difference]: Start difference. First operand 107 states and 139 transitions. Second operand has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2021-05-02 20:33:56,074 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:56,075 INFO L93 Difference]: Finished difference Result 110 states and 143 transitions. [2021-05-02 20:33:56,075 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-05-02 20:33:56,075 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 47 [2021-05-02 20:33:56,075 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:56,077 INFO L225 Difference]: With dead ends: 110 [2021-05-02 20:33:56,077 INFO L226 Difference]: Without dead ends: 110 [2021-05-02 20:33:56,077 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 17.0ms TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2021-05-02 20:33:56,078 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2021-05-02 20:33:56,081 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 90. [2021-05-02 20:33:56,081 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 58 states have (on average 1.1724137931034482) internal successors, (68), 59 states have internal predecessors, (68), 23 states have call successors, (23), 9 states have call predecessors, (23), 8 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2021-05-02 20:33:56,082 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 112 transitions. [2021-05-02 20:33:56,082 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 112 transitions. Word has length 47 [2021-05-02 20:33:56,082 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:56,082 INFO L480 AbstractCegarLoop]: Abstraction has 90 states and 112 transitions. [2021-05-02 20:33:56,082 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2021-05-02 20:33:56,082 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 112 transitions. [2021-05-02 20:33:56,083 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2021-05-02 20:33:56,083 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:56,083 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:56,288 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2021-05-02 20:33:56,289 INFO L428 AbstractCegarLoop]: === Iteration 10 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:56,289 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:56,289 INFO L82 PathProgramCache]: Analyzing trace with hash -1660248707, now seen corresponding path program 1 times [2021-05-02 20:33:56,289 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:56,289 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2085255494] [2021-05-02 20:33:56,290 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:56,296 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:56,296 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [116032594] [2021-05-02 20:33:56,297 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:33:56,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:56,339 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 15 conjunts are in the unsatisfiable core [2021-05-02 20:33:56,340 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:56,360 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,439 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 9 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2021-05-02 20:33:56,439 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:56,439 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2085255494] [2021-05-02 20:33:56,440 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:56,440 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [116032594] [2021-05-02 20:33:56,440 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [116032594] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:33:56,440 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:33:56,440 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2021-05-02 20:33:56,440 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1947094747] [2021-05-02 20:33:56,440 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2021-05-02 20:33:56,440 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:56,441 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-05-02 20:33:56,441 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-05-02 20:33:56,441 INFO L87 Difference]: Start difference. First operand 90 states and 112 transitions. Second operand has 7 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 2 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2021-05-02 20:33:56,502 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:56,502 INFO L93 Difference]: Finished difference Result 128 states and 172 transitions. [2021-05-02 20:33:56,503 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-05-02 20:33:56,503 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 2 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 52 [2021-05-02 20:33:56,503 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:56,504 INFO L225 Difference]: With dead ends: 128 [2021-05-02 20:33:56,504 INFO L226 Difference]: Without dead ends: 128 [2021-05-02 20:33:56,504 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 46 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 27.4ms TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2021-05-02 20:33:56,504 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2021-05-02 20:33:56,507 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 114. [2021-05-02 20:33:56,508 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 114 states, 65 states have (on average 1.1538461538461537) internal successors, (75), 70 states have internal predecessors, (75), 39 states have call successors, (39), 10 states have call predecessors, (39), 9 states have return successors, (37), 33 states have call predecessors, (37), 37 states have call successors, (37) [2021-05-02 20:33:56,508 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 151 transitions. [2021-05-02 20:33:56,508 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 151 transitions. Word has length 52 [2021-05-02 20:33:56,509 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:56,509 INFO L480 AbstractCegarLoop]: Abstraction has 114 states and 151 transitions. [2021-05-02 20:33:56,509 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 7 states, 7 states have (on average 3.142857142857143) internal successors, (22), 6 states have internal predecessors, (22), 2 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2021-05-02 20:33:56,509 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 151 transitions. [2021-05-02 20:33:56,509 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2021-05-02 20:33:56,509 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:56,509 INFO L523 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:56,713 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:33:56,713 INFO L428 AbstractCegarLoop]: === Iteration 11 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:56,714 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:56,714 INFO L82 PathProgramCache]: Analyzing trace with hash 846041443, now seen corresponding path program 1 times [2021-05-02 20:33:56,714 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:56,714 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [669138417] [2021-05-02 20:33:56,714 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:56,720 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:56,720 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1112933617] [2021-05-02 20:33:56,720 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 20:33:56,775 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:56,776 INFO L263 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 23 conjunts are in the unsatisfiable core [2021-05-02 20:33:56,777 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:56,800 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,801 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,807 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,817 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,830 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,831 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,839 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,847 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,856 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,881 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,882 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,889 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,890 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,897 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,898 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:56,915 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 7 proven. 13 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2021-05-02 20:33:56,915 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:56,915 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [669138417] [2021-05-02 20:33:56,915 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:56,915 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1112933617] [2021-05-02 20:33:56,916 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1112933617] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:33:56,916 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:33:56,916 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2021-05-02 20:33:56,916 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1392931685] [2021-05-02 20:33:56,916 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2021-05-02 20:33:56,916 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:56,917 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-05-02 20:33:56,917 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=109, Unknown=0, NotChecked=0, Total=132 [2021-05-02 20:33:56,917 INFO L87 Difference]: Start difference. First operand 114 states and 151 transitions. Second operand has 12 states, 12 states have (on average 2.25) internal successors, (27), 10 states have internal predecessors, (27), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2021-05-02 20:33:57,129 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:57,129 INFO L93 Difference]: Finished difference Result 164 states and 229 transitions. [2021-05-02 20:33:57,129 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-05-02 20:33:57,129 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.25) internal successors, (27), 10 states have internal predecessors, (27), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) Word has length 52 [2021-05-02 20:33:57,130 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:57,131 INFO L225 Difference]: With dead ends: 164 [2021-05-02 20:33:57,131 INFO L226 Difference]: Without dead ends: 164 [2021-05-02 20:33:57,132 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 111.8ms TimeCoverageRelationStatistics Valid=72, Invalid=270, Unknown=0, NotChecked=0, Total=342 [2021-05-02 20:33:57,132 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 164 states. [2021-05-02 20:33:57,136 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 164 to 92. [2021-05-02 20:33:57,136 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 53 states have (on average 1.150943396226415) internal successors, (61), 57 states have internal predecessors, (61), 31 states have call successors, (31), 8 states have call predecessors, (31), 7 states have return successors, (29), 26 states have call predecessors, (29), 29 states have call successors, (29) [2021-05-02 20:33:57,137 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 121 transitions. [2021-05-02 20:33:57,137 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 121 transitions. Word has length 52 [2021-05-02 20:33:57,137 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:57,137 INFO L480 AbstractCegarLoop]: Abstraction has 92 states and 121 transitions. [2021-05-02 20:33:57,137 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 12 states, 12 states have (on average 2.25) internal successors, (27), 10 states have internal predecessors, (27), 4 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2021-05-02 20:33:57,137 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 121 transitions. [2021-05-02 20:33:57,137 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2021-05-02 20:33:57,138 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:57,138 INFO L523 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:57,355 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,11 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:33:57,355 INFO L428 AbstractCegarLoop]: === Iteration 12 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:57,356 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:57,356 INFO L82 PathProgramCache]: Analyzing trace with hash 1094467600, now seen corresponding path program 1 times [2021-05-02 20:33:57,356 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:57,356 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [711016012] [2021-05-02 20:33:57,356 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:57,362 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:57,362 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [614735165] [2021-05-02 20:33:57,362 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:33:57,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:57,412 INFO L263 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 62 conjunts are in the unsatisfiable core [2021-05-02 20:33:57,413 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:57,444 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:57,445 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:57,500 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:57,506 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:57,521 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:57,523 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:57,549 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:57,550 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:57,559 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:57,560 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:57,688 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:57,689 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:57,721 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 16 proven. 14 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2021-05-02 20:33:57,721 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:57,721 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [711016012] [2021-05-02 20:33:57,721 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:57,721 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [614735165] [2021-05-02 20:33:57,721 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [614735165] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:33:57,722 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:33:57,722 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2021-05-02 20:33:57,722 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2061509804] [2021-05-02 20:33:57,722 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states [2021-05-02 20:33:57,722 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:57,722 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2021-05-02 20:33:57,722 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=200, Unknown=0, NotChecked=0, Total=240 [2021-05-02 20:33:57,723 INFO L87 Difference]: Start difference. First operand 92 states and 121 transitions. Second operand has 16 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 14 states have internal predecessors, (32), 4 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2021-05-02 20:33:58,242 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:58,242 INFO L93 Difference]: Finished difference Result 164 states and 219 transitions. [2021-05-02 20:33:58,242 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2021-05-02 20:33:58,242 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 14 states have internal predecessors, (32), 4 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 64 [2021-05-02 20:33:58,242 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:58,243 INFO L225 Difference]: With dead ends: 164 [2021-05-02 20:33:58,243 INFO L226 Difference]: Without dead ends: 163 [2021-05-02 20:33:58,244 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 48 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 84 ImplicationChecksByTransitivity, 339.8ms TimeCoverageRelationStatistics Valid=86, Invalid=466, Unknown=0, NotChecked=0, Total=552 [2021-05-02 20:33:58,244 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states. [2021-05-02 20:33:58,248 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 160. [2021-05-02 20:33:58,248 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 160 states, 92 states have (on average 1.1521739130434783) internal successors, (106), 98 states have internal predecessors, (106), 55 states have call successors, (55), 13 states have call predecessors, (55), 12 states have return successors, (53), 48 states have call predecessors, (53), 53 states have call successors, (53) [2021-05-02 20:33:58,250 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 160 states to 160 states and 214 transitions. [2021-05-02 20:33:58,250 INFO L78 Accepts]: Start accepts. Automaton has 160 states and 214 transitions. Word has length 64 [2021-05-02 20:33:58,251 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:58,251 INFO L480 AbstractCegarLoop]: Abstraction has 160 states and 214 transitions. [2021-05-02 20:33:58,251 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 16 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 14 states have internal predecessors, (32), 4 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2021-05-02 20:33:58,251 INFO L276 IsEmpty]: Start isEmpty. Operand 160 states and 214 transitions. [2021-05-02 20:33:58,252 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2021-05-02 20:33:58,252 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:58,252 INFO L523 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:58,460 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2021-05-02 20:33:58,461 INFO L428 AbstractCegarLoop]: === Iteration 13 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:58,461 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:58,461 INFO L82 PathProgramCache]: Analyzing trace with hash 1523533001, now seen corresponding path program 2 times [2021-05-02 20:33:58,461 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:58,461 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1350483989] [2021-05-02 20:33:58,461 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:58,467 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:58,467 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [402705906] [2021-05-02 20:33:58,467 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 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:33:58,520 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-02 20:33:58,520 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-02 20:33:58,521 INFO L263 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 8 conjunts are in the unsatisfiable core [2021-05-02 20:33:58,521 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:58,553 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,555 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,555 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,560 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,566 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,572 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,572 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,578 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,578 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,583 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,584 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,590 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,591 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,598 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,599 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,608 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:58,618 INFO L134 CoverageAnalysis]: Checked inductivity of 69 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2021-05-02 20:33:58,618 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:58,618 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1350483989] [2021-05-02 20:33:58,618 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:58,618 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [402705906] [2021-05-02 20:33:58,618 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [402705906] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:33:58,618 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:33:58,619 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2021-05-02 20:33:58,619 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1698632655] [2021-05-02 20:33:58,619 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2021-05-02 20:33:58,619 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:58,619 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-05-02 20:33:58,619 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2021-05-02 20:33:58,620 INFO L87 Difference]: Start difference. First operand 160 states and 214 transitions. Second operand has 8 states, 8 states have (on average 3.875) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2021-05-02 20:33:58,835 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:58,835 INFO L93 Difference]: Finished difference Result 270 states and 396 transitions. [2021-05-02 20:33:58,835 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2021-05-02 20:33:58,836 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.875) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 69 [2021-05-02 20:33:58,836 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:58,839 INFO L225 Difference]: With dead ends: 270 [2021-05-02 20:33:58,839 INFO L226 Difference]: Without dead ends: 270 [2021-05-02 20:33:58,839 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 96.0ms TimeCoverageRelationStatistics Valid=93, Invalid=249, Unknown=0, NotChecked=0, Total=342 [2021-05-02 20:33:58,839 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 270 states. [2021-05-02 20:33:58,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 270 to 185. [2021-05-02 20:33:58,853 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 185 states, 109 states have (on average 1.18348623853211) internal successors, (129), 114 states have internal predecessors, (129), 63 states have call successors, (63), 13 states have call predecessors, (63), 12 states have return successors, (61), 57 states have call predecessors, (61), 61 states have call successors, (61) [2021-05-02 20:33:58,854 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 185 states to 185 states and 253 transitions. [2021-05-02 20:33:58,854 INFO L78 Accepts]: Start accepts. Automaton has 185 states and 253 transitions. Word has length 69 [2021-05-02 20:33:58,854 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:58,855 INFO L480 AbstractCegarLoop]: Abstraction has 185 states and 253 transitions. [2021-05-02 20:33:58,855 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 8 states, 8 states have (on average 3.875) internal successors, (31), 8 states have internal predecessors, (31), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2021-05-02 20:33:58,855 INFO L276 IsEmpty]: Start isEmpty. Operand 185 states and 253 transitions. [2021-05-02 20:33:58,858 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2021-05-02 20:33:58,859 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:58,859 INFO L523 BasicCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:59,074 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2021-05-02 20:33:59,074 INFO L428 AbstractCegarLoop]: === Iteration 14 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:59,075 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:59,075 INFO L82 PathProgramCache]: Analyzing trace with hash 696944608, now seen corresponding path program 1 times [2021-05-02 20:33:59,075 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:59,075 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1091014105] [2021-05-02 20:33:59,075 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:59,080 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:59,080 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1684990999] [2021-05-02 20:33:59,080 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:33:59,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:59,128 INFO L263 TraceCheckSpWp]: Trace formula consists of 220 conjuncts, 27 conjunts are in the unsatisfiable core [2021-05-02 20:33:59,129 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:59,151 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,152 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,158 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,159 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,165 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,166 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,179 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,179 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,188 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,209 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,209 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,210 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,210 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,217 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,217 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,218 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,219 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,224 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,225 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,226 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,227 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,243 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,244 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,244 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,245 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,256 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,290 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,291 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,301 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,302 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,314 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,315 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,326 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,328 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,331 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,334 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,336 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,338 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,340 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,360 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 20 proven. 11 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2021-05-02 20:33:59,360 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:59,360 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1091014105] [2021-05-02 20:33:59,360 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:59,360 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1684990999] [2021-05-02 20:33:59,360 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1684990999] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:33:59,360 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:33:59,360 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2021-05-02 20:33:59,360 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [776525216] [2021-05-02 20:33:59,361 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2021-05-02 20:33:59,361 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:59,361 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-05-02 20:33:59,361 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=109, Unknown=0, NotChecked=0, Total=132 [2021-05-02 20:33:59,361 INFO L87 Difference]: Start difference. First operand 185 states and 253 transitions. Second operand has 12 states, 12 states have (on average 2.0) internal successors, (24), 10 states have internal predecessors, (24), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 5 states have call predecessors, (12), 4 states have call successors, (12) [2021-05-02 20:33:59,577 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:33:59,577 INFO L93 Difference]: Finished difference Result 195 states and 262 transitions. [2021-05-02 20:33:59,577 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-05-02 20:33:59,577 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.0) internal successors, (24), 10 states have internal predecessors, (24), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 5 states have call predecessors, (12), 4 states have call successors, (12) Word has length 74 [2021-05-02 20:33:59,578 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:33:59,579 INFO L225 Difference]: With dead ends: 195 [2021-05-02 20:33:59,579 INFO L226 Difference]: Without dead ends: 195 [2021-05-02 20:33:59,579 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 63 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 126.4ms TimeCoverageRelationStatistics Valid=61, Invalid=245, Unknown=0, NotChecked=0, Total=306 [2021-05-02 20:33:59,580 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 195 states. [2021-05-02 20:33:59,583 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 195 to 188. [2021-05-02 20:33:59,583 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 188 states, 112 states have (on average 1.1696428571428572) internal successors, (131), 117 states have internal predecessors, (131), 62 states have call successors, (62), 14 states have call predecessors, (62), 13 states have return successors, (60), 56 states have call predecessors, (60), 60 states have call successors, (60) [2021-05-02 20:33:59,584 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 188 states to 188 states and 253 transitions. [2021-05-02 20:33:59,584 INFO L78 Accepts]: Start accepts. Automaton has 188 states and 253 transitions. Word has length 74 [2021-05-02 20:33:59,584 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:33:59,584 INFO L480 AbstractCegarLoop]: Abstraction has 188 states and 253 transitions. [2021-05-02 20:33:59,585 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 12 states, 12 states have (on average 2.0) internal successors, (24), 10 states have internal predecessors, (24), 4 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 5 states have call predecessors, (12), 4 states have call successors, (12) [2021-05-02 20:33:59,585 INFO L276 IsEmpty]: Start isEmpty. Operand 188 states and 253 transitions. [2021-05-02 20:33:59,585 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2021-05-02 20:33:59,585 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:33:59,585 INFO L523 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:33:59,801 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2021-05-02 20:33:59,801 INFO L428 AbstractCegarLoop]: === Iteration 15 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:33:59,801 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:33:59,801 INFO L82 PathProgramCache]: Analyzing trace with hash -2010106522, now seen corresponding path program 1 times [2021-05-02 20:33:59,801 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:33:59,801 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1991210201] [2021-05-02 20:33:59,801 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:33:59,807 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:33:59,807 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [25402443] [2021-05-02 20:33:59,807 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:33:59,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:33:59,854 INFO L263 TraceCheckSpWp]: Trace formula consists of 243 conjuncts, 12 conjunts are in the unsatisfiable core [2021-05-02 20:33:59,855 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:33:59,880 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,881 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,887 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,887 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,893 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,910 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,911 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,911 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,922 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,935 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,946 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,947 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,953 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,954 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,961 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,962 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,969 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,970 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,977 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:33:59,988 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 30 proven. 6 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2021-05-02 20:33:59,989 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:33:59,989 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1991210201] [2021-05-02 20:33:59,989 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:33:59,989 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [25402443] [2021-05-02 20:33:59,989 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [25402443] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:33:59,989 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:33:59,989 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2021-05-02 20:33:59,989 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2018871616] [2021-05-02 20:33:59,989 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states [2021-05-02 20:33:59,989 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:33:59,990 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-05-02 20:33:59,990 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2021-05-02 20:33:59,990 INFO L87 Difference]: Start difference. First operand 188 states and 253 transitions. Second operand has 10 states, 10 states have (on average 3.6) internal successors, (36), 9 states have internal predecessors, (36), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2021-05-02 20:34:00,187 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:34:00,187 INFO L93 Difference]: Finished difference Result 192 states and 261 transitions. [2021-05-02 20:34:00,188 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-05-02 20:34:00,188 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.6) internal successors, (36), 9 states have internal predecessors, (36), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 72 [2021-05-02 20:34:00,188 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:34:00,191 INFO L225 Difference]: With dead ends: 192 [2021-05-02 20:34:00,191 INFO L226 Difference]: Without dead ends: 192 [2021-05-02 20:34:00,192 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 63 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 110.0ms TimeCoverageRelationStatistics Valid=67, Invalid=205, Unknown=0, NotChecked=0, Total=272 [2021-05-02 20:34:00,192 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 192 states. [2021-05-02 20:34:00,199 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 192 to 176. [2021-05-02 20:34:00,200 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 176 states, 100 states have (on average 1.13) internal successors, (113), 105 states have internal predecessors, (113), 62 states have call successors, (62), 14 states have call predecessors, (62), 13 states have return successors, (60), 56 states have call predecessors, (60), 60 states have call successors, (60) [2021-05-02 20:34:00,201 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 176 states to 176 states and 235 transitions. [2021-05-02 20:34:00,201 INFO L78 Accepts]: Start accepts. Automaton has 176 states and 235 transitions. Word has length 72 [2021-05-02 20:34:00,201 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:34:00,201 INFO L480 AbstractCegarLoop]: Abstraction has 176 states and 235 transitions. [2021-05-02 20:34:00,201 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 10 states, 10 states have (on average 3.6) internal successors, (36), 9 states have internal predecessors, (36), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2021-05-02 20:34:00,201 INFO L276 IsEmpty]: Start isEmpty. Operand 176 states and 235 transitions. [2021-05-02 20:34:00,202 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2021-05-02 20:34:00,202 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:34:00,202 INFO L523 BasicCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:34:00,416 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,15 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:34:00,417 INFO L428 AbstractCegarLoop]: === Iteration 16 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:34:00,417 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:34:00,417 INFO L82 PathProgramCache]: Analyzing trace with hash 1813106047, now seen corresponding path program 2 times [2021-05-02 20:34:00,417 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:34:00,417 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [54778958] [2021-05-02 20:34:00,417 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:34:00,422 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:34:00,422 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1376537052] [2021-05-02 20:34:00,423 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:34:00,477 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-02 20:34:00,477 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-02 20:34:00,477 INFO L263 TraceCheckSpWp]: Trace formula consists of 239 conjuncts, 15 conjunts are in the unsatisfiable core [2021-05-02 20:34:00,479 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:34:00,500 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,501 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,508 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,508 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,514 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,515 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,521 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,529 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,537 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,549 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,550 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,556 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,557 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,563 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,564 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,570 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,570 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,588 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,611 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:00,626 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 50 proven. 11 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2021-05-02 20:34:00,626 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:34:00,626 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [54778958] [2021-05-02 20:34:00,627 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:34:00,627 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1376537052] [2021-05-02 20:34:00,627 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1376537052] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:34:00,627 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:34:00,627 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2021-05-02 20:34:00,627 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1080567623] [2021-05-02 20:34:00,627 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2021-05-02 20:34:00,627 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:34:00,627 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-05-02 20:34:00,628 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2021-05-02 20:34:00,628 INFO L87 Difference]: Start difference. First operand 176 states and 235 transitions. Second operand has 11 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2021-05-02 20:34:00,834 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:34:00,834 INFO L93 Difference]: Finished difference Result 156 states and 200 transitions. [2021-05-02 20:34:00,834 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2021-05-02 20:34:00,835 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) Word has length 77 [2021-05-02 20:34:00,835 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:34:00,836 INFO L225 Difference]: With dead ends: 156 [2021-05-02 20:34:00,836 INFO L226 Difference]: Without dead ends: 148 [2021-05-02 20:34:00,837 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 50 ImplicationChecksByTransitivity, 139.8ms TimeCoverageRelationStatistics Valid=95, Invalid=325, Unknown=0, NotChecked=0, Total=420 [2021-05-02 20:34:00,837 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 148 states. [2021-05-02 20:34:00,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 148 to 147. [2021-05-02 20:34:00,840 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 147 states, 84 states have (on average 1.1071428571428572) internal successors, (93), 88 states have internal predecessors, (93), 50 states have call successors, (50), 13 states have call predecessors, (50), 12 states have return successors, (47), 45 states have call predecessors, (47), 47 states have call successors, (47) [2021-05-02 20:34:00,840 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 147 states to 147 states and 190 transitions. [2021-05-02 20:34:00,841 INFO L78 Accepts]: Start accepts. Automaton has 147 states and 190 transitions. Word has length 77 [2021-05-02 20:34:00,841 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:34:00,841 INFO L480 AbstractCegarLoop]: Abstraction has 147 states and 190 transitions. [2021-05-02 20:34:00,841 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 11 states, 11 states have (on average 3.090909090909091) internal successors, (34), 11 states have internal predecessors, (34), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2021-05-02 20:34:00,841 INFO L276 IsEmpty]: Start isEmpty. Operand 147 states and 190 transitions. [2021-05-02 20:34:00,841 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2021-05-02 20:34:00,841 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:34:00,842 INFO L523 BasicCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:34:01,057 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable20 [2021-05-02 20:34:01,058 INFO L428 AbstractCegarLoop]: === Iteration 17 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:34:01,058 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:34:01,058 INFO L82 PathProgramCache]: Analyzing trace with hash -747783847, now seen corresponding path program 1 times [2021-05-02 20:34:01,058 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:34:01,058 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [684124074] [2021-05-02 20:34:01,058 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:34:01,071 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:34:01,071 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [405178562] [2021-05-02 20:34:01,071 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:34:01,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:34:01,127 INFO L263 TraceCheckSpWp]: Trace formula consists of 242 conjuncts, 35 conjunts are in the unsatisfiable core [2021-05-02 20:34:01,128 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:34:01,147 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,148 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,161 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,162 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,162 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,163 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,177 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,178 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,178 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,179 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,185 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,185 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,194 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,203 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,237 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,238 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,244 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,245 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,251 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,252 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,259 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,260 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,283 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,284 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,292 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,293 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,300 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,301 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,307 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,308 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:01,329 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 14 proven. 18 refuted. 0 times theorem prover too weak. 99 trivial. 0 not checked. [2021-05-02 20:34:01,329 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:34:01,329 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [684124074] [2021-05-02 20:34:01,329 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:34:01,329 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [405178562] [2021-05-02 20:34:01,329 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [405178562] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:34:01,329 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:34:01,329 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2021-05-02 20:34:01,329 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1600517279] [2021-05-02 20:34:01,329 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states [2021-05-02 20:34:01,329 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:34:01,330 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2021-05-02 20:34:01,330 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=178, Unknown=0, NotChecked=0, Total=210 [2021-05-02 20:34:01,330 INFO L87 Difference]: Start difference. First operand 147 states and 190 transitions. Second operand has 15 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 12 states have internal predecessors, (29), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) [2021-05-02 20:34:01,826 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:34:01,826 INFO L93 Difference]: Finished difference Result 177 states and 231 transitions. [2021-05-02 20:34:01,826 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2021-05-02 20:34:01,826 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 12 states have internal predecessors, (29), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) Word has length 79 [2021-05-02 20:34:01,826 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:34:01,827 INFO L225 Difference]: With dead ends: 177 [2021-05-02 20:34:01,827 INFO L226 Difference]: Without dead ends: 177 [2021-05-02 20:34:01,827 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 103 ImplicationChecksByTransitivity, 295.5ms TimeCoverageRelationStatistics Valid=140, Invalid=616, Unknown=0, NotChecked=0, Total=756 [2021-05-02 20:34:01,828 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2021-05-02 20:34:01,830 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 166. [2021-05-02 20:34:01,831 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 166 states, 93 states have (on average 1.10752688172043) internal successors, (103), 98 states have internal predecessors, (103), 58 states have call successors, (58), 15 states have call predecessors, (58), 14 states have return successors, (55), 52 states have call predecessors, (55), 55 states have call successors, (55) [2021-05-02 20:34:01,831 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 166 states to 166 states and 216 transitions. [2021-05-02 20:34:01,831 INFO L78 Accepts]: Start accepts. Automaton has 166 states and 216 transitions. Word has length 79 [2021-05-02 20:34:01,831 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:34:01,831 INFO L480 AbstractCegarLoop]: Abstraction has 166 states and 216 transitions. [2021-05-02 20:34:01,832 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 15 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 12 states have internal predecessors, (29), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) [2021-05-02 20:34:01,832 INFO L276 IsEmpty]: Start isEmpty. Operand 166 states and 216 transitions. [2021-05-02 20:34:01,832 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2021-05-02 20:34:01,832 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:34:01,832 INFO L523 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:34:02,041 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,17 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:34:02,041 INFO L428 AbstractCegarLoop]: === Iteration 18 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:34:02,041 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:34:02,041 INFO L82 PathProgramCache]: Analyzing trace with hash 131640819, now seen corresponding path program 1 times [2021-05-02 20:34:02,041 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:34:02,041 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1595257357] [2021-05-02 20:34:02,042 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:34:02,051 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:34:02,051 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [877681312] [2021-05-02 20:34:02,052 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:34:02,094 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:34:02,095 INFO L263 TraceCheckSpWp]: Trace formula consists of 253 conjuncts, 81 conjunts are in the unsatisfiable core [2021-05-02 20:34:02,097 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:34:02,118 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,119 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,125 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,126 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,138 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,139 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,219 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,220 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,228 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,228 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,237 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,238 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,246 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,247 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,304 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,306 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,315 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,316 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,340 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,342 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,349 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,350 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,535 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,536 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:02,557 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 52 proven. 31 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2021-05-02 20:34:02,557 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:34:02,557 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1595257357] [2021-05-02 20:34:02,557 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:34:02,557 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [877681312] [2021-05-02 20:34:02,557 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [877681312] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:34:02,557 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:34:02,558 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2021-05-02 20:34:02,558 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [147221867] [2021-05-02 20:34:02,560 INFO L460 AbstractCegarLoop]: Interpolant automaton has 18 states [2021-05-02 20:34:02,560 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:34:02,560 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2021-05-02 20:34:02,560 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=251, Unknown=0, NotChecked=0, Total=306 [2021-05-02 20:34:02,560 INFO L87 Difference]: Start difference. First operand 166 states and 216 transitions. Second operand has 18 states, 17 states have (on average 2.0) internal successors, (34), 16 states have internal predecessors, (34), 6 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2021-05-02 20:34:02,997 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:34:02,997 INFO L93 Difference]: Finished difference Result 171 states and 220 transitions. [2021-05-02 20:34:02,997 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2021-05-02 20:34:02,997 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.0) internal successors, (34), 16 states have internal predecessors, (34), 6 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 86 [2021-05-02 20:34:02,997 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:34:02,998 INFO L225 Difference]: With dead ends: 171 [2021-05-02 20:34:02,998 INFO L226 Difference]: Without dead ends: 118 [2021-05-02 20:34:02,998 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 66 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 104 ImplicationChecksByTransitivity, 425.7ms TimeCoverageRelationStatistics Valid=106, Invalid=544, Unknown=0, NotChecked=0, Total=650 [2021-05-02 20:34:02,999 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2021-05-02 20:34:03,001 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 118. [2021-05-02 20:34:03,001 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 65 states have (on average 1.123076923076923) internal successors, (73), 69 states have internal predecessors, (73), 43 states have call successors, (43), 10 states have call predecessors, (43), 9 states have return successors, (41), 38 states have call predecessors, (41), 41 states have call successors, (41) [2021-05-02 20:34:03,001 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 157 transitions. [2021-05-02 20:34:03,002 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 157 transitions. Word has length 86 [2021-05-02 20:34:03,002 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:34:03,002 INFO L480 AbstractCegarLoop]: Abstraction has 118 states and 157 transitions. [2021-05-02 20:34:03,002 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 18 states, 17 states have (on average 2.0) internal successors, (34), 16 states have internal predecessors, (34), 6 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2021-05-02 20:34:03,002 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 157 transitions. [2021-05-02 20:34:03,002 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2021-05-02 20:34:03,002 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:34:03,003 INFO L523 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:34:03,217 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable22 [2021-05-02 20:34:03,217 INFO L428 AbstractCegarLoop]: === Iteration 19 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:34:03,217 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:34:03,217 INFO L82 PathProgramCache]: Analyzing trace with hash -983010836, now seen corresponding path program 2 times [2021-05-02 20:34:03,217 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:34:03,217 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [588847816] [2021-05-02 20:34:03,217 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:34:03,222 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:34:03,223 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1613078033] [2021-05-02 20:34:03,223 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 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:34:03,273 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-02 20:34:03,273 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-02 20:34:03,275 INFO L263 TraceCheckSpWp]: Trace formula consists of 275 conjuncts, 96 conjunts are in the unsatisfiable core [2021-05-02 20:34:03,276 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:34:03,308 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,308 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,462 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,463 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,470 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,471 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,480 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,481 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,488 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,489 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,525 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,526 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,595 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,630 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,643 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,835 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,837 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:03,866 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 58 proven. 31 refuted. 0 times theorem prover too weak. 82 trivial. 0 not checked. [2021-05-02 20:34:03,866 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:34:03,866 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [588847816] [2021-05-02 20:34:03,866 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:34:03,866 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1613078033] [2021-05-02 20:34:03,866 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1613078033] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:34:03,866 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:34:03,866 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2021-05-02 20:34:03,866 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1930083028] [2021-05-02 20:34:03,867 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2021-05-02 20:34:03,867 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:34:03,867 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-05-02 20:34:03,867 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=360, Unknown=0, NotChecked=0, Total=420 [2021-05-02 20:34:03,867 INFO L87 Difference]: Start difference. First operand 118 states and 157 transitions. Second operand has 21 states, 20 states have (on average 1.95) internal successors, (39), 19 states have internal predecessors, (39), 6 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (13), 4 states have call predecessors, (13), 5 states have call successors, (13) [2021-05-02 20:34:04,535 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:34:04,535 INFO L93 Difference]: Finished difference Result 181 states and 248 transitions. [2021-05-02 20:34:04,536 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2021-05-02 20:34:04,536 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 1.95) internal successors, (39), 19 states have internal predecessors, (39), 6 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (13), 4 states have call predecessors, (13), 5 states have call successors, (13) Word has length 91 [2021-05-02 20:34:04,536 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:34:04,537 INFO L225 Difference]: With dead ends: 181 [2021-05-02 20:34:04,537 INFO L226 Difference]: Without dead ends: 180 [2021-05-02 20:34:04,537 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 69 SyntacticMatches, 2 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 166 ImplicationChecksByTransitivity, 556.2ms TimeCoverageRelationStatistics Valid=104, Invalid=708, Unknown=0, NotChecked=0, Total=812 [2021-05-02 20:34:04,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 180 states. [2021-05-02 20:34:04,540 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 180 to 176. [2021-05-02 20:34:04,541 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 176 states, 96 states have (on average 1.1458333333333333) internal successors, (110), 101 states have internal predecessors, (110), 67 states have call successors, (67), 13 states have call predecessors, (67), 12 states have return successors, (65), 61 states have call predecessors, (65), 65 states have call successors, (65) [2021-05-02 20:34:04,541 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 176 states to 176 states and 242 transitions. [2021-05-02 20:34:04,542 INFO L78 Accepts]: Start accepts. Automaton has 176 states and 242 transitions. Word has length 91 [2021-05-02 20:34:04,542 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:34:04,542 INFO L480 AbstractCegarLoop]: Abstraction has 176 states and 242 transitions. [2021-05-02 20:34:04,542 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 21 states, 20 states have (on average 1.95) internal successors, (39), 19 states have internal predecessors, (39), 6 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (13), 4 states have call predecessors, (13), 5 states have call successors, (13) [2021-05-02 20:34:04,542 INFO L276 IsEmpty]: Start isEmpty. Operand 176 states and 242 transitions. [2021-05-02 20:34:04,542 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2021-05-02 20:34:04,542 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:34:04,542 INFO L523 BasicCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:34:04,759 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable23 [2021-05-02 20:34:04,759 INFO L428 AbstractCegarLoop]: === Iteration 20 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:34:04,760 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:34:04,760 INFO L82 PathProgramCache]: Analyzing trace with hash 561452732, now seen corresponding path program 2 times [2021-05-02 20:34:04,760 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:34:04,760 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1109139527] [2021-05-02 20:34:04,760 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:34:04,765 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:34:04,765 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [996961335] [2021-05-02 20:34:04,765 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 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:34:04,945 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-02 20:34:04,946 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-02 20:34:04,947 INFO L263 TraceCheckSpWp]: Trace formula consists of 284 conjuncts, 19 conjunts are in the unsatisfiable core [2021-05-02 20:34:04,948 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:34:04,974 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:04,975 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:04,988 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:04,989 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:04,989 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:04,990 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:04,997 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:04,998 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,014 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,026 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,027 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,027 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,053 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,065 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,077 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,078 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,078 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,079 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,085 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,086 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,087 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,087 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,094 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,095 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,095 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,096 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,103 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,104 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,104 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,105 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,112 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,113 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,131 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,141 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,142 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,142 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,143 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,143 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,151 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,152 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,153 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,153 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,154 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,154 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,161 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,163 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,163 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,164 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,164 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,165 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,190 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,191 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,192 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,193 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,193 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,193 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,202 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,203 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,204 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,222 INFO L134 CoverageAnalysis]: Checked inductivity of 286 backedges. 134 proven. 10 refuted. 0 times theorem prover too weak. 142 trivial. 0 not checked. [2021-05-02 20:34:05,222 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:34:05,222 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1109139527] [2021-05-02 20:34:05,222 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:34:05,222 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [996961335] [2021-05-02 20:34:05,222 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [996961335] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:34:05,223 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:34:05,223 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2021-05-02 20:34:05,223 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1641266710] [2021-05-02 20:34:05,223 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2021-05-02 20:34:05,224 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:34:05,224 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-05-02 20:34:05,224 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=109, Unknown=0, NotChecked=0, Total=132 [2021-05-02 20:34:05,224 INFO L87 Difference]: Start difference. First operand 176 states and 242 transitions. Second operand has 12 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 6 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2021-05-02 20:34:05,541 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:34:05,541 INFO L93 Difference]: Finished difference Result 208 states and 285 transitions. [2021-05-02 20:34:05,541 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2021-05-02 20:34:05,542 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 6 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 101 [2021-05-02 20:34:05,543 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:34:05,544 INFO L225 Difference]: With dead ends: 208 [2021-05-02 20:34:05,544 INFO L226 Difference]: Without dead ends: 208 [2021-05-02 20:34:05,545 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 90 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 50 ImplicationChecksByTransitivity, 201.6ms TimeCoverageRelationStatistics Valid=132, Invalid=374, Unknown=0, NotChecked=0, Total=506 [2021-05-02 20:34:05,545 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 208 states. [2021-05-02 20:34:05,549 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 208 to 158. [2021-05-02 20:34:05,549 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 158 states, 91 states have (on average 1.10989010989011) internal successors, (101), 95 states have internal predecessors, (101), 54 states have call successors, (54), 13 states have call predecessors, (54), 12 states have return successors, (52), 49 states have call predecessors, (52), 52 states have call successors, (52) [2021-05-02 20:34:05,550 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 207 transitions. [2021-05-02 20:34:05,550 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 207 transitions. Word has length 101 [2021-05-02 20:34:05,550 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:34:05,550 INFO L480 AbstractCegarLoop]: Abstraction has 158 states and 207 transitions. [2021-05-02 20:34:05,550 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 12 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 6 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2021-05-02 20:34:05,551 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 207 transitions. [2021-05-02 20:34:05,551 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2021-05-02 20:34:05,551 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:34:05,551 INFO L523 BasicCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:34:05,768 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 20 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable24 [2021-05-02 20:34:05,769 INFO L428 AbstractCegarLoop]: === Iteration 21 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:34:05,769 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:34:05,769 INFO L82 PathProgramCache]: Analyzing trace with hash -1651080925, now seen corresponding path program 1 times [2021-05-02 20:34:05,769 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:34:05,769 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [615833974] [2021-05-02 20:34:05,769 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:34:05,774 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:34:05,774 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1347197785] [2021-05-02 20:34:05,774 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:34:05,828 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-05-02 20:34:05,829 INFO L263 TraceCheckSpWp]: Trace formula consists of 303 conjuncts, 27 conjunts are in the unsatisfiable core [2021-05-02 20:34:05,830 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:34:05,855 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,856 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,863 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,863 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,871 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,922 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,923 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,931 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,932 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,939 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,940 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,947 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,948 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,970 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,971 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,978 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,978 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,985 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,985 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,991 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:05,992 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,013 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,053 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,087 INFO L134 CoverageAnalysis]: Checked inductivity of 257 backedges. 105 proven. 17 refuted. 0 times theorem prover too weak. 135 trivial. 0 not checked. [2021-05-02 20:34:06,087 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:34:06,087 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [615833974] [2021-05-02 20:34:06,087 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:34:06,087 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1347197785] [2021-05-02 20:34:06,088 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1347197785] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:34:06,088 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:34:06,088 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2021-05-02 20:34:06,088 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [679799116] [2021-05-02 20:34:06,088 INFO L460 AbstractCegarLoop]: Interpolant automaton has 14 states [2021-05-02 20:34:06,088 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:34:06,088 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-05-02 20:34:06,089 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=148, Unknown=0, NotChecked=0, Total=182 [2021-05-02 20:34:06,089 INFO L87 Difference]: Start difference. First operand 158 states and 207 transitions. Second operand has 14 states, 14 states have (on average 2.9285714285714284) internal successors, (41), 13 states have internal predecessors, (41), 5 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2021-05-02 20:34:06,458 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:34:06,458 INFO L93 Difference]: Finished difference Result 171 states and 226 transitions. [2021-05-02 20:34:06,458 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2021-05-02 20:34:06,459 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.9285714285714284) internal successors, (41), 13 states have internal predecessors, (41), 5 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) Word has length 104 [2021-05-02 20:34:06,459 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:34:06,459 INFO L225 Difference]: With dead ends: 171 [2021-05-02 20:34:06,459 INFO L226 Difference]: Without dead ends: 168 [2021-05-02 20:34:06,460 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 76 ImplicationChecksByTransitivity, 265.9ms TimeCoverageRelationStatistics Valid=130, Invalid=520, Unknown=0, NotChecked=0, Total=650 [2021-05-02 20:34:06,460 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states. [2021-05-02 20:34:06,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 145. [2021-05-02 20:34:06,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 145 states, 86 states have (on average 1.1046511627906976) internal successors, (95), 89 states have internal predecessors, (95), 46 states have call successors, (46), 13 states have call predecessors, (46), 12 states have return successors, (44), 42 states have call predecessors, (44), 44 states have call successors, (44) [2021-05-02 20:34:06,463 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 145 states to 145 states and 185 transitions. [2021-05-02 20:34:06,463 INFO L78 Accepts]: Start accepts. Automaton has 145 states and 185 transitions. Word has length 104 [2021-05-02 20:34:06,463 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:34:06,463 INFO L480 AbstractCegarLoop]: Abstraction has 145 states and 185 transitions. [2021-05-02 20:34:06,463 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 14 states, 14 states have (on average 2.9285714285714284) internal successors, (41), 13 states have internal predecessors, (41), 5 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2021-05-02 20:34:06,463 INFO L276 IsEmpty]: Start isEmpty. Operand 145 states and 185 transitions. [2021-05-02 20:34:06,464 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2021-05-02 20:34:06,464 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:34:06,464 INFO L523 BasicCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:34:06,680 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable25 [2021-05-02 20:34:06,680 INFO L428 AbstractCegarLoop]: === Iteration 22 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:34:06,681 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:34:06,681 INFO L82 PathProgramCache]: Analyzing trace with hash 1706790864, now seen corresponding path program 3 times [2021-05-02 20:34:06,681 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:34:06,681 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [515677105] [2021-05-02 20:34:06,681 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:34:06,686 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:34:06,686 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1417386317] [2021-05-02 20:34:06,686 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 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:34:06,739 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2021-05-02 20:34:06,740 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-02 20:34:06,741 INFO L263 TraceCheckSpWp]: Trace formula consists of 236 conjuncts, 14 conjunts are in the unsatisfiable core [2021-05-02 20:34:06,742 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:34:06,769 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,770 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,777 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,778 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,785 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,795 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,796 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,803 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,813 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,813 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,819 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,819 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,824 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,825 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,830 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,831 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,841 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,842 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,847 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,848 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,853 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,854 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,860 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,862 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,877 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,879 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,888 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,899 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,900 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,906 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,907 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,912 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,913 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,919 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,920 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,929 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,940 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:06,956 INFO L134 CoverageAnalysis]: Checked inductivity of 350 backedges. 33 proven. 32 refuted. 0 times theorem prover too weak. 285 trivial. 0 not checked. [2021-05-02 20:34:06,956 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:34:06,956 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [515677105] [2021-05-02 20:34:06,956 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:34:06,956 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1417386317] [2021-05-02 20:34:06,956 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1417386317] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:34:06,956 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:34:06,956 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2021-05-02 20:34:06,956 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1759717755] [2021-05-02 20:34:06,957 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2021-05-02 20:34:06,957 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:34:06,957 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-05-02 20:34:06,957 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2021-05-02 20:34:06,958 INFO L87 Difference]: Start difference. First operand 145 states and 185 transitions. Second operand has 13 states, 13 states have (on average 3.076923076923077) internal successors, (40), 12 states have internal predecessors, (40), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2021-05-02 20:34:07,308 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:34:07,308 INFO L93 Difference]: Finished difference Result 171 states and 226 transitions. [2021-05-02 20:34:07,308 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2021-05-02 20:34:07,308 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 3.076923076923077) internal successors, (40), 12 states have internal predecessors, (40), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) Word has length 116 [2021-05-02 20:34:07,309 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:34:07,309 INFO L225 Difference]: With dead ends: 171 [2021-05-02 20:34:07,309 INFO L226 Difference]: Without dead ends: 168 [2021-05-02 20:34:07,310 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 104 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 232.6ms TimeCoverageRelationStatistics Valid=215, Invalid=541, Unknown=0, NotChecked=0, Total=756 [2021-05-02 20:34:07,310 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states. [2021-05-02 20:34:07,312 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 141. [2021-05-02 20:34:07,312 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 141 states, 83 states have (on average 1.0843373493975903) internal successors, (90), 85 states have internal predecessors, (90), 45 states have call successors, (45), 13 states have call predecessors, (45), 12 states have return successors, (44), 42 states have call predecessors, (44), 44 states have call successors, (44) [2021-05-02 20:34:07,313 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 141 states to 141 states and 179 transitions. [2021-05-02 20:34:07,313 INFO L78 Accepts]: Start accepts. Automaton has 141 states and 179 transitions. Word has length 116 [2021-05-02 20:34:07,313 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:34:07,313 INFO L480 AbstractCegarLoop]: Abstraction has 141 states and 179 transitions. [2021-05-02 20:34:07,313 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 13 states, 13 states have (on average 3.076923076923077) internal successors, (40), 12 states have internal predecessors, (40), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2021-05-02 20:34:07,313 INFO L276 IsEmpty]: Start isEmpty. Operand 141 states and 179 transitions. [2021-05-02 20:34:07,314 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2021-05-02 20:34:07,314 INFO L515 BasicCegarLoop]: Found error trace [2021-05-02 20:34:07,314 INFO L523 BasicCegarLoop]: trace histogram [13, 12, 12, 5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-05-02 20:34:07,528 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable26 [2021-05-02 20:34:07,529 INFO L428 AbstractCegarLoop]: === Iteration 23 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2021-05-02 20:34:07,529 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-05-02 20:34:07,529 INFO L82 PathProgramCache]: Analyzing trace with hash -1478543105, now seen corresponding path program 2 times [2021-05-02 20:34:07,529 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-05-02 20:34:07,529 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [297653976] [2021-05-02 20:34:07,529 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-05-02 20:34:07,538 ERROR L278 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-05-02 20:34:07,539 INFO L361 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1207949552] [2021-05-02 20:34:07,539 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:34:07,591 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-05-02 20:34:07,591 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-05-02 20:34:07,592 INFO L263 TraceCheckSpWp]: Trace formula consists of 333 conjuncts, 13 conjunts are in the unsatisfiable core [2021-05-02 20:34:07,593 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-05-02 20:34:07,624 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,625 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,632 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,632 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,647 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,658 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,659 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,667 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,688 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,689 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,690 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,690 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,697 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,698 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,698 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,699 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,705 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,705 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,706 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,706 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,712 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,713 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,714 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,714 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,721 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,722 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,735 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,736 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,737 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,737 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,738 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,738 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,745 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,746 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,746 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,747 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,747 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,748 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,754 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,755 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,756 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,757 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,757 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,757 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,764 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,765 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,765 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,766 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,766 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,767 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,791 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,794 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,818 WARN L159 QuantifierPusher]: Ignoring assumption. [2021-05-02 20:34:07,847 INFO L134 CoverageAnalysis]: Checked inductivity of 364 backedges. 183 proven. 18 refuted. 0 times theorem prover too weak. 163 trivial. 0 not checked. [2021-05-02 20:34:07,847 INFO L179 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-05-02 20:34:07,847 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [297653976] [2021-05-02 20:34:07,847 WARN L340 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unknown [2021-05-02 20:34:07,847 INFO L361 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1207949552] [2021-05-02 20:34:07,847 INFO L200 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1207949552] provided 0 perfect and 1 imperfect interpolant sequences [2021-05-02 20:34:07,847 INFO L226 FreeRefinementEngine]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2021-05-02 20:34:07,848 INFO L239 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2021-05-02 20:34:07,848 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1523768936] [2021-05-02 20:34:07,849 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2021-05-02 20:34:07,849 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-05-02 20:34:07,849 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-05-02 20:34:07,849 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2021-05-02 20:34:07,849 INFO L87 Difference]: Start difference. First operand 141 states and 179 transitions. Second operand has 12 states, 12 states have (on average 3.6666666666666665) internal successors, (44), 11 states have internal predecessors, (44), 5 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2021-05-02 20:34:08,030 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-05-02 20:34:08,031 INFO L93 Difference]: Finished difference Result 60 states and 65 transitions. [2021-05-02 20:34:08,031 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-05-02 20:34:08,031 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.6666666666666665) internal successors, (44), 11 states have internal predecessors, (44), 5 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) Word has length 119 [2021-05-02 20:34:08,031 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-05-02 20:34:08,031 INFO L225 Difference]: With dead ends: 60 [2021-05-02 20:34:08,031 INFO L226 Difference]: Without dead ends: 0 [2021-05-02 20:34:08,031 INFO L779 BasicCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 108 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 160.3ms TimeCoverageRelationStatistics Valid=92, Invalid=288, Unknown=0, NotChecked=0, Total=380 [2021-05-02 20:34:08,032 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2021-05-02 20:34:08,032 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2021-05-02 20:34:08,032 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-05-02 20:34:08,032 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2021-05-02 20:34:08,032 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 119 [2021-05-02 20:34:08,032 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-05-02 20:34:08,032 INFO L480 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-05-02 20:34:08,032 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 12 states, 12 states have (on average 3.6666666666666665) internal successors, (44), 11 states have internal predecessors, (44), 5 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2021-05-02 20:34:08,032 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2021-05-02 20:34:08,032 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2021-05-02 20:34:08,233 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable27,23 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-05-02 20:34:08,236 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 02.05 08:34:08 BasicIcfg [2021-05-02 20:34:08,236 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2021-05-02 20:34:08,236 INFO L168 Benchmark]: Toolchain (without parser) took 17830.60 ms. Allocated memory was 209.7 MB in the beginning and 308.3 MB in the end (delta: 98.6 MB). Free memory was 174.9 MB in the beginning and 267.0 MB in the end (delta: -92.1 MB). Peak memory consumption was 7.9 MB. Max. memory is 8.0 GB. [2021-05-02 20:34:08,236 INFO L168 Benchmark]: CDTParser took 0.10 ms. Allocated memory is still 209.7 MB. Free memory is still 192.1 MB. There was no memory consumed. Max. memory is 8.0 GB. [2021-05-02 20:34:08,236 INFO L168 Benchmark]: CACSL2BoogieTranslator took 222.06 ms. Allocated memory is still 209.7 MB. Free memory was 174.7 MB in the beginning and 192.9 MB in the end (delta: -18.2 MB). Peak memory consumption was 12.8 MB. Max. memory is 8.0 GB. [2021-05-02 20:34:08,236 INFO L168 Benchmark]: Boogie Preprocessor took 18.29 ms. Allocated memory is still 209.7 MB. Free memory was 192.9 MB in the beginning and 191.3 MB in the end (delta: 1.6 MB). Peak memory consumption was 2.1 MB. Max. memory is 8.0 GB. [2021-05-02 20:34:08,236 INFO L168 Benchmark]: RCFGBuilder took 306.79 ms. Allocated memory is still 209.7 MB. Free memory was 191.3 MB in the beginning and 174.0 MB in the end (delta: 17.3 MB). Peak memory consumption was 16.8 MB. Max. memory is 8.0 GB. [2021-05-02 20:34:08,236 INFO L168 Benchmark]: IcfgTransformer took 12.94 ms. Allocated memory is still 209.7 MB. Free memory was 174.0 MB in the beginning and 172.9 MB in the end (delta: 1.0 MB). Peak memory consumption was 1.0 MB. Max. memory is 8.0 GB. [2021-05-02 20:34:08,237 INFO L168 Benchmark]: TraceAbstraction took 17263.97 ms. Allocated memory was 209.7 MB in the beginning and 308.3 MB in the end (delta: 98.6 MB). Free memory was 172.4 MB in the beginning and 267.0 MB in the end (delta: -94.6 MB). Peak memory consumption was 4.5 MB. Max. memory is 8.0 GB. [2021-05-02 20:34:08,237 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.10 ms. Allocated memory is still 209.7 MB. Free memory is still 192.1 MB. There was no memory consumed. Max. memory is 8.0 GB. * CACSL2BoogieTranslator took 222.06 ms. Allocated memory is still 209.7 MB. Free memory was 174.7 MB in the beginning and 192.9 MB in the end (delta: -18.2 MB). Peak memory consumption was 12.8 MB. Max. memory is 8.0 GB. * Boogie Preprocessor took 18.29 ms. Allocated memory is still 209.7 MB. Free memory was 192.9 MB in the beginning and 191.3 MB in the end (delta: 1.6 MB). Peak memory consumption was 2.1 MB. Max. memory is 8.0 GB. * RCFGBuilder took 306.79 ms. Allocated memory is still 209.7 MB. Free memory was 191.3 MB in the beginning and 174.0 MB in the end (delta: 17.3 MB). Peak memory consumption was 16.8 MB. Max. memory is 8.0 GB. * IcfgTransformer took 12.94 ms. Allocated memory is still 209.7 MB. Free memory was 174.0 MB in the beginning and 172.9 MB in the end (delta: 1.0 MB). Peak memory consumption was 1.0 MB. Max. memory is 8.0 GB. * TraceAbstraction took 17263.97 ms. Allocated memory was 209.7 MB in the beginning and 308.3 MB in the end (delta: 98.6 MB). Free memory was 172.4 MB in the beginning and 267.0 MB in the end (delta: -94.6 MB). Peak memory consumption was 4.5 MB. Max. memory is 8.0 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - PositiveResult [Line: 13]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 40 locations, 1 error locations. Started 1 CEGAR loops. VerificationResult: SAFE, OverallTime: 17232.0ms, OverallIterations: 23, TraceHistogramMax: 13, EmptinessCheckTime: 28.5ms, AutomataDifference: 5763.3ms, DeadEndRemovalTime: 0.0ms, HoareAnnotationTime: 0.0ms, InitialAbstractionConstructionTime: 5.9ms, PartialOrderReductionTime: 0.0ms, HoareTripleCheckerStatistics: 1131 SDtfs, 1403 SDslu, 5911 SDs, 0 SdLazy, 5085 SolverSat, 1218 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 2914.2ms Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1642 GetRequests, 1271 SyntacticMatches, 6 SemanticMatches, 365 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 945 ImplicationChecksByTransitivity, 3804.9ms Time, 0.0ms BasicInterpolantAutomatonTime, BiggestAbstraction: size=188occurred in iteration=14, InterpolantAutomatonStates: 289, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0ms DumpTime, AutomataMinimizationStatistics: 158.9ms AutomataMinimizationTime, 23 MinimizatonAttempts, 387 StatesRemovedByMinimization, 20 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 186.4ms SsaConstructionTime, 571.5ms SatisfiabilityAnalysisTime, 4930.1ms InterpolantComputationTime, 1524 NumberOfCodeBlocks, 1477 NumberOfCodeBlocksAsserted, 32 NumberOfCheckSat, 1501 ConstructedInterpolants, 0 QuantifiedInterpolants, 6875 SizeOfPredicates, 153 NumberOfNonLiveVariables, 4775 ConjunctsInSsa, 635 ConjunctsInUnsatCore, 23 InterpolantComputations, 5 PerfectInterpolantSequences, 2228/2491 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold RESULT: Ultimate proved your program to be correct! Received shutdown request...